Skip to main content
Disciplines
Automotive Business IT + Informatics Construction + Real Estate Electrical Engineering + Electronics Energy + Sustainability Insurance + Risk Finance + Banking Management + Leadership Marketing + Sales Mechanical Engineering + Materials
Events
DE
EN
Books
Journals
Topic Page
Marketing
Start single access now
Access for companies
EXTENDED SEARCH
Log in
Top
Published in:
Approximation Algorithms for k-Connected Graph Factors Read chapter Read first chapter

2015 | OriginalPaper | Chapter

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

Authors : Fabrizio Grandoni, Salvatore Ingala, Sumedha Uniyal

Published in: Approximation and Online Algorithms

Publisher: Springer International Publishing

Log in

Activate our intelligent search to find suitable subject content or patents.

search-config
loading …

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 subset 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:
\(\bullet \) 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].
\(\bullet \) 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].
\(\bullet \) 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].

Dont have a licence yet? Then find out more about our products and how to get one now:

Springer Professional "Wirtschaft+Technik"

Online-Abonnement

Mit Springer Professional "Wirtschaft+Technik" erhalten Sie Zugriff auf:

  • über 102.000 Bücher
  • über 537 Zeitschriften

aus folgenden Fachgebieten:

  • Automobil + Motoren
  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Elektrotechnik + Elektronik
  • Energie + Nachhaltigkeit
  • Finance + Banking
  • Management + Führung
  • Marketing + Vertrieb
  • Maschinenbau + Werkstoffe
  • Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

inform now

Springer Professional "Technik"

Online-Abonnement

Mit Springer Professional "Technik" erhalten Sie Zugriff auf:

  • über 67.000 Bücher
  • über 390 Zeitschriften

aus folgenden Fachgebieten:

  • Automobil + Motoren
  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Elektrotechnik + Elektronik
  • Energie + Nachhaltigkeit
  • Maschinenbau + Werkstoffe




 

Jetzt Wissensvorsprung sichern!

inform now

Springer Professional "Wirtschaft"

Online-Abonnement

Mit Springer Professional "Wirtschaft" erhalten Sie Zugriff auf:

  • über 67.000 Bücher
  • über 340 Zeitschriften

aus folgenden Fachgebieten:

  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Finance + Banking
  • Management + Führung
  • Marketing + Vertrieb
  • Versicherung + Risiko




Jetzt Wissensvorsprung sichern!

inform now
previous chapter Approximation Algorithms for k-Connected Graph Factors
next chapter Maximum ATSP with Weights Zero and One via Half-Edges
Footnotes
1
Unless differently stated, \(\varepsilon \) denotes an arbitrarily small positive constant parameter. Where needed, we also assume that \(1/\varepsilon \) is integral and sufficiently large.
 
2
By non-extended we mean that it contains only decision variables for tasks. In the same paper the authors present an extended formulation with O(1) integrality gap.
 
3
The same gap is proved by Chekuri et al. [12]. The authors claim a \(O(\log ^2 n)\) gap, and then refine it to \(O(\log n)\) in an unpublished manuscript.
 
4
We recall that a Quasi-Polynomial-Time Approximation Scheme (QPTAS) is an algorithm that, given a constant parameter \(\varepsilon >0\), computes a \(1+\varepsilon \) approximation in Quasi-Polynomial Time (QPT), i.e. in time \(2^{poly\log (s)}\) where s is the input size.
 
5
We remark that Batra et al. [7] recently managed to remove this assumption on the demands for UFP. Their approach does not seem to be compatible with our randomized dissection technique (at least not trivially).
 
6
Throughout this paper, by guessing we mean trying all the possibilities.
 
7
In the guessing we of course guarantee that \(r^*=\sum _{f,a,b}r^{f,a,b}\).
 
8
Here we exploit a property of twUFP not satisfied by bagUFP.
 
9
Intuitively, the first term in the outer max corresponds to the case that the best solution does not use job k, and the second term to the weight obtained by including some task \(i\in \mathcal{B}_k\) in the solution.
 
10
We call good the jobs of level \(\ell \) by definition.
 
11
For our goals, it is convenient to consider two rectangles as overlapping iff they overlap on a positive value area. In particular, overlapping on rectangle boundaries is allowed.
 
12
Observe that, by construction, \(APX_{max}\) is a maximal independent set w.r.t \(\mathcal{R}'\). This might not be the case w.r.t. \(\mathcal{R}\) since bag constraints might prevent some non-overlapping rectangle to be included in the maximal solution.
 
Literature
1.
Anagnostopoulos, A., Grandoni, F., Leonardi, S., Wiese, A.: Constant integrality gap LP formulations of unsplittable flow on a path. In: Goemans, M., Correa, J. (eds.) IPCO 2013. LNCS, vol. 7801, pp. 25–36. Springer, Heidelberg (2013)CrossRef
2.
Anagnostopoulos, A., Grandoni, F., Leonardi, S., Wiese, A.: A mazing 2+\(\varepsilon \) approximation for unsplittable flow on a path. In: SODA, pp. 26–41 (2014)
3.
4.
Bansal, N., Chakrabarti, A. Epstein,, A., Schieber, B.: A quasi-PTAS for unsplittable flow on line graphs. In: STOC, pp. 721–729 (2006)
5.
Bansal, N., Friggstad, Z., Khandekar, R., Salavatipour, R.: A logarithmic approximation for unsplittable flow on line graphs. In: SODA, pp. 702–709 (2009)
6.
Bar-Noy, A., Guha, S., Naor, J., Schieber, B.: Approximating the throughput of multiple machines in real-time scheduling. SIAM J. Comput. 31(2), 331–352 (2001)MATHMathSciNetCrossRef
7.
Batra, J., Garg, N., Kumar, A., Mömke, T., Wiese, A.: New approximation schemes for unsplittable flow on a path. In: SODA, pp. 47–58 (2015)
8.
Bonsma, P., Schulz, J., Wiese, A.: A constant factor approximation algorithm for unsplittable flow on paths. In: FOCS, pp. 47–56 (2011)
9.
Calinescu, G., Chakrabarti, A., Karloff, H., Rabani, Y.: Improved approximation algorithms for resource allocation. In: Cook, W.J., Schulz, A.S. (eds.) IPCO 2002. LNCS, vol. 2337, pp. 401–414. Springer, Heidelberg (2002)CrossRef
10.
Chakaravarthy, V.T., Choudhury, A.R., Gupta, S., Roy, S., Sabharwal, Y.: Improved algorithms for resource allocation under varying capacity. In: Schulz, A.S., Wagner, D. (eds.) ESA 2014. LNCS, vol. 8737, pp. 222–234. Springer, Heidelberg (2014)
11.
Chan, T.M., Har-Peled, S.: Approximation algorithms for maximum independent set of pseudo-disks. Discrete Comput. Geom. 48(2), 373–392 (2012)MATHMathSciNetCrossRef
12.
Chekuri, C., Ene, A., Korula, N.: Unsplittable flow in paths and trees and column-restricted packing integer programs. In: Dinur, I., Jansen, K., Naor, J., Rolim, J. (eds.) Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques. LNCS, vol. 5687, pp. 42–55. Springer, Heidelberg (2009)CrossRef
13.
Chekuri, C., Mydlarz, M., Shepherd, F.: Multicommodity demand flow in a tree and packing integer programs. ACM Trans. Algorithms 3, 27 (2007)MathSciNetCrossRef
14.
15.
Grandoni, F., Rothvoß, T.: Pricing on paths: a PTAS for the highway problem. In: SODA, pp. 675–684 (2011)
16.
Metadata
Title
Improved Approximation Algorithms for Unsplittable Flow on a Path with Time Windows
Authors
Fabrizio Grandoni
Salvatore Ingala
Sumedha Uniyal
Copyright Year
2015
Book
Approximation and Online Algorithms

Print ISBN: 978-3-319-28683-9

Electronic ISBN: 978-3-319-28684-6

Copyright Year: 2015

DOI
https://doi.org/10.1007/978-3-319-28684-6_2

Premium Partner

    Image Credits