We present a new technique that gives a more thorough analysis on Johnson's classical algorithm for the maximum satisfiability problem. In contrast to the common belief for two decades that Johnson's algorithm has performance ratio 1/2, we show that the performance ratio is 2/3, and that this bound is tight. Moreover we show that simple generalizations of Johnson's algorithm do not improve the performance ratio bound 2/3.

This paper considers the problem of scheduling a set of precedence-related tasks on a nonpreemptive homogeneous message-passing multiprocessors system in order to minimize the makespan, that is, the completion time of the last task relative to start time of the first task. We propose family of scheduling algorithms, called IPR for immediate predecessor rescheduling, which utilize one level of backtracking. We also develop a unifying framework to facilitate the comparison between our results and the various models and algorithms that have been previously studied. We show, both theoretically and experimentally, that the IPR algorithms out-perform previous algorithms in terms of both time complexity and the makespans of the resulting schedules. Moreover our simulation results indicate that the relative advantage of the IPR algorithms increases as the communication constraint is relaxed.

The WK-Recursive Network (WKRN) is a hierarchical interconnection network that is recursively defined and has excellent properties for scalable message-passing multicomputer systems. In this paper, we present efficient routing and broadcasting schemes in a WKRN. For efficient routing, we define the MP-graph between the source and destination nodes of the message. For efficient broadcasting, we define the EDHP-graph and the NDST-graph. The MP-graph can also be used for message routing in the presence of faulty nodes. Similarly, the EDHP-graph (the NDST-graph) can be used for message broadcast in the presence of faulty links (nodes). Fault-tolerant communication schemes using these graphs have the advantage that no information about the presence or location of faulty components is required. Moreover, the MP-graph and the NDSTgraph can be used under different fault models. We analyze the communication delays for message routing (broadcast) along MP-graphs (EDHP-graphs and NDST-graphs) under fault-free and faulty conditions.

Consider the classic bin packing problem, in which we seek to pack a list of items into the minimum number of unit-capacity bins. The worst-case performance of a compound bin packing algorithm that selects the better packing produced by two previously analyzed heuristics, namely, FFD (first fit decreasing) and B2F (best two fit) is investigated. FFD and B2F can asymptotically require as many as $\frac{11}{9}$ and $\frac{5}{4}$ times the optimal number of bins, respectively. A new technique, weighting function averaging, is introduced to prove that our compound algorithm is superior to the individual heuristics on which it is based, never using more than $\frac{6}{5}$ times the optimal number of bins.

The authors have been developing a theory of learning automata that is applicable to studying goal-seeking systems of many types. The stepwise convergence of such systems to a goal state can be mapped into the training sequences of an appropriate learning automaton. This theory has been expanded to include infinite sets of states. The learning automaton may have an infinite characteristic semigroup of state transitions. The algebraic properties of the automaton are determined by this semigroup. A topology is introduced into the characteristic semigroup,S'. The latter can be considered as a function space of transformations ofS. Behavior characteristics of the learning automaton be defined rigorously. In special cases, they can be related to the topological properties ofS' andS, such as continuity of the transition function, separation properties and compactness

CSAB states in its guidelines that one of its six undergraduate core curriculum subject areas is computer theory. It appears that the ACM Core Curriculum Committee will also suggest a core course in this area. However, courses in computer theory, under the titles “Formal Languages” or “Theory of Computation”, have traditionally been taught on the senior or graduate level. There has been little discussion concerning the development of a computer theory course for use at the sophomore or junior level. Also, computer theory is also becoming a larger part of other computer science courses such as discrete structures and compiler design theory. A clearer understanding is needed of how different aspects of computer theory should be developed throughout the undergraduate computer science curriculum.

We consider a bin-packing problem where the sizes of the bins are allowed to vary and where the goal is to maximize the number of pieces packed. This problem is NP-hard. We examine a new efficient approximation algorithm which is a hybrid of two algorithms reported earlier, First-Fit Decreasing (FFD) and Best-Two Fit (B2F). The hybrid is iterative: it attempts to pack smaller and smaller suffixes of its list of pieces until it succeeds in packing an entire suffix. During each attempt, the hybrid operates by partitioning the current list of pieces and packing one part by B2F and afterward packing the other part of its list by FFD. We prove that no instance of the problem exists where an optimal algorithm can pack more than $\tfrac{4}{3}$ the number of pieces the hybrid can pack. We also give a sequence of examples for which the ratio of the number of pieces packed optimally and by our algorithm increases asymptotically to $\frac{4}{3}$.

We examine the nonpreemptive assignment of independent tasks to a system of uniform processors with the objective of minimizing the makespan. The worst case bound for the largest processing time first algorithm for this problem is tightened to be in the interval (1.52, 1.67).

In the classical bin packing problem one seeks to pack a list of pieces in the minimum space using unit capacity bins. This paper addresses the more general problem in which a fixed collection of bin sizes is allowed. Three efficient approximation algorithms are described and analyzed. They guarantee asymptotic worst-case performance bounds of 2, ${3 / 2}$ and ${4 / 3}$.

Abstract This article presents two sorting procedures with computational complexity O(nk2 log(k)) and O(nk2) to perform the generalized vector product A 1⊗ A2⊗ ⃛ ⊗ An, where each vector Ai has k distinct elements arranged in strictly increasing order. The vector product identifies the k minimal sums, each sum being defined as having one addend from each vector.

This paper considers the problem of nonpreemptively scheduling n independent jobs on m identical, parallel processors with the object of minimizing the “makespan”, or completion time for the entire set of jobs. Coffman, Garey, and Johnson [SIAM J. Comput., 7 (1978), pp. 1–17] described an algorithm MULTIFIT which has a considerably better worst case performance than the largest processing time first algorithm. In this paper we tighten the bounds obtained in that paper on the worst case behavior of this algorithm by giving an example showing that it may be as bad as 13/11 and proving that it can be no worse than 6/5.

We examine the nonpreemptive assignment of N independent tasks to a system of M uniform processors with the objective of reducing the makespan, or the time required from the start of execution until all tasks are completed. Since the problem of finding a minimal makespan has been shown to be NP-hard, and hence unlikely to permit an efficient solution procedure, near-optimal heuristic algorithms have been studied. It is known that LPT (longest processing time first) schedules are within twice the length of the optimum. We analyze a variation of the MULTIFIT algorithm derived from bin packing, and prove that its worst-case performance bound is within 1.4 of the optimum.