Fast and simple approximation algorithms for maximum weighted independent set of links.

Peng-Jun Wan Xiaohua Jia Guojun Dai Hongwei Du Ophir Frieder

Published in: INFOCOM (2014)

Keyphrases

approximation algorithms
independent set
np hard
worst case
special case
vertex cover
minimum cost
maximum weight
facility location problem
set cover
randomized algorithms
approximation schemes
open shop
primal dual
approximation guarantees
constant factor