Approximation Algorithms for the Bi-criteria Weighted max-cut Problem.
Eric AngelEvripidis BampisLaurent GourvèsPublished in: WG (2005)
Keyphrases
- approximation algorithms
- bicriteria
- np hard
- efficient solutions
- knapsack problem
- vertex cover
- special case
- integer linear programming
- minimum cost
- completion times
- worst case
- flowshop
- primal dual
- scheduling problem
- optimal solution
- shortest path problem
- precedence constraints
- constant factor
- approximation ratio
- randomized algorithms
- single machine
- weighted graph
- undirected graph
- shortest path
- upper bound
- lower bound