CSci 5403, Fall 2015

CSci 5403, Fall 2015

Homework 6 due: December 7, 2015

 


1. Where you bin? Bin packing is an optimization problem that models the situation of someone packing items into bins, with the goal of minimizing the number of bins used. Formally, a binpack instance is a set of lengths \((a_{1},\dots,a_{n})\) and a capacity \(C\), and a solution is a set of bins \(\{B_{1},\dots,B_{j}\}\) where each \(B_{i}\subseteq[n]\), \(B_{i}\cap B_{j}=\emptyset\) and \(\bigcup_{i}B_{i}=[n]\), such that for all \(j\), \(\sum_{i\in B_{j}}a_{i}\leq C\).

  • (a)

    The binpack decision problem is: given a binpack instance and a number \(k\), is there a solution using \(k\) or fewer bins? Prove, for fun, that the decision version is NP-complete.

Answer:

  • (b)

    Give a very simple algorithm that yields a \(2\)-approximation, e.g. it uses at most twice as many bins as the optimal solution.

Answer:


1. Adopting adaptiveness. One property of an \((r,q)\)-verifier that was not explicitly mentioned in Lecture 21 is whether its oracle queries are adaptive, e.g., whether the value of the \(i^{\text{th}}\) query depends on the results of the first \(i-1\) queries. Our proof that the PCP theorem is equivalent to the existence of a gap-producing reduction from 3sat to max-3sat actually relies on a non-adaptive verifier (e.g. the proof locations that it queries are a fixed function of the input \(x\) and random string \(s\)). Prove that when \(q(n)=O(1)\) this distinction is not very important: every adaptive \((r,q)\)-verifier can be simulated by a nonadaptive \((r,2^{q})\) verifier.

Answer: