3 Search Results for "Jansson, Christian"


Document
Cache Oblivious Algorithms for Computing the Triplet Distance Between Trees

Authors: Gerth Stølting Brodal and Konstantinos Mampentzidis

Published in: LIPIcs, Volume 87, 25th Annual European Symposium on Algorithms (ESA 2017)


Abstract
We study the problem of computing the triplet distance between two rooted unordered trees with n labeled leafs. Introduced by Dobson 1975, the triplet distance is the number of leaf triples that induce different topologies in the two trees. The current theoretically best algorithm is an O(nlogn) time algorithm by Brodal et al. [SODA 2013]. Recently Jansson et al. proposed a new algorithm that, while slower in theory, requiring O(n log^3 n) time, in practice it outperforms the theoretically faster O(n log n) algorithm. Both algorithms do not scale to external memory. We present two cache oblivious algorithms that combine the best of both worlds. The first algorithm is for the case when the two input trees are binary trees and the second a generalized algorithm for two input trees of arbitrary degree. Analyzed in the RAM model, both algorithms require O(n log n) time, and in the cache oblivious model O(n/B log_{2}(n/M)) I/Os. Their relative simplicity and the fact that they scale to external memory makes them achieve the best practical performance. We note that these are the first algorithms that scale to external memory, both in theory and practice, for this problem.

Cite as

Gerth Stølting Brodal and Konstantinos Mampentzidis. Cache Oblivious Algorithms for Computing the Triplet Distance Between Trees. In 25th Annual European Symposium on Algorithms (ESA 2017). Leibniz International Proceedings in Informatics (LIPIcs), Volume 87, pp. 21:1-21:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2017)


Copy BibTex To Clipboard

@InProceedings{stltingbrodal_et_al:LIPIcs.ESA.2017.21,
  author =	{St{\o}lting Brodal, Gerth and Mampentzidis, Konstantinos},
  title =	{{Cache Oblivious Algorithms for Computing the Triplet Distance Between Trees}},
  booktitle =	{25th Annual European Symposium on Algorithms (ESA 2017)},
  pages =	{21:1--21:14},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-049-1},
  ISSN =	{1868-8969},
  year =	{2017},
  volume =	{87},
  editor =	{Pruhs, Kirk and Sohler, Christian},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ESA.2017.21},
  URN =		{urn:nbn:de:0030-drops-78820},
  doi =		{10.4230/LIPIcs.ESA.2017.21},
  annote =	{Keywords: Phylogenetic tree, tree comparison, triplet distance, cache oblivious algorithm}
}
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-dev.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-dev.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}
}
  • Refine by Author
  • 2 Jansson, Christian
  • 1 Buchberger, Bruno
  • 1 Mampentzidis, Konstantinos
  • 1 Oishi, Shin'ichi
  • 1 Plum, Michael
  • Show More...

  • Refine by Classification

  • Refine by Keyword
  • 1 Combinatorial Optimization
  • 1 Ill-posed Problems
  • 1 Phylogenetic tree
  • 1 Self-validating methods
  • 1 Semidefinite Programming
  • Show More...

  • Refine by Type
  • 3 document

  • Refine by Publication Year
  • 2 2006
  • 1 2017

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