New approximation algorithms for routing with multiport terminals.
Christopher S. HelvigGabriel RobinsAlexander ZelikovskyPublished in: IEEE Trans. Comput. Aided Des. Integr. Circuits Syst. (2000)
Keyphrases
- approximation algorithms
- np hard
- special case
- vertex cover
- worst case
- approximation ratio
- minimum cost
- facility location problem
- routing protocol
- routing algorithm
- open shop
- primal dual
- network design problem
- routing problem
- exact algorithms
- np hardness
- upper bound
- precedence constraints
- set cover
- combinatorial auctions
- genetic algorithm
- constant factor
- randomized algorithms
- approximation schemes