Search Results

Documents authored by Jansson, Christian


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
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}
}
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