Please use this identifier to cite or link to this item:
Fulltext available Open Access
Title: Rigorous results in combinatorial optimization
Language: English
Authors: Jansson, Christian 
Keywords: Combinatorial Optimization;Semidefinite Programming;illposed problems;branch-and-bound;interval arithmetic
Issue Date: 2006
Source: Algebraic and Numerical Algorithms and Computer-assisted Proofs. Dagstuhl, 2006 (Dagstuhl Seminar Proceedings ; 05391) ;
Abstract (english): 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 illconditioned or ill-posed, and if Slater’s constraint qualifications fail. We show how verified results can be obtained by rigorously bounding the optimal value of nonlinear semidefinite relaxations, even in the ill-posed case. All rounding errors due to floating point arithmetic are taken into account.
DOI: 10.15480/882.203
Institute: Zuverlässiges Rechnen E-19 
Type: InProceedings (Aufsatz / Paper einer Konferenz etc.)
License: In Copyright In Copyright
Appears in Collections:Publications with fulltext

Files in This Item:
File Description SizeFormat
Jansson.paper1.pdf208,47 kBAdobe PDFThumbnail
Show full item record

Page view(s)

Last Week
Last month
checked on Sep 23, 2020


checked on Sep 23, 2020

Google ScholarTM


Note about this record


Items in TORE are protected by copyright, with all rights reserved, unless otherwise indicated.