We consider the one-dimensional bin packing problem with unit-capacity bins and item sizes chosen according to the discrete uniform distribution U{j,k}, $1 < j \leq k,$ where each item size in {1/k,2/k,. . .,j/k} has probability 1/j of being chosen. Note that for fixed j,k as $m\rightarrow\infty$ the discrete distributions U{mj,mk} approach the continuous distribution U(0,j/k], where the item sizes are chosen uniformly from the interval (0,j/k]. We show that average-case behavior can differ substantially between the two types of distributions. In particular, for all j,k with j < k-1, there exist on-line algorithms that have constant expected wasted space under U{j,k}, whereas no on-line algorithm has even o(n 1/2 ) expected waste under U(0,u] for any $0 < u \leq 1$. Our U{j,k} result is an application of a general theorem of Courcoubetis and Weber [C. Courcoubetis and R.R. Weber, Probab. Engrg. Inform. Sci., 4 (1990), pp. 447--460] that covers all discrete distributions. Under each such distribution, the optimal expected waste for a random list of n items must be either $\Theta (n)$, $\Theta (n^{1/2} )$, or O(1), depending on whether certain"perfect" packings exist. The perfect packing theorem needed for the U{j,k} distributions is an intriguing result of independent combinatorial interest, and its proof is a cornerstone of the paper.

We consider the classical scheduling problem in which a given collection of tasks with lengths tl.t2,..., t,, are to be run on two processors, subject to specified precedence constraints among the tasks, so as to minimize the completion time of the last-finishing task, the so-called makespan of the schedule.A schedule is said to be nonpreemptive if each task, once started, is run continuously until its completion t,time units later, whereas a preemptive schedule allows the running of a task to be temporarily suspended and resumed at a later time, that is, run in noncontiguous pieces whose lengths merely sum to the task length t,.A long-standing conjecture is that, for any set of tasks and precedence constraints among them, the least makcspan achievable by a nonpreemptive schedule is no more than 4/3 the least makespan achievable when preemptions are allowed.In this paper, we prove this conjecture.

We consider the average case behavior of onedmensional bin paekmg algorithms in the case where bins have unit capacity and item sizes are chosen according to the ' 'dficrete uniform" distribution U~; k), 1 s j < k, where each item size in the set {llk,21k,..., ji k) has probability 1/j of beiig chosen.Note that for fixed j,k the distributions U{?nj;mk]' approach the continuous distribution U(O, jlk] as m A W, where in U(O, jl k] the item sizes are chosen uniformly horn the half-open interval (O,jik].In this paper, we show that average case behavior can differ substantially under the two types of distributions.We show that for all j, k, j < k-1, there exist on-line algorithms that have constant expected waste under U~; k], whereas no on-line algorithm can have less than C2(n1'2) waste under U(O, U] for any u s 1. Conmariwise, although the First Fit Decreasing (off-line) algorithm has constant expected waste under U(O, u] for all u < 1/2,

Article Free Access Share on Proof of the 4/3 conjecture for preemptive vs. nonpreemptive two-processor scheduling Authors: E. G. Coffman AT&T Bell Labs., Murray Hill, NJ AT&T Bell Labs., Murray Hill, NJView Profile , M. R. Garey AT&T Bell Labs., Murray Hill, NJ AT&T Bell Labs., Murray Hill, NJView Profile Authors Info & Claims STOC '91: Proceedings of the twenty-third annual ACM symposium on Theory of ComputingJanuary 1991 Pages 241–248https://doi.org/10.1145/103418.103447Online:03 January 1991Publication History 6citation231DownloadsMetricsTotal Citations6Total Downloads231Last 12 Months6Last 6 weeks2 Get Citation AlertsNew Citation Alert added!This alert has been successfully added and will be sent to:You will be notified whenever a record that you have chosen has been cited.To manage your alert preferences, click on the button below.Manage my AlertsNew Citation Alert!Please log in to your account Save to BinderSave to BinderCreate a New BinderNameCancelCreateExport CitationPublisher SiteeReaderPDF

T. Parsons originally proposed and studied the following pursuit-evasion problem on graphs: Members of a team of searchers traverse the edges of a graph G in pursuit of a fugitive, who moves along the edges of the graph with complete knowledge of the locations of the pursuers. What is the smallest number s ( G ) of searchers that will suffice for guaranteeing capture of the fugitive? It is shown that determining whether s ( G ) ≤ K , for a given integer K , is NP-complete for general graphs but can be solved in linear time for trees. We also provide a structural characterization of those graphs G with s ( G ) ≤ K for K = 1, 2, 3.

The fractional covering number$\tau^*$ of a hypergraph $H = ( V, E )$ is defined to be the minimum possible value of $\sum_{x \in V} t( x )$ where t ranges over all functions $t : V \to \mathbb{R}$ which satisfy $\sum_{x \in e} t ( x ) \geqq 1$ for all edges $e \in E$. In the case of ordinary graphs G, it is known that $2\tau^* ( G )$ is always an integer. By contrast, it is shown (among other things) that for any rational $p/q\geqq 1$, there is a 3-uniform hypergraph H with $\tau^* ( H ) = p/q$.

Various switching network construction advantageously use modules known as partial concentrators. A partial concentrator is an n-input, m-output, single-stage switching device in which each input has access to some but not all of the outputs. A partial concentrator is said to have capacity c, if, for any kor=2. In addition, it is shown that the rate of decrease of the cost ratio with increasing n is logarithmic for M=2, and polynomial for M>or=3.>

Abstract We study the problem of orienting all the undirected edges of a mixed multigraph so as to preserve reachability. Extending work by Robbins and by Boesch and Tindell, we develop a linear‐time algorithm to test whether there is an orientation that preserves strong connectivity and to construct such an orientation whenever possible. This algorithm makes no attempt to minimize distances in the resulting directed graph, and indeed the maximum distance, for example, can blow up by a factor proportional to the number of vertices in the graph. Extending work by Chvátal and Thomassen, we then prove that, if a mixed multigraph of radius r has any strongly connected orientation, it must have an orientation of radius at most 42 + Ar. The proof gives a polynomial‐time algorithm for constructing such an orientation.

We consider a problem of scheduling file transfers in a network so as to minimize overall finishing time. Although the general problem is NP-complete, we identify polynomial time solvable special cases and derive good performance bounds for several natural approximation algorithms, assuming the existence of a central controller. We also show how these bounds can be maintained in a distributed regime.

We show that, given a collection F of functions from a finite set D to itself, one can, in polynomial time, find a composition f of functions in F for which the size of $f(D)$ is minimized. This is to be contrasted with the fact that it is PSPACE-complete to determine whether a specific function f is a composition of functions in F. The running time of our algorithm is $O(|D|^2 (|D| + |F|))$, and this bound can be improved if an appropriately abbreviated representation of F is used. The problem first arose in connection with the minimization of conjunctive queries for relational databases.

We consider a problem of scheduling file transfers in a network so as to minimize overall finishing time, which we formalize as a problem of scheduling the edges of a weighted multigraph. Although the general problem is NP-complete, we identify polynomial time solvable special eases and derive good performance bounds for several natural approximation algorithms. The above results assume the existence of a central controller, but we also show how the approximation algorithms, along with their performance guarantees, can be adapted to a distributed regime.

Motivated by potential applications to computer storage allocation, we generalize the classical one-dimensional bin packing model to include dynamic arrivals and departures of items over time. Within this setting, we prove close upper and lower bounds on the worst-case performance of the commonly used First Fit packing algorithm, and, using adversary-type arguments, we show that no on-line packing algorithm can satisfy a substantially better performance bound than that for First Fit.

A simple (combinatorial) special case of the generalized Lloyd-Max (or quantization) problem is shown to be nondeterministic polynomial (NP)-complete. {\em A fortiori}, the general problem of communication theory, in its combinatorial forms, has at least that complexity.

T. Parsons proposed and partially analyzed the following pursuit-evasion problem on graphs: A team of searchers traverse the edges of a graph G in pursuit of a fugitive, who moves along the edges of the graph with complete knowledge of the locations of the pursuers. What is the smallest number s(G) of searchers that will suffice for guaranteeing capture of the fugitive? We show that determining whether s(G) ≤ K, for a given integer K, is NP-hard for general graphs but can be solved in linear time for trees. We also provide a structural characterization of those graphs with s(G) ≤ K for K = 1,2,3.

The basic problem considered is that of scheduling n unit-time tasks, with arbitrary release times and deadlines, so as to minimize the maximum task completion time. Previous work has shown that this problem can be solved rather easily when all release times are integers. We are concerned with the general case in which noninteger release times are allowed, a generalization that considerably increases the difficulty of the problem even for only a single processor. Our results are for the one-processor case, where we provide an $O(n\log n)$ algorithm based on the concept of “forbidden regions”.

We analyze several “level-oriented” algorithms for packing rectangles into a unit-width, infinite-height bin so as to minimize the total height of the packing. For the three algorithms we discuss, we show that the ratio of the height obtained by the algorithm to the optimal height is asymptotically bounded, respectively, by 2, 1.7, and 1.5. The latter two improve substantially over the performance bounds for previously proposed algorithms. In addition, we give more refined bounds for special cases in which the widths of the given rectangles are restricted and in which only squares are to be packed.

We consider the game of Checkers generalized to an N × N board. Although certain properties of positions are efficiently computable (e.g., can Black jump all of White's pieces in a single move?), the general question, given a position, of whether a specified player can force a win against best play by his opponent, is shown to be PSPACE-hard. Under certain reasonable assumptions about the "drawing rule" in force, the problem is itself in PSPACE and hence is PSPACE-complete.

The NP-completeness of a computational problem ~s frequently taken to unply its "mtractabthty" However, there are certain NP-complete problems mvolvmg numbers, such as PARTITION and KNAPSACK, which are considered by many practitioners to be tractable The reason for this IS that, although no algontluns for solvmg them in tune bounded by a polynomial m the mput length are known, algorithms are known which solve them m tune bounded by a polynomial m the input length and the magmtude of the largest number an the given problem mstance.For other NP-complete problems mvolvmg numbers it can be shown that no such "pseudopolynomml tune" algonthra can exist unless P = NP.In this paper we provide a standard framework for stating and proving "strong" NP-completeness results of this sort, survey some of the strong NP-completeness results proved to date, and indicate some unphcauons of these results for both opumlzatlon and approximaUon algontluns KEY WORDS AND PHRASES NP-completeness, pseudo-polynomial Ume, approxunauon schemes CR CATEGORIES 5 25 General

Abstract Let A be a finite set of points in a Euclidean space Er and M a minimum spanning tree (MST) for A, regarded as a subset of Er. If A′ ⊂ Er is a finite subset of M, then M is a spanning tree for A ∪ A′, but in general M will no longer be an MST. However, if A′ is chosen to be the set of all the midpoints of the line segments of M, then M will be an MST for A ∪ A′. Examples are given in which at least |A| ‐ 1 points must be adjoined to avoid destroying the MST.

We consider one of the basic, well-studied problems of scheduling theory, that of nonpreemptively scheduling n independent tasks on m identical, parallel processors with the objective of minimizing the “makespan,” i.e., the total timespan required to process all the given tasks. Because this problem is $NP$-complete and apparently intractable in general, much effort has been directed toward devising fast algorithms which find near-optimal schedules. The well-known LPT (Largest Processing Time first) algorithm always finds a schedule having makespan within $4/3 = 1.333 \cdots $ of the minimum possible makespan, and this is the best such bound satisfied by any previously published fast algorithm. We describe a comparably fast algorithm, based on techniques from “bin-packing,” which we prove satisfies a bound of 1.220. On the basis of exact upper bounds determined for each $m \leqq 7$, we conjecture that the best possible general bound for our algorithm is actually $20/17 = 1.176 \cdots $.

Abstract A minimal rectilinear Steiner tree for a set A of points in the plane is a tree which interconnects A using horizontal and vertical lines of shortest possible total length. Such trees have potential application to wire layout for printed circuits. Unfortunately, at present no practical algorithm is known for constructing these trees in general. We present two algorithms, each requiring a number of operations proportional to only a low degree polynomial in the number of points to be interconnected, for the special cases in which all the points of A lie on a small number of parallel lines or on the boundary of a rectangle.

Given a set $\mathcal{T} = \{ T_1 ,T_2 , \cdots ,T_n \} $ of tasks, each $T_i$ having execution time 1, an integer start-time $s_i \geqq 0$ and a deadline $d_i > 0$, along with precedence constraints among the tasks, we examine the problem of determining whether there exists a schedule on two identical processors that executes each task in the time interval between its start-time and deadline. We present an $O(n^3)$ algorithm that constructs such a schedule whenever one exists. The algorithm may also be used in a binary search mode to find the shortest such schedule or to find a schedule that minimizes maximum “tardiness”. A number of natural extensions of this problem are seen to be $NP$ complete and hence probably intractable.

We consider an abstract partitioning problem which has applications to the design of standard libraries of multipurpose units (such as multi-purpose circuit cards) and to storage allocation in the presence of users with conflicting demands. Although the general problem of finding minimum cost partitions appears to be very difficult, we describe a dynamic programming approach which can be quite efficient if the parameters for the items to be partitioned take on only a limited number of distinct values.

We show that the STEINER TREE problem and TRAVELING SALESMAN problem for points in the plane are NP-complete when distances are measured either by the rectilinear (Manhattan) metric or by a natural discretized version of the Euclidean metric. Our proofs also indicate that the problems are NP-hard if the distance measure is the (unmodified) Euclidean metric. However, for reasons we discuss, there is some question as to whether these problems, or even the well-solved MINIMUM SPANNING TREE problem, are in NP when the distance measure is the Euclidean metric.

Graph coloring problems, in which one would like to color the vertices of a given graph with a small number of colors so that no two adjacent vertices receive the same color, arise in many applications, including various scheduling and partitioning problems. In this paper the complexity and performance of algorithms which construct such colorings are investigated. For a graph G , let χ( G ) denote the minimum possible number of colors required to color G and, for any graph coloring algorithm A , let A ( G ) denote the number of colors used by A when applied to G . Since the graph coloring problem is known to be “NP-complete,” it is considered unlikely that any efficient algorithm can guarantee A ( G ) = χ( G ) for all input graphs. In this paper it is proved that even coming close to khgr;( G ) with a fast algorithm is hard. Specifically, it is shown that if for some constant r < 2 and constant d there exists a polynomial-time algorithm A which guarantees A ( G ) ≤ r ·χ( G ) + d , then there also exists a polynomial-time algorithm A which guarantees A ( G ) = χ( G ).

Given a set @@@@ = { T 1 , T 2 ,···, T n } of tasks, with each T i having execution time 1 and a deadline d i > 0, and a set of precedence constraints which restrict allowable schedules, the problem of determining whether there exists a schedule using two processors in which each task is completed before its deadline is examined. An efficient algorithm for finding such a schedule, whenever one exists, is given. The algorithm may also be used to find the shortest such schedule. In addition it is shown that the problem of finding a one-processor schedule which minimizes the number of tasks failing to meet their deadlines is NP-complete and, hence, is likely to be computationally intractable.

We consider the problem of determining whether a planar, cubic, triply-connected graph G has a Hamiltonian circuit. We show that this problem is NP-complete. Hence the Hamiltonian circuit problem for this class of graphs, or any larger class containing all such graphs, is probably computationally intractable.

A proposed method for testing printed circuit boards for the existence of possible (undesired) short circuits transforms the test minimization problem into one of finding minimum vertex colorings of certain special graphs, called line-of-sight graphs. Under certain assumptions on the possible types of short circuits, we analyze the structure of such graphs and show that a well-known and efficient algorithm can be used to color them with a small number of colors. In particular, we show that no more than 5, 8, or 12 colors (depending on the particular assumptions) will ever be required for such a graph, independent of the number of vertices. Thus, in such cases, the potential advantage of the proposed method over exhaustive testing could be considerable.

ABSTRACrr.An algorithm for constructing an optimal prefix code of n eqmprobable words over r unequal cost coding letters is given.The discussion is in terms of rooted labeled trees.The algorithm consists of two parts.The first one is an extension algorithm which constructs a prefix code of n words.This code is either optimal or is a "good" approximation The second part is a mending algorithm which changes the code constructed by the extension algorithm into an optimal code in case it is not already optimal.The validity of the combined algorithm is proved and its structure is analyzed.The analysis leads to further improvement of the algorithm's efficiency.It is shown that the number of steps required is at mnst O(r.n.log n), if a heap data structure is used Alternatively, one can use a data structure of r queues, in which case the number of steps is bounded by O(r.n).

One well-studied model of a multiprocessing system involves a fixed number n of identical abstract processors, a finite set of tasks to be executed, each requiring a specified amount of computation time, and a partial ordering on the tasks which requires certain tasks to be completed before certain others can be initiated. The nonpreemptive operation of the system is guided by an ordered list L of the tasks, according to the rule that whenever a processor becomes idle, it selects for processing the first unexecuted task on L which may validly be executed. We introduce an additional element of realism into this model by postulating the existence of a set of “resources” with the property that for each resource, the total usage of that resource at any instant of time may not exceed its total availability. For this augmented model, we determine upper bounds on the ratio of finishing times achieved using two different lists, L and $L'$, and exhibit constructions to show that the bounds are best possible.

We examine the computational complexity of scheduling problems associated with a certain abstract model of a multiprocessing system. The essential elements of the model are a finite number of identical processors, a finite set of tasks to be executed, a partial order constraining the sequence in which tasks may be executed, a finite set of limited resources, and, for each task, the time required for its execution and the amount of each resource which it requires. We focus on the complexity of algorithms for determining a schedule which satisfies the partial order and resource usage constraints and which completes all required processing before a given fixed deadline. For certain special cases, it is possible to give such a scheduling algorithm which runs in low order polynomial time. However, the main results of this paper imply that almost all cases of this scheduling problem, even with only one resource, are NP-complete and hence are as difficult as the notorious traveling salesman problem.

It is widely believed that showing a problem to be NP-complete is tantamount to proving its computational intractability. In this paper we show that a number of NP-complete problems remain NP-complete even when their domains are substantially restricted. First we show the completeness of SIMPLE MAX CUT (MAX CUT with edge weights restricted to value 1), and, as a corollary, the completeness of the OPTIMAL LINEAR ARRANGEMENT problem. We then show that even if the domains of the NODE COVER and DIRECTED HAMILTONIAN PATH problems are restricted to planar graphs, the two problems remain NP-complete, and that these and other graph problems remain NP-complete even when their domains are restricted to graphs with low node degrees. For GRAPH 3-COLORABILITY, NODE COVER, and UNDIRECTED HAMILTONIAN CIRCUIT, we determine essentially the lowest possible upper bounds on node degree for which the problems remain NP-complete.

An algorithm is given for constructing a binary tree of minimum weighted path length for n nonnegative weights under the constraint that no path length exceed a given bound L. The number of operations required is proportional to $Ln^2 $. Such problems, which impose an additional constraint on the usual Huffman tree, arise in many applications, including computer file searching and the construction of optimal prefix codes under certain practical conditions.

The following abstract problem models several practical problems in computer science and operations research: given a list L of real numbers between 0 and l, place the elements of L into a minimum number $L^ * $ of “bins” so that no bin contains numbers whose sum exceeds l. Motivated by the likelihood that an excessive amount of computation will be required by any algorithm which actually determines an optimal placement, we examine the performance of a number of simple algorithms which obtain “good” placements. The first-fit algorithm places each number, in succession, into the first bin in which it fits. The best-fit algorithm places each number, in succession, into the most nearly full bin in which it fits. We show that neither the first-fit nor the best-fit algorithm will ever use more than $\frac{17}{10}L^ * + 2$ bins. Furthermore, we outline a proof that, if L is in decreasing order, then neither algorithm will use more than $\frac{11}{9} L^ * + 4$ bins. Examples are given to show that both upper bounds are essentially the best possible. Similar results are obtained when the list L contains no numbers larger than $\alpha < 1$.

A number of authors (of. [12],[6], [7],[3],[11],[4],[5],[9]) have recently been concerned with scheduling problems associated with a certain model of an abstract multiprocessing system (to be described in the next section) and, in particular, with bounds on the worst-case behavior of this system as a function of the way in which the inputs are allowed to vary. In this paper, we introduce an additional element of realism into the model by postulating the existence of a set of “resources” with the property that at no time may the system use more than some predetermined amount of each resource. With this extra constraint taken into consideration, we derive a number of bounds on the behavior of this augmented system. It will be seen that this investigation leads to several interesting results in graph theory and analysis.

Various memory allocation problems can be modeled by the following abstract problem. Given a list A = (α1,α2,...αn,) of real numbers in the range (0, 1], place these in a minimum number of “bins” so that no bin holds numbers summing to more than 1. We let A* be the smallest number of bins into which the numbers of list A may be placed. Since a general placement algorithm for attaining A* appears to be impractical, it is important to determine good heuristic methods for assigning numbers of bins. We consider four such simple methods and analyze the worst-case performance of each, closely bounding the maximum of the ratio of the number of bins used by each method applied to list A to the optimal quantity A*.

We consider economical representations for the path information in a directed graph. A directed graph $G^t $ is said to be a transitive reduction of the directed graph G provided that (i) $G^t $ has a directed path from vertex u to vertex v if and only if G has a directed path from vertex u to vertex v, and (ii) there is no graph with fewer arcs than $G^t $ satisfying condition (i). Though directed graphs with cycles may have more than one such representation, we select a natural canonical representative as the transitive reduction for such graphs. It is shown that the time complexity of the best algorithm for finding the transitive reduction of a graph is the same as the time to compute the transitive closure of a graph or to perform Boolean matrix multiplication.

A new approach to the design of complex logic circuitry using magnetic bubbles is described. The method is based on the construction of cells that perform simple logical operations and that can be combined to realize more complex functions. An important property of these cells is that no bubbles ever enter or leave any cell, all intercell communications being accomplished by bubble interactions near the cell boundaries. Illustratively, a set of four basic cells is described which is sufficient to realize all combinatorial and sequential switching functions. The cells possess an important synchronization property that allows them to be combined in a manner quite similar to combining semiconductor gates in current technology.

Given some unknown object belonging to a known finite set of n possibilities, it is required to determine its identity by successive comparisons with each of the possibilities. Associating with each of these possibilities a testing cost and a probability that it is identical to the unknown object, we would like to obtain such a testing procedure which has minimum expected testing cost. Intuitively, it would appear that one should proceed by always applying the remaining test with least cost/probability ratio. We show that this technique does not necessarily yield the optimal procedure and present an algorithm which determines the optimal testing sequence in a number of steps proportional to n · log2n.