Combinatorial optimization

Wednesday, May 20, 2015 - 4:25pm - 5:15pm
Jinwoo Shin (Korea Advanced Institute of Science and Technology (KAIST))
Max-product belief propagation (BP) is a popular message-passing algorithm for computing a maximum-a-posteriori assignment in a graphical model. It has been shown that BP can solve a few classes of Linear Programming (LP) formulations to combinatorial optimization problems including maximum weight matching and shortest path. However, those LPs and corresponding BP analysis are very sensitive to underlying problem setups, and it has been not clear what extent these results can be generalized to.
Tuesday, November 18, 2008 - 9:00am - 10:00am
Franz Rendl (Universität Klagenfurt)
It has recently been shown that linear programs over the cone of
completely positive matrices give exact formulations for many
NP-hard combinatorial optimization problems. This motivates the
investigation of solution methods for such problems.
In this talk I will present a heuristic algorithm for this problem,
whos main effort in each iteration consists in solving a convex quadratic
problem in sign constrained variables.
The algorithm will be applied to random copositive programs
as well as to the copositive formulation of some
Subscribe to RSS - Combinatorial optimization