The checkpoint problem

DOI10.1007/978-3-642-15369-3_17zbMATH Open1306.90128OpenAlexW2139785710MaRDI QIDQ3588409FDOQ3588409

Authors: Rohit Khandekar, Julián Mestre, Mohammad T. Hajiaghayi, Guy Kortsarz 

Publication date: 10 September 2010

Published in: Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/978-3-642-15369-3_17

Recommendations

• The checkpoint problem
• On the Complexity and Approximation of the Min-Sum and Min-Max Disjoint Paths Problems
• Complexity and approximation results for the min-sum and min-max disjoint paths problems
• Approximation algorithms and hardness of the \(k\)-route cut problem
• Near-optimal hardness results and approximation algorithms for edge-disjoint paths and related problems

Mathematics Subject Classification ID

Programming involving graphs or networks (90C35) Combinatorial optimization (90C27) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Approximation algorithms (68W25)

Cited In (3)

• On the path avoiding forbidden pairs polytope
• The checkpoint problem
• Complexity of the path avoiding forbidden pairs problem revisited

This page was built for publication: The checkpoint problem

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3588409)