Approximation Algorithms for the Bi-criteria Weighted max-cut Problem.

Eric Angel Evripidis Bampis Laurent Gourvès

Published 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