The maximum congested cut problem and its robust counterpart: Exact and approximation algorithms for the single and the multicommodity case.
Maria Grazia ScutellàPublished in: Networks (2008)
Keyphrases
- approximation algorithms
- network design problem
- np hard
- integrality gap
- special case
- vertex cover
- worst case
- primal dual
- approximation guarantees
- linear program
- randomized algorithms
- minimum cost
- network design
- precedence constraints
- approximation ratio
- constant factor
- disjoint paths
- combinatorial auctions
- learning algorithm
- lower bound
- search algorithm
- open shop
- optimal solution