CS614. Advanced Algorithms. L19 Quiz.
CS614. Advanced Algorithms.
L19 Quiz
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.
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?
Describe a polynomial-time reduction from BOX-DEPTH to MAXCLIQUE.
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.]
Why don’t these two results imply that \(\mathrm{P}=\mathrm{NP}\)?