School Seminars and Colloquia

Approximation Algorithms and Local Search for Ranking and Clustering

Complex Systems Seminar

by Tom Coleman

Institution: The University of Melbourne CSSE Phd Completion
Date: Tue 2nd December 2008
Time: 11:00 AM
Location: Theater 3, ICT Building, 111 Barry Street, Carlton

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