The checkpoint problem

DOI10.1016/J.TCS.2012.05.021zbMATH Open1252.68141OpenAlexW2002766600MaRDI QIDQ714790FDOQ714790

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

Publication date: 11 October 2012

Published in: Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.tcs.2012.05.021

Recommendations

• The checkpoint problem
• On the Complexity and Approximation of the Min-Sum and Min-Max Disjoint Paths Problems
• Approximation Algorithms for k-Hurdle Problems
• Complexity and approximation results for the min-sum and min-max disjoint paths problems
• Approximation algorithms for \(k\)-hurdle problems

zbMATH Keywords

checkpointapproximationcuts

Mathematics Subject Classification ID

Applications of graph theory (05C90) Graph algorithms (graph-theoretic aspects) (05C85) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)

Cites Work

• Approximation algorithms for NP-hard problems.
• Proof verification and the hardness of approximation problems
• The complexity of satisfiability problems
• Finding Paths and Cycles of Superpolylogarithmic Length
• On the hardness of approximating Multicut and Sparsest-Cut
• The Traveling Salesman Problem with Distances One and Two
• Title not available (Why is that?)
• Approximate Max-Flow Min-(Multi)Cut Theorems and Their Applications
• The hardness of approximate optima in lattices, codes, and systems of linear equations
• On paths avoding forbidden pairs of vertices in a graph
• On the complexity of paths avoiding forbidden pairs
• Primal-dual approximation algorithms for integral flow and multicut in trees
• Approximating the k-multicut problem
• The importance of being biased
• Lagrangian relaxation and partial cover (Extended abstract)
• Approximating directed multicuts
• Polynomial flow-cut gaps and hardness of directed cut problems
• Improved approximation for directed cut problems
• Title not available (Why is that?)
• Greedy approximation algorithms for directed multicuts
• Impossible pair constrained test path generation in a program
• Partial multicuts in trees
• Combination Can Be Hard: Approximability of the Unique Coverage Problem
• Title not available (Why is that?)
• On the hardness of approximating spanners
• Computing and Combinatorics

Cited In (4)

• On the minimum routing cost clustered tree problem
• \((k-2)\)-linear connected components in hypergraphs of rank \(k\)
• Evader interdiction: algorithms, complexity and collateral damage
• The checkpoint problem

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 Q714790)