We study the unsplittable flow on a path problem (UFP), which arises naturally in many applications such as bandwidth allocation, job scheduling, and caching. Here we are given a path with non-negative edge capacities and a set of tasks, which are characterized by a subpath, a demand, and a profit. The goal is to find the most profitable subset of tasks whose total demand does not violate the edge capacities. Not surprisingly, this problem has received a lot of attention in the research community. If the demand of each task is at most a small enough fraction δ of the capacity along its subpath (δ-small tasks), then it has been known for a long time [Chekuri et al., ICALP 2003] how to compute a solution of value arbitrarily close to the optimum via LP rounding. However, much remains unknown for the complementary case, that is, when the demand of each task is at least some fraction δ>0 of the smallest capacity of its subpath (δ-large tasks). For this setting a constant factor approximat

A Mazing 2+eps Approximation Algorithm for Unsplittable Flow on a Path / Anagnostopoulos, Aristidis; Fabrizio, Grandoni; Leonardi, Stefano; Andreas, Wiese. - STAMPA. - (2014), pp. 26-41. (Intervento presentato al convegno 25th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA 2014) tenutosi a Portland, Oregon, USA) [10.1137/1.9781611973402.3].

A Mazing 2+eps Approximation Algorithm for Unsplittable Flow on a Path

ANAGNOSTOPOULOS, ARISTIDIS;LEONARDI, Stefano;
2014

Abstract

We study the unsplittable flow on a path problem (UFP), which arises naturally in many applications such as bandwidth allocation, job scheduling, and caching. Here we are given a path with non-negative edge capacities and a set of tasks, which are characterized by a subpath, a demand, and a profit. The goal is to find the most profitable subset of tasks whose total demand does not violate the edge capacities. Not surprisingly, this problem has received a lot of attention in the research community. If the demand of each task is at most a small enough fraction δ of the capacity along its subpath (δ-small tasks), then it has been known for a long time [Chekuri et al., ICALP 2003] how to compute a solution of value arbitrarily close to the optimum via LP rounding. However, much remains unknown for the complementary case, that is, when the demand of each task is at least some fraction δ>0 of the smallest capacity of its subpath (δ-large tasks). For this setting a constant factor approximat
2014
25th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA 2014)
04 Pubblicazione in atti di convegno::04b Atto di convegno in volume
A Mazing 2+eps Approximation Algorithm for Unsplittable Flow on a Path / Anagnostopoulos, Aristidis; Fabrizio, Grandoni; Leonardi, Stefano; Andreas, Wiese. - STAMPA. - (2014), pp. 26-41. (Intervento presentato al convegno 25th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA 2014) tenutosi a Portland, Oregon, USA) [10.1137/1.9781611973402.3].
File allegati a questo prodotto
File Dimensione Formato  
VE_2014_11573-556164.pdf

solo gestori archivio

Tipologia: Versione editoriale (versione pubblicata con il layout dell'editore)
Licenza: Tutti i diritti riservati (All rights reserved)
Dimensione 655.35 kB
Formato Adobe PDF
655.35 kB Adobe PDF   Contatta l'autore

I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.

Utilizza questo identificativo per citare o creare un link a questo documento: https://hdl.handle.net/11573/556164
 Attenzione

Attenzione! I dati visualizzati non sono stati sottoposti a validazione da parte dell'ateneo

Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus 39
  • ???jsp.display-item.citation.isi??? ND
social impact