Proceedings Article, Paper
@InProceedings
Beitrag in Tagungsband, Workshop


Show entries of:

this year (2019) | last year (2018) | two years ago (2017) | Notes URL

Action:

login to update

Options:








Author, Editor

Author(s):

Martens, Maren
Skutella, Martin

dblp
dblp



Editor(s):

Albers, Susanne
Radzik, Tomasz

dblp
dblp

Not MPII Editor(s):

Albers, Susanne
Radzik, Thomasz

BibTeX cite key*:

Martens2004

Title, Booktitle

Title*:

Flows on Few Paths: Algorithms and Lower Bounds

Booktitle*:

Algorithms – ESA 2004: 12th Annual European Symposium

Event, URLs

URL of the conference:

http://www.ii.uib.no/algo2004/esa2004/

URL for downloading the paper:


Event Address*:

Bergen, Norway

Language:

English

Event Date*
(no longer used):


Organization:


Event Start Date:

14 September 2004

Event End Date:

17 September 2004

Publisher

Name*:

Springer

URL:

http://www.springeronline.com

Address*:

Berlin, Germany

Type:


Vol, No, Year, pp.

Series:

Lecture Notes in Computer Science

Volume:

3221

Number:


Month:

September

Pages:

520-531

Year*:

2004

VG Wort Pages:


ISBN/ISSN:

3-540-23025-4

Sequence Number:


DOI:




Note, Abstract, ©


(LaTeX) Abstract:

In classical network flow theory, flow being sent from a source to a destination may be split into a large number of chunks traveling on different paths through the network. This effect is undesired or even forbidden in many applications. Kleinberg introduced the unsplittable flow problem where all flow traveling from a source to a destination must be sent on only one path. This is a generalization of the NP-complete edge-disjoint paths problem. In particular, the randomized rounding technique of Raghavan and Thompson can be applied. A generalization of unsplittable flows are k-splittable flows where the number of paths used by a commodity $i$ is bounded by a given integer~$k_i$.

The contribution of this paper is twofold. First, for the unsplittable flow problem, we prove a lower bound of~$\Omega(\log m/\log\log m)$ on the performance of randomized rounding. This result matches the best known upper bound of~$O(\log m/\log\log m)$. To the best of our knowledge, the problem of finding a non-trivial lower bound has so far been open.

In the second part of the paper, we study a new variant of the k-splittable flow problem with additional constraints on the amount of flow being sent along each path. The motivation for these constraints comes from the following packing and routing problem: A commodity must be shipped using a given number of containers of given sizes. First, one has to make a decision on the fraction of the commodity packed into each container. Then, the containers must be routed through a network whose edges correspond, for example, to ships or trains. Each edge has a capacity bounding the total size or weight of containers which are being routed on it. We present approximation results for two versions of this problem with multiple commodities and the objective to minimize the congestion of the network. The key idea is to reduce the problem under consideration to an unsplittable flow problem while only losing a constant factor in the performance ratio.

Keywords:

multicommodity flow, network flow, unsplittable flow, k-splittable flow, approximation algorithm, randomized rounding



Download
Access Level:

Public

Correlation

MPG Unit:

Max-Planck-Institut für Informatik



MPG Subunit:

Algorithms and Complexity Group

Appearance:

MPII WWW Server, MPII FTP Server, MPG publications list, university publications list, working group publication list, Fachbeirat, VG Wort



BibTeX Entry:

@INPROCEEDINGS{Martens2004,
AUTHOR = {Martens, Maren and Skutella, Martin},
EDITOR = {Albers, Susanne and Radzik, Tomasz},
TITLE = {Flows on Few Paths: Algorithms and Lower Bounds},
BOOKTITLE = {Algorithms – ESA 2004: 12th Annual European Symposium},
PUBLISHER = {Springer},
YEAR = {2004},
VOLUME = {3221},
PAGES = {520--531},
SERIES = {Lecture Notes in Computer Science},
ADDRESS = {Bergen, Norway},
MONTH = {September},
ISBN = {3-540-23025-4},
}


Entry last modified by Christine Kiesel, 04/22/2005
Show details for Edit History (please click the blue arrow to see the details)Edit History (please click the blue arrow to see the details)
Hide details for Edit History (please click the blue arrow to see the details)Edit History (please click the blue arrow to see the details)

Editor(s)
Maren Martens
Created
03/08/2005 01:13:47 PM
Revisions
3.
2.
1.
0.
Editor(s)
Christine Kiesel
Christine Kiesel
Christine Kiesel
Maren Martens
Edit Dates
22.04.2005 15:11:57
22.04.2005 15:10:40
22.04.2005 15:07:22
03/08/2005 01:13:47 PM
Show details for Attachment SectionAttachment Section
Hide details for Attachment SectionAttachment Section