BIB-VERSION:: CS-TR-v2.0
ID:: ncstrl.dartmouthcs//TR2009-642
ENTRY:: March 03, 2009
ORGANIZATION:: Dartmouth College, Computer Science
REQUESTED-BY:: ac@cs.dartmouth.edu
REQUESTED-FOR:: cja@cs.dartmouth.edu
REQUESTED-DATE:: Tue Mar 3 08:31:57 EST 2009
TITLE:: Approximability of the Unsplittable Flow Problem on Trees
TYPE:: Technical Report (paper)
REVISION:: 1
AUTHOR:: Arackaparambil, Chrisil
AUTHOR:: Chakrabarti, Amit
AUTHOR:: Huang, Chien-Chung
DATE:: March 2009
RETRIEVAL:: For a paper copy, email <reports@cs.dartmouth.edu>
RETRIEVAL:: For a paper copy, write to
       Technical Report Librarian
       Department of Computer Science
       Dartmouth College
       6211 Sudikoff Laboratory
       Hanover, NH 03755-3510
       USA
RETRIEVAL:: PDF at http://www.cs.dartmouth.edu/reports/TR2009-642.pdf
ABSTRACT:: 
   We consider the approximability of the Unsplittable Flow Problem
(UFP) on tree graphs, and give a deterministic quasi-polynomial time
approximation scheme for the problem when the number of leaves in the
tree graph is at most poly-logarithmic in $n$ (the number of demands),
and when all edge capacities and resource requirements are suitably
bounded.
Our algorithm generalizes a recent technique that obtained the first
such approximation scheme for line graphs.  Our results show that the
problem is not APX-hard for such graphs unless NP \subseteq
DTIME(2^{polylog(n)}).  Further, a reduction from the
Demand Matching Problem shows that UFP is APX-hard when the number of
leaves is Omega(n^\epsilon) for any constant \epsilon > 0.
   Together, the two results give a nearly tight characterization of the
approximability of the problem on tree graphs in terms of the number
of leaves, and show the structure of the graph that results in
hardness of approximation.
END:: ncstrl.dartmouthcs//TR2009-642