5 Search Results for "Frei, Fabian"

Document
DOI: 10.4230/LIPIcs.STACS.2024.18
Removable Online Knapsack and Advice

Authors: Hans-Joachim Böckenhauer, Fabian Frei, and Peter Rossmanith

Published in: LIPIcs, Volume 289, 41st International Symposium on Theoretical Aspects of Computer Science (STACS 2024)

Abstract
In the proportional knapsack problem, we are given a knapsack of some capacity and a set of variably sized items. The goal is to pack a selection of these items that fills the knapsack as much as possible. The online version of this problem reveals the items and their sizes not all at once but one by one. For each item, the algorithm has to decide immediately whether to pack it or not. We consider a natural variant of this online knapsack problem, which has been coined removable knapsack. It differs from the classical variant by allowing the removal of any packed item from the knapsack. Repacking is impossible, however: Once an item is removed, it is gone for good. We analyze the advice complexity of this problem. It measures how many advice bits an omniscient oracle needs to provide for an online algorithm to reach any given competitive ratio, which is - understood in its strict sense - just the algorithm’s approximation factor. The online knapsack problem is known for its peculiar advice behavior involving three jumps in competitivity. We show that the advice complexity of the version with removability is quite different but just as interesting: The competitivity starts from the golden ratio when no advice is given. It then drops down to 1+ε for a constant amount of advice already, which requires logarithmic advice in the classical version. Removability comes as no relief to the perfectionist, however: Optimality still requires linear advice as before. These results are particularly noteworthy from a structural viewpoint for the exceptionally slow transition from near-optimality to optimality. Our most important and demanding result shows that the general knapsack problem, which allows an item’s value to differ from its size, exhibits a similar behavior for removability, but with an even more pronounced jump from an unbounded competitive ratio to near-optimality within just constantly many advice bits. This is a unique behavior among the problems considered in the literature so far. An advice analysis is interesting in its own right, as it allows us to measure the information content of a problem and leads to structural insights. But it also provides insurmountable lower bounds, applicable to any kind of additional information about the instances, including predictions provided by machine-learning algorithms and artificial intelligence. Unexpectedly, advice algorithms are useful in various real-life situations, too. For example, they provide smart strategies for cooperation in winner-take-all competitions, where several participants pool together to implement different strategies and share the obtained prize. Further illustrating the versatility of our advice-complexity bounds, our results automatically improve some of the best known lower bounds on the competitive ratio for removable knapsack with randomization. The presented advice algorithms also automatically yield deterministic algorithms for established deterministic models such as knapsack with a resource buffer and various problems with more than one knapsack. In their seminal paper introducing removability to the knapsack problem, Iwama and Taketomi have indeed proposed a multiple knapsack problem for which we can establish a one-to-one correspondence with the advice model; this paper therefore even provides a comprehensive analysis for this up until now neglected problem.
Cite as

Hans-Joachim Böckenhauer, Fabian Frei, and Peter Rossmanith. Removable Online Knapsack and Advice. In 41st International Symposium on Theoretical Aspects of Computer Science (STACS 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 289, pp. 18:1-18:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)

Copy BibTex To Clipboard

@InProceedings{bockenhauer_et_al:LIPIcs.STACS.2024.18,
  author =	{B\"{o}ckenhauer, Hans-Joachim and Frei, Fabian and Rossmanith, Peter},
  title =	{{Removable Online Knapsack and Advice}},
  booktitle =	{41st International Symposium on Theoretical Aspects of Computer Science (STACS 2024)},
  pages =	{18:1--18:17},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-311-9},
  ISSN =	{1868-8969},
  year =	{2024},
  volume =	{289},
  editor =	{Beyersdorff, Olaf and Kant\'{e}, Mamadou Moustapha and Kupferman, Orna and Lokshtanov, Daniel},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2024.18},
  URN =		{urn:nbn:de:0030-drops-197283},
  doi =		{10.4230/LIPIcs.STACS.2024.18},
  annote =	{Keywords: Removable Online Knapsack, Multiple Knapsack, Advice Analysis, Advice Applications, Machine Learning and AI}
}
Document
DOI: 10.4230/LIPIcs.ISAAC.2020.19
Complexity of Stability

Authors: Fabian Frei, Edith Hemaspaandra, and Jörg Rothe

Published in: LIPIcs, Volume 181, 31st International Symposium on Algorithms and Computation (ISAAC 2020)

Abstract
Graph parameters such as the clique number, the chromatic number, and the independence number are central in many areas, ranging from computer networks to linguistics to computational neuroscience to social networks. In particular, the chromatic number of a graph (i.e., the smallest number of colors needed to color all vertices such that no two adjacent vertices are of the same color) can be applied in solving practical tasks as diverse as pattern matching, scheduling jobs to machines, allocating registers in compiler optimization, and even solving Sudoku puzzles. Typically, however, the underlying graphs are subject to (often minor) changes. To make these applications of graph parameters robust, it is important to know which graphs are stable for them in the sense that adding or deleting single edges or vertices does not change them. We initiate the study of stability of graphs for such parameters in terms of their computational complexity. We show that, for various central graph parameters, the problem of determining whether or not a given graph is stable is complete for Θ₂ᵖ, a well-known complexity class in the second level of the polynomial hierarchy, which is also known as "parallel access to NP."
Cite as

Fabian Frei, Edith Hemaspaandra, and Jörg Rothe. Complexity of Stability. In 31st International Symposium on Algorithms and Computation (ISAAC 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 181, pp. 19:1-19:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)

Copy BibTex To Clipboard

@InProceedings{frei_et_al:LIPIcs.ISAAC.2020.19,
  author =	{Frei, Fabian and Hemaspaandra, Edith and Rothe, J\"{o}rg},
  title =	{{Complexity of Stability}},
  booktitle =	{31st International Symposium on Algorithms and Computation (ISAAC 2020)},
  pages =	{19:1--19:14},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-173-3},
  ISSN =	{1868-8969},
  year =	{2020},
  volume =	{181},
  editor =	{Cao, Yixin and Cheng, Siu-Wing and Li, Minming},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ISAAC.2020.19},
  URN =		{urn:nbn:de:0030-drops-133631},
  doi =		{10.4230/LIPIcs.ISAAC.2020.19},
  annote =	{Keywords: Stability, Robustness, Complexity, Local Modifications, Colorability, Vertex Cover, Clique, Independent Set, Satisfiability, Unfrozenness, Criticality, DP, coDP, Parallel Access to NP}
}
Document
DOI: 10.4230/LIPIcs.FUN.2021.14
An Open Pouring Problem

Authors: Fabian Frei, Peter Rossmanith, and David Wehner

Published in: LIPIcs, Volume 157, 10th International Conference on Fun with Algorithms (FUN 2021) (2020)

Abstract
We analyze a little riddle that has challenged mathematicians for half a century. Imagine three clubs catering to people with some niche interest. Everyone willing to join a club has done so and nobody new will pick up this eccentric hobby for the foreseeable future, thus the mutually exclusive clubs compete for a common constituency. Members are highly invested in their chosen club; only a targeted campaign plus prolonged personal persuasion can convince them to consider switching. Even then, they will never be enticed into a bigger group as they naturally pride themselves in avoiding the mainstream. Therefore each club occasionally starts a campaign against a larger competitor and sends its own members out on a recommendation program. Each will win one person over; the small club can thus effectively double its own numbers at the larger one’s expense. Is there always a risk for one club to wind up with zero members, forcing it out of business? If so, how many campaign cycles will this take?
Cite as

Fabian Frei, Peter Rossmanith, and David Wehner. An Open Pouring Problem. In 10th International Conference on Fun with Algorithms (FUN 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 157, pp. 14:1-14:9, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)

Copy BibTex To Clipboard

@InProceedings{frei_et_al:LIPIcs.FUN.2021.14,
  author =	{Frei, Fabian and Rossmanith, Peter and Wehner, David},
  title =	{{An Open Pouring Problem}},
  booktitle =	{10th International Conference on Fun with Algorithms (FUN 2021)},
  pages =	{14:1--14:9},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-145-0},
  ISSN =	{1868-8969},
  year =	{2020},
  volume =	{157},
  editor =	{Farach-Colton, Martin and Prencipe, Giuseppe and Uehara, Ryuhei},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.FUN.2021.14},
  URN =		{urn:nbn:de:0030-drops-127751},
  doi =		{10.4230/LIPIcs.FUN.2021.14},
  annote =	{Keywords: Pitcher Pouring Problem, Water Jug Riddle, Water Bucket Problem, Vessel Puzzle, Complexity, Die Hard}
}
Document
DOI: 10.4230/LIPIcs.ISAAC.2019.52
Efficient Circuit Simulation in MapReduce

Authors: Fabian Frei and Koichi Wada

Published in: LIPIcs, Volume 149, 30th International Symposium on Algorithms and Computation (ISAAC 2019)

Abstract
The MapReduce framework has firmly established itself as one of the most widely used parallel computing platforms for processing big data on tera- and peta-byte scale. Approaching it from a theoretical standpoint has proved to be notoriously difficult, however. In continuation of Goodrich et al.’s early efforts, explicitly espousing the goal of putting the MapReduce framework on footing equal to that of long-established models such as the PRAM, we investigate the obvious complexity question of how the computational power of MapReduce algorithms compares to that of combinational Boolean circuits commonly used for parallel computations. Relying on the standard MapReduce model introduced by Karloff et al. a decade ago, we develop an intricate simulation technique to show that any problem in NC (i.e., a problem solved by a logspace-uniform family of Boolean circuits of polynomial size and a depth polylogarithmic in the input size) can be solved by a MapReduce computation in O(T(n)/log n) rounds, where n is the input size and T(n) is the depth of the witnessing circuit family. Thus, we are able to closely relate the standard, uniform NC hierarchy modeling parallel computations to the deterministic MapReduce hierarchy DMRC by proving that NC^{i+1} subseteq DMRC^i for all i in N. Besides the theoretical significance, this result has important applied aspects as well. In particular, we show for all problems in NC^1 - many practically relevant ones, such as integer multiplication and division and the parity function, being among these - how to solve them in a constant number of deterministic MapReduce rounds.
Cite as

Fabian Frei and Koichi Wada. Efficient Circuit Simulation in MapReduce. In 30th International Symposium on Algorithms and Computation (ISAAC 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 149, pp. 52:1-52:21, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)

Copy BibTex To Clipboard

@InProceedings{frei_et_al:LIPIcs.ISAAC.2019.52,
  author =	{Frei, Fabian and Wada, Koichi},
  title =	{{Efficient Circuit Simulation in MapReduce}},
  booktitle =	{30th International Symposium on Algorithms and Computation (ISAAC 2019)},
  pages =	{52:1--52:21},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-130-6},
  ISSN =	{1868-8969},
  year =	{2019},
  volume =	{149},
  editor =	{Lu, Pinyan and Zhang, Guochuan},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ISAAC.2019.52},
  URN =		{urn:nbn:de:0030-drops-115487},
  doi =		{10.4230/LIPIcs.ISAAC.2019.52},
  annote =	{Keywords: MapReduce, Circuit Complexity, Parallel Algorithms, Nick’s Class NC}
}
Document
DOI: 10.4230/LIPIcs.MFCS.2019.78
Finding Optimal Solutions With Neighborly Help

Authors: Elisabet Burjons, Fabian Frei, Edith Hemaspaandra, Dennis Komm, and David Wehner

Published in: LIPIcs, Volume 138, 44th International Symposium on Mathematical Foundations of Computer Science (MFCS 2019)

Abstract
Can we efficiently compute optimal solutions to instances of a hard problem from optimal solutions to neighboring (i.e., locally modified) instances? For example, can we efficiently compute an optimal coloring for a graph from optimal colorings for all one-edge-deleted subgraphs? Studying such questions not only gives detailed insight into the structure of the problem itself, but also into the complexity of related problems; most notably graph theory’s core notion of critical graphs (e.g., graphs whose chromatic number decreases under deletion of an arbitrary edge) and the complexity-theoretic notion of minimality problems (also called criticality problems, e.g., recognizing graphs that become 3-colorable when an arbitrary edge is deleted). We focus on two prototypical graph problems, Colorability and Vertex Cover. For example, we show that it is NP-hard to compute an optimal coloring for a graph from optimal colorings for all its one-vertex-deleted subgraphs, and that this remains true even when optimal solutions for all one-edge-deleted subgraphs are given. In contrast, computing an optimal coloring from all (or even just two) one-edge-added supergraphs is in P. We observe that Vertex Cover exhibits a remarkably different behavior, demonstrating the power of our model to delineate problems from each other more precisely on a structural level. Moreover, we provide a number of new complexity results for minimality and criticality problems. For example, we prove that Minimal-3-UnColorability is complete for DP (differences of NP sets), which was previously known only for the more amenable case of deleting vertices rather than edges. For Vertex Cover, we show that recognizing beta-vertex-critical graphs is complete for Theta_2^p (parallel access to NP), obtaining the first completeness result for a criticality problem for this class.
Cite as

Elisabet Burjons, Fabian Frei, Edith Hemaspaandra, Dennis Komm, and David Wehner. Finding Optimal Solutions With Neighborly Help. In 44th International Symposium on Mathematical Foundations of Computer Science (MFCS 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 138, pp. 78:1-78:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)

Copy BibTex To Clipboard

@InProceedings{burjons_et_al:LIPIcs.MFCS.2019.78,
  author =	{Burjons, Elisabet and Frei, Fabian and Hemaspaandra, Edith and Komm, Dennis and Wehner, David},
  title =	{{Finding Optimal Solutions With Neighborly Help}},
  booktitle =	{44th International Symposium on Mathematical Foundations of Computer Science (MFCS 2019)},
  pages =	{78:1--78:14},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-117-7},
  ISSN =	{1868-8969},
  year =	{2019},
  volume =	{138},
  editor =	{Rossmanith, Peter and Heggernes, Pinar and Katoen, Joost-Pieter},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.MFCS.2019.78},
  URN =		{urn:nbn:de:0030-drops-110221},
  doi =		{10.4230/LIPIcs.MFCS.2019.78},
  annote =	{Keywords: Critical Graphs, Computational Complexity, Structural Self-Reducibility, Minimality Problems, Colorability, Vertex Cover, Satisfiability, Reoptimization, Advice}
}
  • Refine by Author
  • 5 Frei, Fabian
  • 2 Hemaspaandra, Edith
  • 2 Rossmanith, Peter
  • 2 Wehner, David
  • 1 Burjons, Elisabet
  • Show More...

  • Refine by Classification
  • 3 Theory of computation → Complexity classes
  • 2 Theory of computation → Problems, reductions and completeness
  • 1 Computing methodologies → MapReduce algorithms
  • 1 Mathematics of computing → Extremal graph theory
  • 1 Software and its engineering → Ultra-large-scale systems
  • Show More...

  • Refine by Keyword
  • 2 Colorability
  • 2 Complexity
  • 2 Satisfiability
  • 2 Vertex Cover
  • 1 Advice
  • Show More...

  • Refine by Type
  • 5 document

  • Refine by Publication Year
  • 2 2019
  • 2 2020
  • 1 2024

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