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: On Approximating Storage Allocation Problems as Good as Their Siblings Andreas Wiese Max-Planck-Institut für Informatik - D1 AG1 Mittagsseminar (own work) D1, MMCIWe use this to send out email in the morning. AG Audience English
Date: Thursday, 11 June 2015 13:00 30 Minutes Saarbrücken E1 4 024
 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 awiese@mpi-inf.mpg.de