Titel: Rigorous results in combinatorial optimization
Sprache: English
Autor/Autorin: Jansson, Christian 
Schlagwörter: Combinatorial Optimization;Semidefinite Programming;illposed problems;branch-and-bound;interval arithmetic
Erscheinungsdatum: 2006
Quellenangabe: Algebraic and Numerical Algorithms and Computer-assisted Proofs. Dagstuhl, 2006 (Dagstuhl Seminar Proceedings ; 05391) ; http://drops.dagstuhl.de/opus/volltexte/2006/446/
Zusammenfassung (englisch): 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.
URI: http://tubdok.tub.tuhh.de/handle/11420/205
DOI: 10.15480/882.203
Institut: Zuverlässiges Rechnen E-19 
Dokumenttyp: InProceedings (Aufsatz / Paper einer Konferenz etc.)
Enthalten in den Sammlungen:Publications (tub.dok)

Dateien zu dieser Ressource:
Datei Beschreibung GrößeFormat
Jansson.paper1.pdf208,47 kBAdobe PDFMiniaturbild
Öffnen/Anzeigen
Zur Langanzeige

Seitenansichten

169
Letzte Woche
0
Letzten Monat
3
checked on 23.02.2019

Download(s)

47
checked on 23.02.2019

Google ScholarTM

Prüfe

Export

Alle Ressourcen in diesem Repository sind urheberrechtlich geschützt.