Improved Bounds for the Unsplittable Flow Problem

Result code in IS VaVaI
<a href="https://www.isvavai.cz/riv?ss=detail&h=RIV%2F00216208%3A11320%2F06%3A00002854" target="_blank" >RIV/00216208:11320/06:00002854 - isvavai.cz</a>
Result on the web
—
DOI - Digital Object Identifier
—

Result language
angličtina
Original language name
Improved Bounds for the Unsplittable Flow Problem
Original language description
In this paper we consider the unsplittable flow problem (UFP): given a network $G=(V,E)$ with edge capacities and a set of terminal pairs (or requests) with associated demands, find a subset of the pairs of maximum total demand for which a single flow path can be chosen for each pair so that for every edge, the sum of the demands of the paths crossing the edge does not exceed its capacity. We present a collection of new results for the UFP both in the offline and the online setting. A fundamental ingredient of our analysis is the introduction of a new graph parameter, the flow number, that aims to capture global communication properties of the network. With the help of the flow number we develop a general method for transforming arbitrary multicommodity flow solutions into solutions that use short paths only. This generalizes a well-known theorem of Leighton and Rao that applies to uniform flows only. Both the parameter and the method may therefore be of independent interest.
Czech name
Vylepšené odhady pro problém nedělitelného toku
Czech description
Uvažujeme problém nedělitelného toku a předkládáme řadu nových výsledků. Podstatnou složkou analýzy algoritmů je zavedení nového grafového parametru, tzv. tokové číslo, které se snaží postihnout lokální i globální komunikační vlastnosti grafu.

Type
J<sub>x</sub> - Unclassified - Peer-reviewed scientific article (Jimp, Jsc and Jost)
CEP classification
BA - General mathematics
OECD FORD branch
—

Project
<a href="/en/project/1M0545" target="_blank" >1M0545: Institute for Theoretical Computer Science</a><br>
Continuities
P - Projekt vyzkumu a vyvoje financovany z verejnych zdroju (s odkazem do CEP)<br>Z - Vyzkumny zamer (s odkazem do CEZ)

Publication year
2006
Confidentiality
S - Úplné a pravdivé údaje o projektu nepodléhají ochraně podle zvláštních právních předpisů

Similar results(10)