New Exact and Approximation Algorithms for the Star Packing Problem in Undirected Graphs.
Maxim A. BabenkoAlexey GusakovPublished in: STACS (2011)
Keyphrases
- approximation algorithms
- packing problem
- undirected graph
- np hard
- integer programming
- special case
- bin packing
- disjoint paths
- worst case
- minimum cost
- vertex cover
- randomized algorithms
- primal dual
- approximation ratio
- constant factor approximation
- exact inference
- constant factor
- lower bound
- optimal solution
- reinforcement learning