DROPS

Document

05391 Executive Summary – Numerical and Algebraic Algorithms and Computer-assisted Proofs

Authors: Bruno Buchberger, Christian Jansson, Shin'ichi Oishi, Michael Plum, and Siegfried M. Rump

Published in: Dagstuhl Seminar Proceedings, Volume 5391, Algebraic and Numerical Algorithms and Computer-assisted Proofs (2006)

Abstract

The common goal of self-validating methods and computer algebra methods is to solve mathematical problems with complete rigor and with the aid of computers. The seminar focused on several aspects of such methods for computer-assisted proofs.

Cite as

Bruno Buchberger, Christian Jansson, Shin'ichi Oishi, Michael Plum, and Siegfried M. Rump. 05391 Executive Summary – Numerical and Algebraic Algorithms and Computer-assisted Proofs. In Algebraic and Numerical Algorithms and Computer-assisted Proofs. Dagstuhl Seminar Proceedings, Volume 5391, pp. 1-5, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2006)

Copy BibTex To Clipboard

@InProceedings{buchberger_et_al:DagSemProc.05391.2,
  author =	{Buchberger, Bruno and Jansson, Christian and Oishi, Shin'ichi and Plum, Michael and Rump, Siegfried M.},
  title =	{{05391 Executive Summary – Numerical and Algebraic Algorithms and Computer-assisted Proofs}},
  booktitle =	{Algebraic and Numerical Algorithms and Computer-assisted Proofs},
  pages =	{1--5},
  series =	{Dagstuhl Seminar Proceedings (DagSemProc)},
  ISSN =	{1862-4405},
  year =	{2006},
  volume =	{5391},
  editor =	{Bruno Buchberger and Shin'ichi Oishi and Michael Plum and Sigfried M. Rump},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/DagSemProc.05391.2},
  URN =		{urn:nbn:de:0030-drops-4549},
  doi =		{10.4230/DagSemProc.05391.2},
  annote =	{Keywords: Self-validating methods, computer algebra, computer-assisted proofs, real number algorithms}
}

Document

DOI: 10.4230/DagSemProc.05391.7

Rigorous Results in Combinatorial Optimization

Authors: Christian Jansson

Published in: Dagstuhl Seminar Proceedings, Volume 5391, Algebraic and Numerical Algorithms and Computer-assisted Proofs (2006)

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.

Cite as

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)

Copy BibTex To Clipboard

@InProceedings{jansson:DagSemProc.05391.7,
  author =	{Jansson, Christian},
  title =	{{Rigorous Results in Combinatorial Optimization}},
  booktitle =	{Algebraic and Numerical Algorithms and Computer-assisted Proofs},
  pages =	{1--8},
  series =	{Dagstuhl Seminar Proceedings (DagSemProc)},
  ISSN =	{1862-4405},
  year =	{2006},
  volume =	{5391},
  editor =	{Bruno Buchberger and Shin'ichi Oishi and Michael Plum and Sigfried M. Rump},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/DagSemProc.05391.7},
  URN =		{urn:nbn:de:0030-drops-4467},
  doi =		{10.4230/DagSemProc.05391.7},
  annote =	{Keywords: Combinatorial Optimization, Semidefinite Programming, Ill-posed Problems, Verification Methods}
}

Search Results

Documents authored by Jansson, Christian

05391 Executive Summary – Numerical and Algebraic Algorithms and Computer-assisted Proofs

Abstract

Cite as

Rigorous Results in Combinatorial Optimization

Abstract

Cite as

Thanks for your feedback!

Could not send message