TUHH Open Research
Help
  • Log In
    New user? Click here to register.Have you forgotten your password?
  • English
  • Deutsch
  • Communities & Collections
  • Publications
  • Research Data
  • People
  • Institutions
  • Projects
  • Statistics
  1. Home
  2. TUHH
  3. Publications
  4. Rigorous results in combinatorial optimization
 
Options

Rigorous results in combinatorial optimization

Citation Link: https://doi.org/10.15480/882.203
Publikationstyp
Conference Paper
Date Issued
2006
Sprache
English
Author(s)
Jansson, Christian  
Institut
Zuverlässiges Rechnen E-19  
TORE-DOI
10.15480/882.203
TORE-URI
http://tubdok.tub.tuhh.de/handle/11420/205
Citation
Algebraic and Numerical Algorithms and Computer-assisted Proofs. Dagstuhl, 2006 (Dagstuhl Seminar Proceedings ; 05391) ; http://drops.dagstuhl.de/opus/volltexte/2006/446/
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.
Subjects
Combinatorial Optimization
Semidefinite Programming
illposed problems
branch-and-bound
interval arithmetic
Lizenz
http://rightsstatements.org/vocab/InC/1.0/
Loading...
Thumbnail Image
Name

Jansson.paper1.pdf

Size

208.47 KB

Format

Adobe PDF

TUHH
Weiterführende Links
  • Contact
  • Send Feedback
  • Cookie settings
  • Privacy policy
  • Impress
DSpace Software

Built with DSpace-CRIS software - Extension maintained and optimized by 4Science
Design by effective webwork GmbH

  • Deutsche NationalbibliothekDeutsche Nationalbibliothek
  • ORCiD Member OrganizationORCiD Member Organization
  • DataCiteDataCite
  • Re3DataRe3Data
  • OpenDOAROpenDOAR
  • OpenAireOpenAire
  • BASE Bielefeld Academic Search EngineBASE Bielefeld Academic Search Engine
Feedback