An Approximation Perspective on Algorithms
Recorded 06 October 2014 in Lausanne, Vaud, Switzerland
Event: IC Colloquia - EPFL IC School Colloquia
Faced with hard optimization problems where polynomial time exact algorithms are unlikely to be found, theoretical computer scientists have focussed on the development of efficient heuristics with provable guarantees. This pursuit of such approximation algorithms has led to a rich body of tools and techniques. In this talk, I will argue that this approximation perspective is a useful way to approach algorithm design and the resulting ideas are more broadly applicable beyond the field of approximation. I will illustrate this thesis via a few vignettes drawn from my own work on compact data representation, network design, information aggregation and tensor decomposition.
Watched 453 times.Watch