• Polski
  • English

Seminarium ZOK: Sumedha Uniyal i Bartosz Rybicki  

W dniu 8 września 2015 (wtorek, godz. 10:15-12:00, sala 310) na seminarium Zakładu Optymalizacji Kombinatorycznej wygłoszone zostaną dwie prezentacje:

Sumedha Uniyal (IDSIA, Szwajcaria) przedstawi wyniki z pracy z konferencji WAOA 2015 pt. Improved Approximation Algorithms for Unsplittable Flow on a Path with Time Windows autorów Fabrizio Grandoni, Salvatore Ingala, Sumedha Uniyal.

Bartosz Rybicki przedstawi wyniki z pracy z konferencji ESA 2015 pt. An Improved Approximation Algorithm for Knapsack Median using Sparsification autorów Jaroslaw Byrka, Thomas Pensyl, Bartosz Rybicki, Joachim Spoerhase, Aravind Srinivasan, Khoa Trinh.


Improved Approximation Algorithms for Unsplittable Flow on a Path with Time Windows

In the well-studied Unsplittable Flow on a Path problem (UFP), we are given a path graph with edge capacities. Furthermore, we are given a collection of n tasks, each one characterized by a subpath, a weight, and a demand. Our goal is to select a maximum weight sub- set of tasks so that the total demand of selected tasks using each edge is upper bounded by the corresponding capacity. Chakaravarthy et al. [ESA'14] studied a generalization of UFP, bagUFP, where tasks are partitioned into bags, and we can select at most one task per bag. Intuitively, bags model jobs that can be executed at different times (with different duration, weight, and demand). They gave a O(log n) approximation for bagUFP. This is also the best known ratio in the case of uniform weights. In this paper we achieve the following main results:

  • We present an LP-based O(log n/ log log n) approximation for bagUFP. We remark that, prior to our work, the best known integrality gap (for a non-extended formulation) was O(log n) even in the special case of UFP [Chekuri et al., APPROX'09].
  • We present an LP-based O(1) approximation for uniform-weight bagUFP. This also generalizes the integrality gap bound for uniform-weight UFP by Anagnostopoulos et al. [IPCO'13].
  • We consider a relevant special case of bagUFP, twUFP, where tasks in a bag model the possible ways in which we can schedule a job with a given processing time within a given time window. We present a QPTAS for twUFP with quasi-polynomial demands and under the Bounded Time- Window Assumption, i.e. assuming that the time window size of each job is within a constant factor from its processing time. This generalizes the QPTAS for UFP by Bansal et al. [STOC'06].
Instytut Informatyki
Uniwersytetu Wroclawskiego
ul. Joliot-Curie 15
50-383 Wroclaw
tel.: 71 375 7800
tel.: 71 325 1271
fax: 71 375 7801
tel.: 71 375 7892
sprawy studenckie:
tel.: 71 375 7958
Redaktor strony WWW