On the approximability of time disjoint walks

Alexandre Bayen; Jesse Goodman; Eugene Vinitsky

doi:10.1007/978-3-030-04651-4_5

On the approximability of time disjoint walks

Alexandre Bayen, Jesse Goodman, Eugene Vinitsky

Civil and Urban Engineering

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

Abstract

We introduce the combinatorial optimization problem Time Disjoint Walks. This problem takes as input a digraph G with positive integer arc lengths, and k pairs of vertices that each represent a trip demand from a source to a destination. The goal is to find a path and delay for each demand so that no two trips occupy the same vertex at the same time, and so that the sum of trip times is minimized. We show that even for DAGs with max degree Δ ≤ 3, Time Disjoint Walks is APXhard. We also present a natural approximation algorithm, and provide a tight analysis. In particular, we prove that it achieves an approximation ratio of Θ(k/log k) on bounded-degree DAGs, and Θ(k) on DAGs and bounded-degree digraphs.

Original language	English (US)
Title of host publication	Combinatorial Optimization and Applications - 12th International Conference, COCOA 2018, Proceedings
Editors	Alexander Zelikovsky, Donghyun Kim, R.N. Uma
Publisher	Springer Verlag
Pages	62-78
Number of pages	17
ISBN (Print)	9783030046507
DOIs	https://doi.org/10.1007/978-3-030-04651-4_5
State	Published - 2018
Event	12th Annual International Conference on Combinatorial Optimization and Applications, COCOA 2018 - Atlanta , United States Duration: Dec 15 2018 → Dec 17 2018

Publication series

Name	Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume	11346 LNCS
ISSN (Print)	0302-9743
ISSN (Electronic)	1611-3349

Conference

Conference	12th Annual International Conference on Combinatorial Optimization and Applications, COCOA 2018
Country/Territory	United States
City	Atlanta
Period	12/15/18 → 12/17/18

Keywords

Approximation algorithms
Disjoint Paths problem
Hardness of approximation

ASJC Scopus subject areas

Theoretical Computer Science
General Computer Science

Access to Document

10.1007/978-3-030-04651-4_5

Cite this

Bayen, A., Goodman, J., & Vinitsky, E. (2018). On the approximability of time disjoint walks. In A. Zelikovsky, D. Kim, & R. N. Uma (Eds.), Combinatorial Optimization and Applications - 12th International Conference, COCOA 2018, Proceedings (pp. 62-78). (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 11346 LNCS). Springer Verlag. https://doi.org/10.1007/978-3-030-04651-4_5

On the approximability of time disjoint walks. / Bayen, Alexandre; Goodman, Jesse; Vinitsky, Eugene.
Combinatorial Optimization and Applications - 12th International Conference, COCOA 2018, Proceedings. ed. / Alexander Zelikovsky; Donghyun Kim; R.N. Uma. Springer Verlag, 2018. p. 62-78 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 11346 LNCS).

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

Bayen, A, Goodman, J & Vinitsky, E 2018, On the approximability of time disjoint walks. in A Zelikovsky, D Kim & RN Uma (eds), Combinatorial Optimization and Applications - 12th International Conference, COCOA 2018, Proceedings. Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), vol. 11346 LNCS, Springer Verlag, pp. 62-78, 12th Annual International Conference on Combinatorial Optimization and Applications, COCOA 2018, Atlanta , United States, 12/15/18. https://doi.org/10.1007/978-3-030-04651-4_5

Bayen A, Goodman J, Vinitsky E. On the approximability of time disjoint walks. In Zelikovsky A, Kim D, Uma RN, editors, Combinatorial Optimization and Applications - 12th International Conference, COCOA 2018, Proceedings. Springer Verlag. 2018. p. 62-78. (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)). doi: 10.1007/978-3-030-04651-4_5

Bayen, Alexandre ; Goodman, Jesse ; Vinitsky, Eugene. / On the approximability of time disjoint walks. Combinatorial Optimization and Applications - 12th International Conference, COCOA 2018, Proceedings. editor / Alexander Zelikovsky ; Donghyun Kim ; R.N. Uma. Springer Verlag, 2018. pp. 62-78 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)).

@inproceedings{97bf2204a93c4ec6a96decc764e11028,

title = "On the approximability of time disjoint walks",

abstract = "We introduce the combinatorial optimization problem Time Disjoint Walks. This problem takes as input a digraph G with positive integer arc lengths, and k pairs of vertices that each represent a trip demand from a source to a destination. The goal is to find a path and delay for each demand so that no two trips occupy the same vertex at the same time, and so that the sum of trip times is minimized. We show that even for DAGs with max degree Δ ≤ 3, Time Disjoint Walks is APXhard. We also present a natural approximation algorithm, and provide a tight analysis. In particular, we prove that it achieves an approximation ratio of Θ(k/log k) on bounded-degree DAGs, and Θ(k) on DAGs and bounded-degree digraphs.",

keywords = "Approximation algorithms, Disjoint Paths problem, Hardness of approximation",

author = "Alexandre Bayen and Jesse Goodman and Eugene Vinitsky",

note = "Publisher Copyright: {\textcopyright} 2018, Springer Nature Switzerland AG.; 12th Annual International Conference on Combinatorial Optimization and Applications, COCOA 2018 ; Conference date: 15-12-2018 Through 17-12-2018",

year = "2018",

doi = "10.1007/978-3-030-04651-4_5",

language = "English (US)",

isbn = "9783030046507",

series = "Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)",

publisher = "Springer Verlag",

pages = "62--78",

editor = "Alexander Zelikovsky and Donghyun Kim and R.N. Uma",

booktitle = "Combinatorial Optimization and Applications - 12th International Conference, COCOA 2018, Proceedings",

}

TY - GEN

T1 - On the approximability of time disjoint walks

AU - Bayen, Alexandre

AU - Goodman, Jesse

AU - Vinitsky, Eugene

PY - 2018

Y1 - 2018

N2 - We introduce the combinatorial optimization problem Time Disjoint Walks. This problem takes as input a digraph G with positive integer arc lengths, and k pairs of vertices that each represent a trip demand from a source to a destination. The goal is to find a path and delay for each demand so that no two trips occupy the same vertex at the same time, and so that the sum of trip times is minimized. We show that even for DAGs with max degree Δ ≤ 3, Time Disjoint Walks is APXhard. We also present a natural approximation algorithm, and provide a tight analysis. In particular, we prove that it achieves an approximation ratio of Θ(k/log k) on bounded-degree DAGs, and Θ(k) on DAGs and bounded-degree digraphs.

AB - We introduce the combinatorial optimization problem Time Disjoint Walks. This problem takes as input a digraph G with positive integer arc lengths, and k pairs of vertices that each represent a trip demand from a source to a destination. The goal is to find a path and delay for each demand so that no two trips occupy the same vertex at the same time, and so that the sum of trip times is minimized. We show that even for DAGs with max degree Δ ≤ 3, Time Disjoint Walks is APXhard. We also present a natural approximation algorithm, and provide a tight analysis. In particular, we prove that it achieves an approximation ratio of Θ(k/log k) on bounded-degree DAGs, and Θ(k) on DAGs and bounded-degree digraphs.

KW - Approximation algorithms

KW - Disjoint Paths problem

KW - Hardness of approximation

UR - http://www.scopus.com/inward/record.url?scp=85058529059&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=85058529059&partnerID=8YFLogxK

U2 - 10.1007/978-3-030-04651-4_5

DO - 10.1007/978-3-030-04651-4_5

M3 - Conference contribution

AN - SCOPUS:85058529059

SN - 9783030046507

T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)

SP - 62

EP - 78

BT - Combinatorial Optimization and Applications - 12th International Conference, COCOA 2018, Proceedings

A2 - Zelikovsky, Alexander

A2 - Kim, Donghyun

A2 - Uma, R.N.

PB - Springer Verlag

T2 - 12th Annual International Conference on Combinatorial Optimization and Applications, COCOA 2018

Y2 - 15 December 2018 through 17 December 2018

ER -

On the approximability of time disjoint walks

Abstract

Publication series

Conference

Keywords

ASJC Scopus subject areas

Access to Document

Other files and links

Fingerprint

Cite this