Menu

Sept. 8, 2015, 10:15 a.m.

Tuesday 10:15-12:00, room 310.

Abstract. 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 par- titioned into bags, and we can select at most one task per bag. Intuitively, bags model jobs that can be executed at di􏰱erent times (with diff􏰱erent 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].

This is a joint work wirh Fabrizio Grandoni and Salvatore Ingala published at WAOA 2015.