ROUGH DRAFT authorea.com/92210
Main Data History
Export
Show Index Toggle 0 comments
  •  Quick Edit
  • 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 th