3 Search Results for "Mock, Daniel"

Document
DOI: 10.4230/LIPIcs.ESA.2023.43
Evaluating Restricted First-Order Counting Properties on Nowhere Dense Classes and Beyond

Authors: Jan Dreier, Daniel Mock, and Peter Rossmanith

Published in: LIPIcs, Volume 274, 31st Annual European Symposium on Algorithms (ESA 2023)

Abstract
It is known that first-order logic with some counting extensions can be efficiently evaluated on graph classes with bounded expansion, where depth-r minors have constant density. More precisely, the formulas are ∃ x₁… x_k#y φ(x_1,…,x_k, y) > N, where φ is an FO-formula. If φ is quantifier-free, we can extend this result to nowhere dense graph classes with an almost linear FPT run time. Lifting this result further to slightly more general graph classes, namely almost nowhere dense classes, where the size of depth-r clique minors is subpolynomial, is impossible unless FPT = W[1]. On the other hand, in almost nowhere dense classes we can approximate such counting formulas with a small additive error. Note those counting formulas are contained in FOC({>}) but not FOC₁(𝐏). In particular, it follows that partial covering problems, such as partial dominating set, have fixed parameter algorithms on nowhere dense graph classes with almost linear running time.
Cite as

Jan Dreier, Daniel Mock, and Peter Rossmanith. Evaluating Restricted First-Order Counting Properties on Nowhere Dense Classes and Beyond. In 31st Annual European Symposium on Algorithms (ESA 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 274, pp. 43:1-43:17, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2023)

Copy BibTex To Clipboard

@InProceedings{dreier_et_al:LIPIcs.ESA.2023.43,
  author =	{Dreier, Jan and Mock, Daniel and Rossmanith, Peter},
  title =	{{Evaluating Restricted First-Order Counting Properties on Nowhere Dense Classes and Beyond}},
  booktitle =	{31st Annual European Symposium on Algorithms (ESA 2023)},
  pages =	{43:1--43:17},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-295-2},
  ISSN =	{1868-8969},
  year =	{2023},
  volume =	{274},
  editor =	{G{\o}rtz, Inge Li and Farach-Colton, Martin and Puglisi, Simon J. and Herman, Grzegorz},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ESA.2023.43},
  URN =		{urn:nbn:de:0030-drops-186961},
  doi =		{10.4230/LIPIcs.ESA.2023.43},
  annote =	{Keywords: nowhere dense, sparsity, counting logic, dominating set, FPT}
}
Document
DOI: 10.4230/LIPIcs.MFCS.2023.29
The Online Simple Knapsack Problem with Reservation and Removability

Authors: Elisabet Burjons, Matthias Gehnen, Henri Lotze, Daniel Mock, and Peter Rossmanith

Published in: LIPIcs, Volume 272, 48th International Symposium on Mathematical Foundations of Computer Science (MFCS 2023)

Abstract
In the online simple knapsack problem, a knapsack of unit size 1 is given and an algorithm is tasked to fill it using a set of items that are revealed one after another. Each item must be accepted or rejected at the time they are presented, and these decisions are irrevocable. No prior knowledge about the set and sequence of items is given. The goal is then to maximize the sum of the sizes of all packed items compared to an optimal packing of all items of the sequence. In this paper, we combine two existing variants of the problem that each extend the range of possible actions for a newly presented item by a new option. The first is removability, in which an item that was previously packed into the knapsack may be finally discarded at any point. The second is reservations, which allows the algorithm to delay the decision on accepting or rejecting a new item indefinitely for a proportional fee relative to the size of the given item. If both removability and reservations are permitted, we show that the competitive ratio of the online simple knapsack problem rises depending on the relative reservation costs. As soon as any nonzero fee has to be paid for a reservation, no online algorithm can be better than 1.5-competitive. With rising reservation costs, this competitive ratio increases up to the golden ratio (ϕ ≈ 1.618) that is reached for relative reservation costs of 1-√5/3 ≈ 0.254. We provide a matching upper and lower bound for relative reservation costs up to this value. From this point onward, the tight bound by Iwama and Taketomi for the removable knapsack problem is the best possible competitive ratio, not using any reservations.
Cite as

Elisabet Burjons, Matthias Gehnen, Henri Lotze, Daniel Mock, and Peter Rossmanith. The Online Simple Knapsack Problem with Reservation and Removability. In 48th International Symposium on Mathematical Foundations of Computer Science (MFCS 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 272, pp. 29:1-29:12, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2023)

Copy BibTex To Clipboard

@InProceedings{burjons_et_al:LIPIcs.MFCS.2023.29,
  author =	{Burjons, Elisabet and Gehnen, Matthias and Lotze, Henri and Mock, Daniel and Rossmanith, Peter},
  title =	{{The Online Simple Knapsack Problem with Reservation and Removability}},
  booktitle =	{48th International Symposium on Mathematical Foundations of Computer Science (MFCS 2023)},
  pages =	{29:1--29:12},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-292-1},
  ISSN =	{1868-8969},
  year =	{2023},
  volume =	{272},
  editor =	{Leroux, J\'{e}r\^{o}me and Lombardy, Sylvain and Peleg, David},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.MFCS.2023.29},
  URN =		{urn:nbn:de:0030-drops-185635},
  doi =		{10.4230/LIPIcs.MFCS.2023.29},
  annote =	{Keywords: online algorithm, knapsack, competitive ratio, reservation, preemption}
}
Document
DOI: 10.4230/OASIcs.ICCSW.2015.54
Interactive 3D Reconstruction: New Opportunities for Getting CAD-ready Models

Authors: Julius Schöning

Published in: OASIcs, Volume 49, 2015 Imperial College Computing Student Workshop (ICCSW 2015)

Abstract
A multitude of image-based 3D reconstruction and modeling techniques exist, which have achieved significant success in recent years. However, these techniques still lack certain abilities. For example, current 3D reconstruction techniques cannot decompose an object into its individual subparts. Thus, a printed model will consist of one single monolithic piece, which does not allow composing or decomposing parts, does not allow movable or flexible parts, and does not allow manufacturing the model from multiple different materials like wood, metal, or plastic. I reviewed the work in the research area of 3D reconstruction and provide an analysis of neglected research objectives and current drawbacks. Furthermore, I propose a mock-up of an interactive tool as a guideline for future research which describes a possible architecture, user interfaces, and processing pipeline, to overcome existing drawbacks of 3D reconstruction techniques.
Cite as

Julius Schöning. Interactive 3D Reconstruction: New Opportunities for Getting CAD-ready Models. In 2015 Imperial College Computing Student Workshop (ICCSW 2015). Open Access Series in Informatics (OASIcs), Volume 49, pp. 54-61, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2015)

Copy BibTex To Clipboard

@InProceedings{schoning:OASIcs.ICCSW.2015.54,
  author =	{Sch\"{o}ning, Julius},
  title =	{{Interactive 3D Reconstruction: New Opportunities for Getting CAD-ready Models}},
  booktitle =	{2015 Imperial College Computing Student Workshop (ICCSW 2015)},
  pages =	{54--61},
  series =	{Open Access Series in Informatics (OASIcs)},
  ISBN =	{978-3-95977-000-2},
  ISSN =	{2190-6807},
  year =	{2015},
  volume =	{49},
  editor =	{Schulz, Claudia and Liew, Daniel},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/OASIcs.ICCSW.2015.54},
  URN =		{urn:nbn:de:0030-drops-54814},
  doi =		{10.4230/OASIcs.ICCSW.2015.54},
  annote =	{Keywords: 3D Reconstruction, 3D Modeling, Interactive Reconstruction, CAD-ready}
}
  • Refine by Author
  • 2 Mock, Daniel
  • 2 Rossmanith, Peter
  • 1 Burjons, Elisabet
  • 1 Dreier, Jan
  • 1 Gehnen, Matthias
  • Show More...

  • Refine by Classification
  • 1 Mathematics of computing → Graph theory
  • 1 Theory of computation
  • 1 Theory of computation → Computational complexity and cryptography
  • 1 Theory of computation → Logic
  • 1 Theory of computation → Parameterized complexity and exact algorithms

  • Refine by Keyword
  • 1 3D Modeling
  • 1 3D Reconstruction
  • 1 CAD-ready
  • 1 FPT
  • 1 Interactive Reconstruction
  • Show More...

  • Refine by Type
  • 3 document

  • Refine by Publication Year
  • 2 2023
  • 1 2015

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
© 2023 Schloss Dagstuhl - LZI GmbH Imprint Privacy Contact