 max planck institut
informatik # MPI-INF or MPI-SWS or Local Campus Event Calendar

 << Previous Entry Next Entry >> New Event Entry Edit this Entry Login to DB (to update, delete)
Title: Faster approximation schemes for the two-dimensional knapsack problem Sandy Heydrich Max-Planck-Institut für Informatik - D1 AG1 Mittagsseminar (own work) D1We use this to send out email in the morning. AG Audience English
Date: Tuesday, 13 December 2016 13:00 30 Minutes Saarbrücken E1 4 024
 An important question in theoretical computer science is to determine the best possible running time for solving a problem at hand. For geometric optimization problems, we often understand their complexity on a rough scale, but not very well on a finer scale. One such example is the two-dimensional knapsack problem for squares. There is a polynomial time (1+epsilon)-approximation algorithm for it (i.e., a PTAS) but the running time of this algorithm is triple exponential in 1/epsilon, i.e., Omega(n^{2^{2^{1/epsilon}}}). A double or triple exponential dependence on 1/epsilon is inherent in how this and several other algorithms for other geometric problems work. In this paper, we present an EPTAS for knapsack for squares, i.e., a (1+epsilon)-approximation algorithm with a running time of O_{epsilon}(1) * n^{O(1)}. In particular, the exponent of n in the running time does not depend on epsilon at all! Since there can be no FPTAS for the problem (unless P=NP) this is the best kind of approximation scheme we can hope for. To achieve this improvement, we introduce two new key ideas: We present a fast method to guess the Omega(2^{2^{1/epsilon}}) relatively large squares of a suitable near-optimal packing instead of using brute-force enumeration. Secondly, we introduce an indirect guessing framework to define sizes of cells for the remaining squares. In the previous PTAS each of these steps needs a running time of Omega(n^{2^{2^{1/epsilon}}}) and we improve both to O_{epsilon}(1) * n^{O(1)}. We complete our result by giving an algorithm for two-dimensional knapsack for rectangles under (1+epsilon)-resource augmentation. In this setting, we also improve the best known running time of Omega(n^{1/epsilon^{1/epsilon}}) to O_{epsilon}(1) * n^{O(1)} and compute even a solution with optimal profit, in contrast to the best previously known polynomial time algorithm for this setting that computes only an approximation. We believe that our new techniques have the potential to be useful for other settings as well.
Name(s): Sandy Heydrich