2 Search Results for "Tschager, Thomas"

Document
DOI: 10.4230/LIPIcs.MFCS.2025.46
Guarding Offices with Maximum Dispersion

Authors: Sándor P. Fekete, Kai Kobbe, Dominik Krupke, Joseph S. B. Mitchell, Christian Rieck, and Christian Scheffer

Published in: LIPIcs, Volume 345, 50th International Symposium on Mathematical Foundations of Computer Science (MFCS 2025)

Abstract
We investigate the Dispersive Art Gallery Problem with vertex guards and rectangular visibility (r-visibility) for a class of orthogonal polygons that reflect the properties of real-world floor plans: these office-like polygons consist of rectangular rooms and corridors. In the dispersive variant of the Art Gallery Problem, the objective is not to minimize the number of guards but to maximize the minimum geodesic L₁-distance between any two guards, called the dispersion distance. Our main contributions are as follows. We prove that determining whether a vertex guard set can achieve a dispersion distance of 4 in office-like polygons is NP-complete, where vertices of the polygon are restricted to integer coordinates. Additionally, we present a simple worst-case optimal algorithm that guarantees a dispersion distance of 3 in polynomial time. Our complexity result extends to polyominoes, resolving an open question posed by Rieck and Scheffer [Christian Rieck and Christian Scheffer, 2024]. When vertex coordinates are allowed to be rational, we establish analogous results, proving that achieving a dispersion distance of 2+ε is NP-hard for any ε > 0, while the classic Art Gallery Problem remains solvable in polynomial time for this class of polygons. Furthermore, we give a straightforward polynomial-time algorithm that computes worst-case optimal solutions with a dispersion distance 2. On the other hand, for the more restricted class of hole-free independent office-like polygons, we propose a dynamic programming approach that computes optimal solutions. Moreover, we demonstrate that the problem is practically tractable for arbitrary orthogonal polygons. To this end, we compare solvers based on SAT, CP, and MIP formulations. Notably, SAT solvers efficiently compute optimal solutions for randomly generated instances with up to 1600 vertices in under 15s.
Cite as

Sándor P. Fekete, Kai Kobbe, Dominik Krupke, Joseph S. B. Mitchell, Christian Rieck, and Christian Scheffer. Guarding Offices with Maximum Dispersion. In 50th International Symposium on Mathematical Foundations of Computer Science (MFCS 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 345, pp. 46:1-46:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{fekete_et_al:LIPIcs.MFCS.2025.46,
  author =	{Fekete, S\'{a}ndor P. and Kobbe, Kai and Krupke, Dominik and Mitchell, Joseph S. B. and Rieck, Christian and Scheffer, Christian},
  title =	{{Guarding Offices with Maximum Dispersion}},
  booktitle =	{50th International Symposium on Mathematical Foundations of Computer Science (MFCS 2025)},
  pages =	{46:1--46:17},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-388-1},
  ISSN =	{1868-8969},
  year =	{2025},
  volume =	{345},
  editor =	{Gawrychowski, Pawe{\l} and Mazowiecki, Filip and Skrzypczak, Micha{\l}},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.MFCS.2025.46},
  URN =		{urn:nbn:de:0030-drops-241530},
  doi =		{10.4230/LIPIcs.MFCS.2025.46},
  annote =	{Keywords: Dispersive Art Gallery Problem, vertex guards, office-like polygons, orthogonal polygons, polyominoes, NP-completeness, worst-case optimality, dynamic programming, SAT solver}
}
Document
DOI: 10.4230/LIPIcs.WABI.2017.26
Improved De Novo Peptide Sequencing using LC Retention Time Information

Authors: Yves Frank, Tomas Hruz, Thomas Tschager, and Valentin Venzin

Published in: LIPIcs, Volume 88, 17th International Workshop on Algorithms in Bioinformatics (WABI 2017)

Abstract
Liquid chromatography combined with tandem mass spectrometry (LC-MS/MS) is an important tool in proteomics for identifying the peptides in a sample. Liquid chromatography temporally separates the peptides and tandem mass spectrometry analyzes the peptides, that elute one after another, by measuring their mass-to-charge ratios and the mass-to-charge ratios of their prefix and suffix fragments. De novo peptide sequencing is the problem of reconstructing the amino acid sequences of the analyzed peptide from this measurement data. While previous approaches solely consider the mass spectrum of the fragments for reconstructing a sequence, we propose to also exploit the information obtained from liquid chromatography. We study the problem of computing a sequence that is not only in accordance with the experimental mass spectrum, but also with the retention time of the separation by liquid chromatography. We consider three models for predicting the retention time of a peptide and develop algorithms for de novo sequencing for each model. An evaluation on experimental data from synthesized peptides for two of these models shows an improved performance compared to not using the chromatographic information.
Cite as

Yves Frank, Tomas Hruz, Thomas Tschager, and Valentin Venzin. Improved De Novo Peptide Sequencing using LC Retention Time Information. In 17th International Workshop on Algorithms in Bioinformatics (WABI 2017). Leibniz International Proceedings in Informatics (LIPIcs), Volume 88, pp. 26:1-26:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2017)

Copy BibTex To Clipboard

@InProceedings{frank_et_al:LIPIcs.WABI.2017.26,
  author =	{Frank, Yves and Hruz, Tomas and Tschager, Thomas and Venzin, Valentin},
  title =	{{Improved De Novo Peptide Sequencing using LC Retention Time Information}},
  booktitle =	{17th International Workshop on Algorithms in Bioinformatics (WABI 2017)},
  pages =	{26:1--26:17},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-050-7},
  ISSN =	{1868-8969},
  year =	{2017},
  volume =	{88},
  editor =	{Schwartz, Russell and Reinert, Knut},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.WABI.2017.26},
  URN =		{urn:nbn:de:0030-drops-76383},
  doi =		{10.4230/LIPIcs.WABI.2017.26},
  annote =	{Keywords: Computational proteomics, Peptide identification, Mass spectrometry, De novo peptide sequencing, Retention time prediction}
}
  • Refine by Type
  • 2 Document/PDF
  • 1 Document/HTML

  • Refine by Publication Year
  • 1 2025
  • 1 2017

  • Refine by Author
  • 1 Fekete, Sándor P.
  • 1 Frank, Yves
  • 1 Hruz, Tomas
  • 1 Kobbe, Kai
  • 1 Krupke, Dominik
  • Show More...

  • Refine by Series/Journal
  • 2 LIPIcs

  • Refine by Classification
  • 1 Theory of computation → Computational geometry

  • Refine by Keyword
  • 1 Computational proteomics
  • 1 De novo peptide sequencing
  • 1 Dispersive Art Gallery Problem
  • 1 Mass spectrometry
  • 1 NP-completeness
  • Show More...

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-2026 Schloss Dagstuhl – LZI GmbH Schloss Dagstuhl – LZI GmbH About DROPS Imprint Privacy Contact