NDLI: A Constant-Factor Approximation Algorithm for Unsplittable Flow on Paths

Content Provider	Society for Industrial and Applied Mathematics (SIAM)
Author	Wiese, Andreas Schulz, Jens Bonsma, Paul
Copyright Year	2014
Abstract	In the unsplittable flow problem on a path, we are given a capacitated path $P$ and $n$ tasks, each task having a demand, a profit, and start and end vertices. The goal is to compute a maximum profit set of tasks such that, for each edge $e$ of $P$, the total demand of selected tasks that use $e$ does not exceed the capacity of $e$. This is a well-studied problem that has been described under alternative names, such as resource allocation, bandwidth allocation, resource constrained scheduling, temporal knapsack, and interval packing. We present a polynomial time constant-factor approximation algorithm for this problem. This improves on the previous best known approximation ratio of $O(\log n)$. The approximation ratio of our algorithm is $7+\epsilon$ for any $\epsilon>0$. We introduce several novel algorithmic techniques, which might be of independent interest: a framework which reduces the problem to instances with a bounded range of capacities, and a new geometrically inspired dynamic program which solves to optimality a special case of the problem of finding a maximum weight independent set of rectangles. In the setting of resource augmentation, wherein the capacities can be slightly violated, we give a $(2+\epsilon)$-approximation algorithm. In addition, we show that the problem is strongly NP-hard even if all edge capacities are equal and all demands are either 1, 2, or 3.
Starting Page	767
Ending Page	799
Page Count	33
File Format	PDF
ISSN	00975397
DOI	10.1137/120868360
e-ISSN	10957111
Journal	SIAM Journal on Computing (SMJCAT)
Issue Number	2 (Special Section on the Fifty-Second IEEE Annual Symposium on Foundations of Computer Science (FOCS 2011))
Volume Number	43
Language	English
Publisher	Society for Industrial and Applied Mathematics
Publisher Date	2014-04-29
Access Restriction	Subscribed
Subject Keyword	unsplittable flow resource allocation Approximation algorithms strong NP-hardness constant-factor approximation Combinatorics maximum weight independent set
Content Type	Text
Resource Type	Article
Subject	Mathematics Computer Science

Sl.	Authority	Responsibilities	Communication Details
1	Ministry of Education (GoI), Department of Higher Education	Sanctioning Authority	https://www.education.gov.in/ict-initiatives
2	Indian Institute of Technology Kharagpur	Host Institute of the Project: The host institute of the project is responsible for providing infrastructure support and hosting the project	https://www.iitkgp.ac.in
3	National Digital Library of India Office, Indian Institute of Technology Kharagpur	The administrative and infrastructural headquarters of the project	Dr. B. Sutradhar bsutra@ndl.gov.in
4	Project PI / Joint PI	Principal Investigator and Joint Principal Investigators of the project	Dr. B. Sutradhar bsutra@ndl.gov.in Prof. Saswat Chakrabarti will be added soon
5	Website/Portal (Helpdesk)	Queries regarding NDLI and its services	support@ndl.gov.in
6	Contents and Copyright Issues	Queries related to content curation and copyright issues	content@ndl.gov.in
7	National Digital Library of India Club (NDLI Club)	Queries related to NDLI Club formation, support, user awareness program, seminar/symposium, collaboration, social media, promotion, and outreach	clubsupport@ndl.gov.in
8	Digital Preservation Centre (DPC)	Assistance with digitizing and archiving copyright-free printed books	dpc@ndl.gov.in
9	IDR Setup or Support	Queries related to establishment and support of Institutional Digital Repository (IDR) and IDR workshops	idr@ndl.gov.in

A Constant Factor Approximation Algorithm for Unsplittable Flow on Paths

A Constant Factor Approximation Algorithm for Unsplittable Flow on Paths

A constant factor approximation algorithm for unsplittable flow on paths (2011)

A Near-linear Time Constant Factor Algorithm for Unsplittable Flow Problem on Line with Bag Constraints

A constant factor approximation algorithm for the storage allocation problem: extended abstract

Approximation Algorithms for the Unsplittable Flow Problem ∗ (2005)

A quasi-PTAS for unsplittable flow on line graphs

Approximation algorithms for the unsplittable flow problem on paths and trees.

Approximation Algorithms for the Unsplittable Flow Problem (2002)

A Constant-Factor Approximation Algorithm for Unsplittable Flow on Paths

Similar Documents

A Constant Factor Approximation Algorithm for Unsplittable Flow on Paths

A Constant Factor Approximation Algorithm for Unsplittable Flow on Paths

A constant factor approximation algorithm for unsplittable flow on paths (2011)

A Near-linear Time Constant Factor Algorithm for Unsplittable Flow Problem on Line with Bag Constraints

A constant factor approximation algorithm for the storage allocation problem: extended abstract

Approximation Algorithms for the Unsplittable Flow Problem ∗ (2005)

A quasi-PTAS for unsplittable flow on line graphs

Approximation algorithms for the unsplittable flow problem on paths and trees.

Approximation Algorithms for the Unsplittable Flow Problem (2002)

A Constant-Factor Approximation Algorithm for Unsplittable Flow on Paths