Campuses:

Copositive programming and combinatorial optimization

Tuesday, November 18, 2008 - 9:00am - 10:00am
EE/CS 3-180
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
NP-hard graph optimization problems.

(joint work with M. Bomze (Vienna) and F. Jarre (Duesseldorf))
MSC Code: 
90C27