Approximation algorithms for the two-center problem of convex polygon.
Sanjib SadhuSasanka RoySoumen NandiAnil MaheshwariSubhas C. NandyPublished in: CoRR (2015)
Keyphrases
- approximation algorithms
- convex hull
- minkowski sum
- np hard
- quadratic program
- special case
- minimum cost
- worst case
- vertex cover
- network design problem
- set cover
- approximation ratio
- facility location problem
- approximation schemes
- primal dual
- disjoint paths
- exact algorithms
- undirected graph
- np hardness
- convex optimization
- randomized algorithms
- open shop
- search algorithm
- convex sets
- optimal solution
- integrality gap