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: