Fast Algorithms via Convex Relaxation

Опубликовано 9 марта 2018, 19:32

In Theoretical CS many of the fastest algorithms are obtained by considering the Linear Programming (LP) relaxation of the problem. In this talk, I will survey several results on the effectiveness of employing the more general *convex* relaxation. We discovered that for a host of classical problems, their convex relaxation is often a more natural starting point to design fast algorithms. Examples include submodular minimization, market equilibrium computation and approximate Caratheodory. Our journey will involve some fun interplay of convex optimization with tools from discrete optimization and economics.

See more at microsoft.com/en-us/research/v...