Approximation Algorithms for the Minimum-Length Corridor and Related Problems.
Arturo Gonzalez-GutierrezTeofilo F. GonzalezPublished in: CCCG (2007)
Keyphrases
- related problems
- approximation algorithms
- minimum length
- np hard
- special case
- shortest path
- digital curves
- worst case
- minimum cost
- vertex cover
- open shop
- optimal solution
- primal dual
- set cover
- approximation ratio
- disjoint paths
- shortest path problem
- randomized algorithms
- constant factor
- linear programming
- constant factor approximation