License: 
Creative Commons Attribution-NonCommercial-NoDerivs 3.0 Unported license (CC BY-NC-ND 3.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.FSTTCS.2010.181
URN: urn:nbn:de:0030-drops-28623
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2010/2862/
Chakaravarthy, Venkatesan T. ;
Choudhury, Anamitra R. ;
Sabharwal, Yogish
A Near-linear Time Constant Factor Algorithm for Unsplittable Flow Problem on Line with Bag Constraints
Abstract
Consider a scenario where we need to schedule a set of jobs on a system offering some resource (such as electrical power or communication bandwidth), which we shall refer to as bandwidth. Each job consists of a set (or bag) of job instances. For each job instance, the input specifies the start time, finish time, bandwidth requirement and profit. The bandwidth offered by the system varies at different points of time and is specified as part of the input. A feasible solution is to choose a subset of instances such that at
any point of time, the sum of bandwidth requirements of the chosen instances does not exceed the bandwidth available at that point of time, and furthermore, at most one instance is picked from each job.
The goal is to find a maximum profit feasible solution. We study this problem under a natural assumption called the no-bottleneck assumption (NBA), wherein the bandwidth requirement of any job instance is at most the minimum bandwidth available. We present a simple, near-linear time constant factor approximation algorithm for this problem, under NBA. When each job consists of only one job instance, the above problem is the same as the well-studied unsplittable flow problem (UFP) on lines. A constant factor approximation algorithm is known for the UFP on line, under NBA.
Our result leads to an alternative constant factor approximation algorithm for this problem. Though the approximation ratio achieved by our algorithm is inferior, it is much simpler, deterministic and faster in comparison to the existing algorithms. Our algorithm runs in near-linear time ($O(n*log^2 n)$), whereas the running time of the known algorithms is a high order polynomial. The core idea behind our algorithm is a reduction from the varying bandwidth case to the easier uniform bandwidth case, using a technique that we call slicing.
BibTeX - Entry
@InProceedings{chakaravarthy_et_al:LIPIcs:2010:2862,
author = {Venkatesan T. Chakaravarthy and Anamitra R. Choudhury and Yogish Sabharwal},
title = {{A Near-linear Time Constant Factor Algorithm for Unsplittable Flow Problem on Line with Bag Constraints}},
booktitle = {IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2010)},
pages = {181--191},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-939897-23-1},
ISSN = {1868-8969},
year = {2010},
volume = {8},
editor = {Kamal Lodaya and Meena Mahajan},
publisher = {Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
address = {Dagstuhl, Germany},
URL = {http://drops.dagstuhl.de/opus/volltexte/2010/2862},
URN = {urn:nbn:de:0030-drops-28623},
doi = {10.4230/LIPIcs.FSTTCS.2010.181},
annote = {Keywords: Approximation Algorithms; Scheduling; Resource Allocation}
}
|
Keywords: |
|
Approximation Algorithms; Scheduling; Resource Allocation |
|
Collection: |
|
IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2010) |
|
Issue Date: |
|
2010 |
|
Date of publication: |
|
14.12.2010 |
