CS614. Advanced Algorithms. L19 Quiz.

CS614. Advanced Algorithms.

L19 Quiz

Back to the course page

Problem 1. Bin Packing

Consider the bin-packing problem:

Input: n items with sizes a_1 \cdots a_n respectively, a positive integer B (bin capacity) and a positive integer k (number of bins). Question: Is there a partition of the set \{1 \cdots n\} into sets S_1, \ldots, S_k such that for each i \in\{1 \cdots k\} we have that \sum_{j \in S_i} a_j \leq B?

Show that Bin Packing is NP-complete.

Problem 2. BOX-DEPTH

Consider the following problem, called BOX-DEPTH: Given a set of n axisaligned rectangles in the plane, how big is the largest subset of these rectangles that contain a common point?

1. Describe a polynomial-time reduction from BOX-DEPTH to MAXCLIQUE.

2. Describe and analyze a polynomial-time algorithm for BOX-DEPTH. [Hint: O\left(n^3\right) time should be easy, but O(n \log n) time is possible.]

3. Why don’t these two results imply that \mathrm{P}=\mathrm{NP}?