Approximation algorithms for orienting mixed graphs.
Michael ElberfeldDanny SegevColin R. DavidsonDana SilverbushRoded SharanPublished in: Theor. Comput. Sci. (2013)
Keyphrases
- approximation algorithms
- undirected graph
- np hard
- vertex cover
- special case
- worst case
- approximation guarantees
- network design problem
- minimum cost
- facility location problem
- approximation ratio
- open shop
- graph matching
- constant factor
- primal dual
- np hardness
- constant factor approximation
- precedence constraints
- spanning tree
- graph structure
- approximation schemes
- combinatorial auctions
- graph model
- randomized algorithms
- lower bound
- bipartite graph
- graphical models