Title of presentation:
Semidefinite Relaxations for Hard Combinatorial Problems
Invited talk at
EURO XVII conference.
The Conference will take place in the main building of the Budapest
Economic Sciences and Public Administration (H-1093 Budapest, Fovam ter
8.) facing the wonderful Danube and Gellert Hill;
and plenary talk at 2nd Workshop on Interior Point Methods, IPM 2000, Budapest, July 14-15, 2000. The IPM 2000 workshop is an integrated part of the EURO XVII conference. Venue of the workshop is Budapest University of Economic Sciences Budapest, Fuvam tir 8.
The main building of the university is situated on the left bank of river Danube just next to Szabadsag Bridge in the middle of the city. It is accesible by tram No 2, No 47, No 49 and by bus No 15. A photo of the main buiding taken from across the river.
(The Abstract (text file):; the presentation (ps file))
This talk is based on several papers; principally, on the papers
dealing with the strength of Lagrangian Relaxations:
A RECIPE FOR BEST SEMIDEFINITE RELAXATION FOR (0,1)-QUADRATIC PROGRAMMING
and the two papers:
On Lagrangian Relaxation of Quadratic Matrix Constraints and
Strong Duality for a Trust-Region Type Relaxation of the Quadratic Assignment Problem
A summary of these results is presented in
Semidefinite and Lagrangian Relaxations for Hard Combinatorial Problems (in Proceedings of 19th IFIP TC7 CONFERENCE ON Semidefinite Programming), Kluwer Academic, 2000.