IMPRS Publications: Thesis

Thesis - Masters thesis
@MastersThesis
Diplomarbeit

Show entries of:

this year (2010) | last year (2009) | two years ago (2008) | Notes URL

Action:

Options:

Goto entry point

Author

Author(s)*:	Kaligossi, Kanela
BibTeX citekey*:	Kaligossi2003
Language:	English

Title, School

Title*:	Length Bounded Network Flows
School*:	Universität des Saarlandes
Type of Thesis*:	Masters thesis
Month:	October
Year*:	2003
Pages:

Publisher

Publishers Name:
Publishers Address:

Note, Abstract, ©

Note:
LaTeX Abstract:	In this work we consider "length bounded" network flow problems which are problems with the requirement that the flows, resulting as solutions, can be decomposed into flow paths of bounded length. For the fractional case we study de "maximum T-length bounded flow problem", for which we show that is an NP-hard and we describe how to approximate it with an FPTAS. For the unsplittable case, we consider the "single source length bounded unsplittable flow problem". Given a graph and a set of commodities with associated demands that share a single source, we consider the problem of routing the demand of each commoditiy on a single path of bounded length. We obtain an effcient algorithm for computing an unsplittable flow whose average weighted path length is bounded by (1+€) To and whose congestion is at most 3 times the congestion of an optimal To-length bounded unsplittable flow, where To is the given bound on the path lengths. We show that at least max {} of the total demand can be routed unsplittably on paths of length within (1+d) times the path length bound of a feasible fractional flow. Moreover, we give an (8 [log_1+dk]+1)-approximation nalgorithm for the problem of finding the minimum number of rounds needed to toute the whole demand on paths of length within (1+d) times the path lengt bound of a feasible fractional flow. Finally we applied the ranomized rounding technique on the unsplittable length bounded flow problem, which yields a congestion of 2 with high probability, when the capaccities have value W(ln m)
Keywords:
HyperLinks / References / URLs:
Personal Comments:
Download Access Level:	Public

Referee, Status

1. Referee:
2. Referee:
Supervisor:	Skutella, Martin
Status:	Completed
First Lecture Title:
Location of Lecture:
Date of the Kolloquium:	22 March 2010
Chair of the Kolloquium:

Correlation

MPG Unit:

MPG Subunit:
Audience:	Expert
Appearance:	MPII WWW Server, MPII FTP Server, MPG publications list, university publications list, working group publication list, Fachbeirat, VG Wort

BibTeX Entry:
@MASTERSTHESIS{Kaligossi2003,
AUTHOR = {Kaligossi, Kanela},
TITLE = {Length Bounded Network Flows},
SCHOOL = {Universit{\"a}t des Saarlandes},
YEAR = {2003},
MONTH = {October},
}

Entry last modified by Lourdes Lara-Tapia, 03/10/2006

Edit History (please click the blue arrow to see the details)

Attachment Section