Conflict-free coloring of points with respect to rectangles and approximation algorithms for discrete independent set.

Timothy M. Chan

Published in: SCG (2012)

Keyphrases

approximation algorithms
independent set
conflict free
np hard
special case
functional dependencies
vertex cover
minimum cost
worst case
randomized algorithms
maximum independent set
database schemes
approximation ratio
maximum weight
convex hull
constant factor
learning algorithm
databases
data points
lower bound