Jansson, Christian
Rigorous Results in Combinatorial Optimization
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: |
|
2006 |
2006
