Tomas Werner presents Linear Programming Approach to Discrete Energy Minimization (Habilitation Defense)
On 2016-01-27 13:00:00 at T2: D3-209, Karlovo náměstí 13, Praha 2
Come to my habilitation defense!
In my habilitation lecture I will define the problem of discrete energy
minimization and then summarize my contributions to one successful approach to
this NP-hard problem, linear programming (LP) relaxation.
My first contribution is a revisit of an old and not widely known approach by
Schlesinger et al., which was independently rediscovered recently and is a basis
of the LP relaxation approach. My second contribution is an elegant
generalization of this approach, which enables handling energy terms of
arbitrary arity, constructing a hierarchy of progressively tighter relaxations,
and incrementally tightening the relaxation in a cutting plane fashion. My third
contribution (with Daniel Prusa) is to show that trying to find a very efficient
algorithm to solve the LP relaxation is hopeless because the general linear
programming problem can be reduced in linear time to this LP relaxation.
In my habilitation lecture I will define the problem of discrete energy
minimization and then summarize my contributions to one successful approach to
this NP-hard problem, linear programming (LP) relaxation.
My first contribution is a revisit of an old and not widely known approach by
Schlesinger et al., which was independently rediscovered recently and is a basis
of the LP relaxation approach. My second contribution is an elegant
generalization of this approach, which enables handling energy terms of
arbitrary arity, constructing a hierarchy of progressively tighter relaxations,
and incrementally tightening the relaxation in a cutting plane fashion. My third
contribution (with Daniel Prusa) is to show that trying to find a very efficient
algorithm to solve the LP relaxation is hopeless because the general linear
programming problem can be reduced in linear time to this LP relaxation.