Optimal Approximation Algorithms for Maximum Distance-Bounded Subgraph Problems.
Yuichi AsahiroYuya DoiEiji MiyanoKazuaki SamizoHirotaka ShimizuPublished in: Algorithmica (2018)
Keyphrases
- approximation algorithms
- vertex cover
- np hard
- maximum distance
- worst case
- approximation schemes
- np hardness
- minimum cost
- randomized algorithms
- constant factor
- optimal solution
- primal dual
- special case
- network design problem
- linear programming
- decision trees
- precedence constraints
- disjoint paths
- branch and bound algorithm
- practical problems
- linear program
- approximation ratio
- np complete
- approximation guarantees
- optimization problems
- dynamic programming