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,\dots ,S_k$ such that for each $i\in \{1\cdots k\}$ we have that $\sum _{j\in S_i}{a}_j\le 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}$?