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:On Approximating Storage Allocation Problems as Good as Their Siblings
Speaker:Andreas Wiese
coming from:Max-Planck-Institut für Informatik - D1
Speakers Bio:
Event Type:AG1 Mittagsseminar (own work)
Visibility:D1, MMCI
We use this to send out email in the morning.
Level:AG Audience
Date, Time and Location
Date:Thursday, 11 June 2015
Duration:30 Minutes
Building:E1 4
Packing problems are a fundamental class of problems studied in combinatorial optimization.

Three particularly important and well-studied
questions in this domain are the Unsplittable Flow on a Path problem
(UFP), the Maximum Weight Independent Set of Rectangles problem (MWISR),
and the 2-dimensional geometric knapsack problem. In this paper, we
study the Storage Allocation Problem (SAP) which is a natural combination
of those three questions. Given is a path with edge capacities and
a set of tasks that are specified by start and end vertices, demands,
and profits. The goal is to select a subset of the tasks that
can be drawn as non-overlapping rectangles underneath
the capacity profile, the height of a rectangles corresponding to
the demand of the respective task. This problem arises naturally in
settings where a certain available bandwidth has to be allocated contiguously
to selected requests.

While for 2D-knapsack and UFP there are polynomial time (2+epsilon)-approximation
algorithms known [Jansen and Zhang, SODA 2004] [Anagnostopoulos
et al., SODA 2014] the best known approximation factor for SAP is
9+epsilon [Bar-Yehuda, SPAA 2013]. In this paper, we level
the understanding of SAP and the other two problems above by presenting
a polynomial time (2+epsilon)-approximation algorithm for SAP.
A typically difficult special case of UFP and its variations arises
if all input tasks are relatively large compared to the capacity of
the smallest edge they are using. For that case, we even obtain a
pseudopolynomial time exact algorithm for SAP.
Finally, we show that any solution to UFP can be transformed to a solution
to SAP by either losing only a constant factor of the profit or by increasing the
edge capacities by a constant factor.

Name(s):Andreas Wiese
Video Broadcast
Video Broadcast:NoTo Location:
Tags, Category, Keywords and additional notes
Attachments, File(s):

Andreas Wiese, 05/20/2015 04:44 PM
Last modified:
Uwe Brahm/MPII/DE, 11/24/2016 04:13 PM
  • Andreas Wiese, 05/20/2015 04:44 PM -- Created document.