Large moses

An Approximation Perspective on Algorithms

Moses Charikar

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 945 times.