Search Results

Documents authored by Althaus, Ernst

Document
DOI: 10.4230/LIPIcs.SEA.2025.24
A New Relaxation for Tree-Based Problems and Minimum Power-Cost Spanning Trees

Authors: Luzie Marianczuk, Ernst Althaus, Stefan Irnich, and Marc E. Pfetsch

Published in: LIPIcs, Volume 338, 23rd International Symposium on Experimental Algorithms (SEA 2025)

Abstract
In this paper, we investigate lower bounds of tree-based optimization problems in order to obtain effective exact algorithms, such as branch-and-bound algorithms. Our new approach inherits the development of dynamic programming algorithms for constrained shortest path problems, as they occur as subproblems in Lagrangian relaxation algorithms and column generation-based algorithms for variants of the Vehicle Routing Problem. In the q-route relaxation, paths must satisfy a capacity constraint while the elementarity constraint is relaxed, that is, paths may contain cycles. An analogue of q-routes for tree optimization problems are q-arbs, a structure that relaxes elementarity for arborescences. We introduce a generalized formulation of q-arbs for a broad class of tree-based problems, and apply the neighborhood restrictions of so-called ng-routes to them to obtain tighter bounds. We apply the new dynamic programming approach to the Minimum Power-Cost Spanning Tree Problem and show empirically that the resulting bounds are often better than traditional LP-based lower bounds of (mixed) integer programming models.
Cite as

Luzie Marianczuk, Ernst Althaus, Stefan Irnich, and Marc E. Pfetsch. A New Relaxation for Tree-Based Problems and Minimum Power-Cost Spanning Trees. In 23rd International Symposium on Experimental Algorithms (SEA 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 338, pp. 24:1-24:18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{marianczuk_et_al:LIPIcs.SEA.2025.24,
  author =	{Marianczuk, Luzie and Althaus, Ernst and Irnich, Stefan and Pfetsch, Marc E.},
  title =	{{A New Relaxation for Tree-Based Problems and Minimum Power-Cost Spanning Trees}},
  booktitle =	{23rd International Symposium on Experimental Algorithms (SEA 2025)},
  pages =	{24:1--24:18},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-375-1},
  ISSN =	{1868-8969},
  year =	{2025},
  volume =	{338},
  editor =	{Mutzel, Petra and Prezza, Nicola},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SEA.2025.24},
  URN =		{urn:nbn:de:0030-drops-232620},
  doi =		{10.4230/LIPIcs.SEA.2025.24},
  annote =	{Keywords: lower bounds, symmetric connectivity, power range assignment, dynamic programming, optimal substructure}
}
Document
DOI: 10.4230/LIPIcs.SEA.2021.9
On Tamaki’s Algorithm to Compute Treewidths

Authors: Ernst Althaus, Daniela Schnurbusch, Julian Wüschner, and Sarah Ziegler

Published in: LIPIcs, Volume 190, 19th International Symposium on Experimental Algorithms (SEA 2021)

Abstract
We revisit the exact algorithm to compute the treewidth of a graph of Tamaki and present it in a way that facilitates improvements. The so-called I-blocks and O-blocks enumerated by the algorithm are interpreted as subtrees of a tree-decomposition that is constructed. This simplifies the proof of correctness and allows to discard subtrees from the enumeration by some simple observations. In our experiments, we show that one of these modifications in particular reduces the number of enumerated objects considerably.
Cite as

Ernst Althaus, Daniela Schnurbusch, Julian Wüschner, and Sarah Ziegler. On Tamaki’s Algorithm to Compute Treewidths. In 19th International Symposium on Experimental Algorithms (SEA 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 190, pp. 9:1-9:18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)

Copy BibTex To Clipboard

@InProceedings{althaus_et_al:LIPIcs.SEA.2021.9,
  author =	{Althaus, Ernst and Schnurbusch, Daniela and W\"{u}schner, Julian and Ziegler, Sarah},
  title =	{{On Tamaki’s Algorithm to Compute Treewidths}},
  booktitle =	{19th International Symposium on Experimental Algorithms (SEA 2021)},
  pages =	{9:1--9:18},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-185-6},
  ISSN =	{1868-8969},
  year =	{2021},
  volume =	{190},
  editor =	{Coudert, David and Natale, Emanuele},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SEA.2021.9},
  URN =		{urn:nbn:de:0030-drops-137818},
  doi =		{10.4230/LIPIcs.SEA.2021.9},
  annote =	{Keywords: Tree Decomposition, Exact Algorithm, Algorithms Engineering}
}
Document
DOI: 10.4230/OASIcs.GCB.2013.56
Efficient Interpretation of Tandem Mass Tags in Top-Down Proteomics

Authors: Anna Katharina Hildebrandt, Ernst Althaus, Hans-Peter Lenhof, Chien-Wen Hung, Andreas Tholey, and Andreas Hildebrandt

Published in: OASIcs, Volume 34, German Conference on Bioinformatics 2013

Abstract
Mass spectrometry is the major analytical tool for the identification and quantification of proteins in biological samples. In so-called top-down proteomics, separation and mass spectrometric analysis is performed at the level of intact proteins, without preparatory digestion steps. It has been shown that the tandem mass tag (TMT) labeling technology, which is often used for quantification based on digested proteins (bottom-up studies), can be applied in top-down proteomics as well. This, however, leads to a complex interpretation problem, where we need to annotate measured peaks with their respective generating protein, the number of charges, and the a priori unknown number of TMT-groups attached to this protein. In this work, we give an algorithm for the efficient enumeration of all valid annotations that fulfill available experimental constraints. Applying the algorithm to real-world data, we show that the annotation problem can indeed be efficiently solved. However, our experiments also demonstrate that reliable annotation in complex mixtures requires at least partial sequence information and high mass accuracy and resolution to go beyond the proof-of-concept stage.
Cite as

Anna Katharina Hildebrandt, Ernst Althaus, Hans-Peter Lenhof, Chien-Wen Hung, Andreas Tholey, and Andreas Hildebrandt. Efficient Interpretation of Tandem Mass Tags in Top-Down Proteomics. In German Conference on Bioinformatics 2013. Open Access Series in Informatics (OASIcs), Volume 34, pp. 56-67, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2013)

Copy BibTex To Clipboard

@InProceedings{hildebrandt_et_al:OASIcs.GCB.2013.56,
  author =	{Hildebrandt, Anna Katharina and Althaus, Ernst and Lenhof, Hans-Peter and Hung, Chien-Wen and Tholey, Andreas and Hildebrandt, Andreas},
  title =	{{Efficient Interpretation of Tandem Mass Tags in Top-Down Proteomics}},
  booktitle =	{German Conference on Bioinformatics 2013},
  pages =	{56--67},
  series =	{Open Access Series in Informatics (OASIcs)},
  ISBN =	{978-3-939897-59-0},
  ISSN =	{2190-6807},
  year =	{2013},
  volume =	{34},
  editor =	{Bei{\ss}barth, Tim and Kollmar, Martin and Leha, Andreas and Morgenstern, Burkhard and Schultz, Anne-Kathrin and Waack, Stephan and Wingender, Edgar},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/OASIcs.GCB.2013.56},
  URN =		{urn:nbn:de:0030-drops-42304},
  doi =		{10.4230/OASIcs.GCB.2013.56},
  annote =	{Keywords: Mass spectrometry, TMT labeling, Top-down Proteomics}
}
Any Issues?
X

Feedback on the Current Page

CAPTCHA

Thanks for your feedback!

Feedback submitted to Dagstuhl Publishing

Could not send message

Please try again later or send an E-mail
© 2023-2025 Schloss Dagstuhl – LZI GmbH About DROPS Imprint Privacy Contact