Search Results

Documents authored by Mock, Daniel

Document
DOI: 10.4230/LIPIcs.SWAT.2024.35
Solving a Family Of Multivariate Optimization and Decision Problems on Classes of Bounded Expansion

Authors: Daniel Mock and Peter Rossmanith

Published in: LIPIcs, Volume 294, 19th Scandinavian Symposium and Workshops on Algorithm Theory (SWAT 2024)

Abstract
For some time, it has been known that the model checking problem for first-order formulas is fixed-parameter tractable on nowhere dense graph classes, so we shall ask in which direction there is space for improvements. One of the possible directions is to go beyond first-order formulas: Augmenting first-order logic with general counting quantifiers increases the expressiveness by far, but makes the model checking problem hard even on graphs of bounded tree-depth. The picture is different if we allow only "simple" - but arbitrarily nested - counting terms of the form #y φ(x^- ,y) > N. Even then, only approximate model checking is possible on graph classes of bounded expansion. Here, the largest known logic fragment, on which exact model checking is still fpt, consists of formulas of the form ∃x_1 … ∃x_k #y φ(x^- ,y) > N, where φ(x^- ,y) is a first-order formula without counting terms. An example of a problem that can be expressed in this way is partial dominating set: Are there k vertices that dominate at least a given number of vertices in the graph? The complexity of the same problem is open if you replace at least with exactly. Likewise, the complexity of "are there k vertices that dominate at least half of the blue and half of the red vertices?" is also open. We answer both questions by providing an fpt algorithm that solves the model checking problem for formulas of the more general form ψ ≡ ∃x_1 … ∃x_k P(#y φ_1(x^- ,y), …, #y φ_ℓ(x^- ,y)), where P is an arbitrary polynomially computable predicate on numbers. The running time is f(|ψ|)n^{𝓁+1} polylog(n) on graph classes of bounded expansion. Under SETH, this running time is tight up to almost linear factor.
Cite as

Daniel Mock and Peter Rossmanith. Solving a Family Of Multivariate Optimization and Decision Problems on Classes of Bounded Expansion. In 19th Scandinavian Symposium and Workshops on Algorithm Theory (SWAT 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 294, pp. 35:1-35:18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)

Copy BibTex To Clipboard

@InProceedings{mock_et_al:LIPIcs.SWAT.2024.35,
  author =	{Mock, Daniel and Rossmanith, Peter},
  title =	{{Solving a Family Of Multivariate Optimization and Decision Problems on Classes of Bounded Expansion}},
  booktitle =	{19th Scandinavian Symposium and Workshops on Algorithm Theory (SWAT 2024)},
  pages =	{35:1--35:18},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-318-8},
  ISSN =	{1868-8969},
  year =	{2024},
  volume =	{294},
  editor =	{Bodlaender, Hans L.},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SWAT.2024.35},
  URN =		{urn:nbn:de:0030-drops-200754},
  doi =		{10.4230/LIPIcs.SWAT.2024.35},
  annote =	{Keywords: bounded expansion, parameterized algorithms, sparsity, counting logic, dominating set, model checking, multivariate optimization}
}
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}
}
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-2024 Schloss Dagstuhl – LZI GmbH Imprint Privacy Contact