Document Open Access Logo

Rigorous Results in Combinatorial Optimization

Author Christian Jansson



PDF
Thumbnail PDF

File

DagSemProc.05391.7.pdf
  • Filesize: 208 kB
  • 8 pages

Document Identifiers

Author Details

Christian Jansson

Cite AsGet BibTex

Christian Jansson. Rigorous Results in Combinatorial Optimization. In Algebraic and Numerical Algorithms and Computer-assisted Proofs. Dagstuhl Seminar Proceedings, Volume 5391, pp. 1-8, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2006)
https://doi.org/10.4230/DagSemProc.05391.7

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.
Keywords
  • Combinatorial Optimization
  • Semidefinite Programming
  • Ill-posed Problems
  • Verification Methods

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail