Approximation Algorithms and Local Search for Ranking and Clustering
by Tom Coleman
Abstract: Ranking and clustering are two fundamental and widely-applicable
classes of data analysis problem.
Many of the interesting problems are provably infeasible to solve
optimally. We consider both theoretical, approximation preserving, and
practical, heuristic, approaches to finding near-optimal solutions.
Additionally, we study the intersection of these approaches.
Which approximation algorithms are efficient in practice,
and which effective heuristics admit approximation algorithms?
Local search approaches are often the most practical;
given an appropriate starting solution,
they sometimes provide provable approximation factors.
For More Information: Tony Guttmann T.Guttmann@ms.unimelb.edu.au