Weighted capacitated, priority, and geometric set cover via improved quasi-uniform sampling.

Timothy M. Chan Elyot Grant Jochen Könemann Malcolm Sharpe

Published in: SODA (2012)

Keyphrases

set cover
np hard
uniform sampling
greedy algorithm
approximation algorithms
computational geometry
network flow
greedy heuristic
geometric structure
knapsack problem
solution space
primal dual
lower bound
special case
convex hull
high dimensional
data mining
integer programming
voronoi diagram
image processing