Questions? Call 800-624-6242

| Items in cart [0]

PAPERBACK
price:\$52.75

## Probability and Algorithms (1992) Commission on Physical Sciences, Mathematics, and Applications (CPSMA)

### Citation Manager

. "7 Probabilistic Analysis of Packing and Related Partitioning Problems." Probability and Algorithms. Washington, DC: The National Academies Press, 1992.

Please select a format:

 Page 88

The following HTML text is provided to enhance online readability. Many aspects of typography translate only awkwardly to HTML. Please use the page image as the authoritative form to ensure accuracy.

Probability and Algorithms

### 7.1Introduction

#### 7.1.1Problems

The problems studied here all involve the partitioning of a set of positive numbers into a collection of subsets satisfying a sum constraint. The following two problems are among the most fundamental. They have wide-ranging applications throughout computer science and operations research (see, e.g., Coffman et al., 1984b; Coffman et al., 1988; and Dyckhoff, 1990).

Bin Packing (BP). Given c > 0 and a set S = {X1, ..., Xn} with , , partition S into a minimum number of subsets such that the sum of the Xi's in each subset is no more than c.

The Xi's are usually called items or pieces and are thought of as being packed into bins B1, B2, ..., each with capacity c; the items packed in a bin constitute one of the subsets in a solution to the optimization problem.

Multiprocessor Scheduling (MS). Given an integer and a set S = {X 1, ..., Xn}, partition S into m subsets such that among all such partitions, the maximum subset sum is minimized.

Note that the MS problem is complementary to the BP problem in that the objective function and the given parameter are interchanged. The items are now called tasks or jobs, with running times or durations instead of sizes. The bins become processors P1, ..., Pm, and the partition becomes a schedule of S on m processors that minimizes the makespan c, i.e., the completion time of a latest finishing task. Because of the sequential nature of most heuristics, it is convenient to assume that the set to be partitioned is given as a list Ln = (X1, ..., Xn) from which items are packed or scheduled one by one. If H denotes an MS heuristic, then H(Ln, m) denotes the makespan of the m-processor schedule generated by H for the tasks in Ln. In the BP problem the bin capacity is only a scale factor, so we take c = 1 without loss of generality. Thus, if H denotes a BP heuristic, then H(Ln) denotes the number of unit capacity bins in which H packs the items of Ln.

Merely deciding whether a list of numbers can be partitioned into two subsets with equal sums is NP-complete, so, as one would expect, both the BP and the MS problems are NP-complete. Thus, one is unlikely to find an

 Page 88
 Front Matter (R1-R10) 1 Introduction (1-16) 2 Simulated Annealing (17-30) 3 Approximate Counting Via Markov Chains (31-38) 4 Probabilistic Algorithms for Speedup (39-52) 5 Probabilistic Algorithms for Defeating Adversaries (53-64) 6 Pseudorandom Numbers (65-86) 7 Probabilistic Analysis of Packing and Related Partitioning Problems (87-108) 8 Probability and Problems in Euclidean Combinatorial Optimization (109-130) 9 Probabilistic Analysis in Linear Programming (131-148) 10 Randomization in Parallel Algorithms (149-160) 11 Randomly Wired Multistage Networks (161-174) 12 Missing Pieces, Derandomization, and Concluding Remarks (175-178)