On the approximability of time disjoint walks

Alexandre Bayen, Jesse Goodman, Eugene Vinitsky

Research output: Chapter in Book/Report/Conference proceedingConference contribution


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 languageEnglish (US)
Title of host publicationCombinatorial Optimization and Applications - 12th International Conference, COCOA 2018, Proceedings
EditorsAlexander Zelikovsky, Donghyun Kim, R.N. Uma
PublisherSpringer Verlag
Number of pages17
ISBN (Print)9783030046507
StatePublished - 2018
Event12th Annual International Conference on Combinatorial Optimization and Applications, COCOA 2018 - Atlanta , United States
Duration: Dec 15 2018Dec 17 2018

Publication series

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


Conference12th Annual International Conference on Combinatorial Optimization and Applications, COCOA 2018
Country/TerritoryUnited States


  • Approximation algorithms
  • Disjoint Paths problem
  • Hardness of approximation

ASJC Scopus subject areas

  • Theoretical Computer Science
  • General Computer Science


Dive into the research topics of 'On the approximability of time disjoint walks'. Together they form a unique fingerprint.

Cite this