Improved Primal-Dual Approximation Algorithm for the Connected Facility Location Problem.
Hyunwoo JungMohammad Khairul HasanKyung-Yong ChwaPublished in: COCOA (2008)
Keyphrases
- primal dual
- approximation algorithms
- facility location problem
- dominating set
- convergence rate
- linear programming
- np hard
- affine scaling
- simplex algorithm
- computational complexity
- probabilistic model
- objective function
- convex optimization
- worst case
- integrality gap
- graphical models
- interior point methods
- linear programming problems
- interior point algorithm
- algorithm for linear programming