License
when quoting this document, please refer to the following
URN: urn:nbn:de:0030-drops-4467
URL: http://drops.dagstuhl.de/opus/volltexte/2006/446/

Jansson, Christian

Rigorous Results in Combinatorial Optimization

pdf-format:
Dokument 1.pdf (208 KB)


Abstract

Many current deterministic solvers for NP-hard combinatorial optimization problems are based on nonlinear relaxation techniques that use floating point arithmetic. Occasionally, due to solving these relaxations, rounding errors may produce erroneous results, although the deterministic algorithm should compute the exact solution in a finite number of steps. This may occur especially if the relaxations are ill-conditioned or ill-posed, and if Slater's constraint qualifications fail. We show how exact solutions can be obtained by rigorously bounding the optimal value of semidefinite relaxations, even in the ill-posed case. All rounding errors due to floating point arithmetic are taken into account.

BibTeX - Entry

@InProceedings{jansson:DSP:2006:446,
  author =	{Christian Jansson},
  title =	{Rigorous Results in Combinatorial Optimization},
  booktitle =	{Algebraic and Numerical Algorithms and Computer-assisted Proofs},
  year =	{2006},
  editor =	{Bruno Buchberger and Shin'ichi Oishi and Michael Plum and Sigfried M. Rump},
  number =	{05391},
  series =	{Dagstuhl Seminar Proceedings},
  ISSN =	{1862-4405},
  publisher =	{Internationales Begegnungs- und Forschungszentrum f{\"u}r Informatik (IBFI), Schloss Dagstuhl, Germany},
  address =	{Dagstuhl, Germany},
  URL =		{http://drops.dagstuhl.de/opus/volltexte/2006/446},
  annote =	{Keywords: Combinatorial Optimization, Semidefinite Programming, Ill-posed Problems,  Verification Methods}
}

Keywords: Combinatorial Optimization, Semidefinite Programming, Ill-posed Problems, Verification Methods
Seminar: 05391 - Algebraic and Numerical Algorithms and Computer-assisted Proofs
Issue date: 2006
Date of publication: 31.01.2006


DROPS-Home | Fulltext Search | Imprint Published by LZI