Linear Programming-based Approximation Algorithms for Multi-Vehicle Minimum Latency Problems (Extended Abstract).
Ian PostChaitanya SwamyPublished in: SODA (2015)
Keyphrases
- extended abstract
- approximation algorithms
- linear programming
- vertex cover
- np hard
- minimum cost
- np hardness
- special case
- primal dual
- approximation schemes
- exact algorithms
- optimization problems
- linear program
- worst case
- mathematical programming
- network design problem
- quadratic program
- constant factor
- precedence constraints
- dynamic programming
- lower bound
- quadratic programming