Dartmouth College Computer Science Technical Report series CS home TR home TR search TR listserv By author: A B C D E F G H I J K L M N O P Q R S T U V W X Y Z By number: 2019, 2018, 2017, 2016, 2015, 2014, 2013, 2012, 2011, 2010, 2009, 2008, 2007, 2006, 2005, 2004, 2003, 2002, 2001, 2000, 1999, 1998, 1997, 1996, 1995, 1994, 1993, 1992, 1991, 1990, 1989, 1988, 1987, 1986

Approximability of the Unsplittable Flow Problem on Trees
Chrisil Arackaparambil, Amit Chakrabarti, Chien-Chung Huang
Dartmouth TR2009-642

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.

PDF (715KB)

Bibliographic citation for this report: [plain text] [BIB] [BibTeX] [Refer]

Or copy and paste:
Chrisil Arackaparambil, Amit Chakrabarti, and Chien-Chung Huang, "Approximability of the Unsplittable Flow Problem on Trees." Dartmouth Computer Science Technical Report TR2009-642, March 2009.

To receive paper copy of a report, by mail, send your address and the TR number to reports AT cs.dartmouth.edu

Copyright notice: The documents contained in this server are included by the contributing authors as a means to ensure timely dissemination of scholarly and technical work on a non-commercial basis. Copyright and all rights therein are maintained by the authors or by other copyright holders, notwithstanding that they have offered their works here electronically. It is understood that all persons copying this information will adhere to the terms and constraints invoked by each author's copyright. These works may not be reposted without the explicit permission of the copyright holder.

Technical reports collection maintained by David Kotz.