# Approximation Algorithms and Local Search for Ranking and Clustering

#### by Tom Coleman (Computer Science and Software Engineering Phd Completion)

Institution: The University of Melbourne
Date: Tue 2nd December 2008
Time: 11:00 AM
Location: Theatre 3, ICT Building, 111 Barry St, The Uni of Melbourne

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.