Max-Planck-Institut für Informatik
max planck institut
mpii logo Minerva of the Max Planck Society

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)
What and Who
Title:Faster approximation schemes for the two-dimensional knapsack problem
Speaker:Sandy Heydrich
coming from:Max-Planck-Institut für Informatik - D1
Speakers Bio:
Event Type:AG1 Mittagsseminar (own work)
We use this to send out email in the morning.
Level:AG Audience
Date, Time and Location
Date:Tuesday, 13 December 2016
Duration:30 Minutes
Building:E1 4
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
Video Broadcast
Video Broadcast:NoTo Location:
Tags, Category, Keywords and additional notes
Attachments, File(s):

Sandy Heydrich, 10/07/2016 09:57 AM
Last modified:
halma/MPII/DE, 10/16/2018 04:04 PM
  • Sandy Heydrich, 10/07/2016 09:57 AM -- Created document.