5 Search Results for "Neuwohner, Meike"

Document
DOI: 10.4230/LIPIcs.ESA.2025.79
Semi-Streaming Algorithms for Hypergraph Matching

Authors: Henrik Reinstädtler, S M Ferdous, Alex Pothen, Bora Uçar, and Christian Schulz

Published in: LIPIcs, Volume 351, 33rd Annual European Symposium on Algorithms (ESA 2025)

Abstract
We propose two one-pass streaming algorithms for the NP-hard hypergraph matching problem. The first algorithm stores a small subset of potential matching edges in a stack using dual variables to select edges. It has an approximation guarantee of 1/(d(1+ε)) and requires 𝒪((n/ε)log²n) bits of memory, where n is the number of vertices in the hypergraph, d is the maximum number of vertices in a hyperedge, and ε > 0 is a parameter to be chosen. The second algorithm computes, stores, and updates a single matching as the edges stream, with an approximation ratio dependent on a parameter α. Its best approximation guarantee is 1/((2d-1) + 2 √{d(d-1)}), and it requires only 𝒪(n) memory. We have implemented both algorithms and compared them with respect to solution quality, memory consumption, and running times on two diverse sets of hypergraphs with a non-streaming greedy and a naive streaming algorithm. Our results show that the streaming algorithms achieve much better solution quality than naive algorithms when facing adverse orderings. Furthermore, these algorithms reduce the memory required by a factor of 13 in the geometric mean on our test problems, and also outperform the offline Greedy algorithm in running time.
Cite as

Henrik Reinstädtler, S M Ferdous, Alex Pothen, Bora Uçar, and Christian Schulz. Semi-Streaming Algorithms for Hypergraph Matching. In 33rd Annual European Symposium on Algorithms (ESA 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 351, pp. 79:1-79:19, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{reinstadtler_et_al:LIPIcs.ESA.2025.79,
  author =	{Reinst\"{a}dtler, Henrik and Ferdous, S M and Pothen, Alex and U\c{c}ar, Bora and Schulz, Christian},
  title =	{{Semi-Streaming Algorithms for Hypergraph Matching}},
  booktitle =	{33rd Annual European Symposium on Algorithms (ESA 2025)},
  pages =	{79:1--79:19},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-395-9},
  ISSN =	{1868-8969},
  year =	{2025},
  volume =	{351},
  editor =	{Benoit, Anne and Kaplan, Haim and Wild, Sebastian 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.2025.79},
  URN =		{urn:nbn:de:0030-drops-245478},
  doi =		{10.4230/LIPIcs.ESA.2025.79},
  annote =	{Keywords: hypergraph, matching, semi-streaming}
}
Document
DOI: 10.4230/LIPIcs.ITCS.2024.71
Hardness of Approximating Bounded-Degree Max 2-CSP and Independent Set on k-Claw-Free Graphs

Authors: Euiwoong Lee and Pasin Manurangsi

Published in: LIPIcs, Volume 287, 15th Innovations in Theoretical Computer Science Conference (ITCS 2024)

Abstract
We consider the question of approximating Max 2-CSP where each variable appears in at most d constraints (but with possibly arbitrarily large alphabet). There is a simple ((d+1)/2)-approximation algorithm for the problem. We prove the following results for any sufficiently large d: - Assuming the Unique Games Conjecture (UGC), it is NP-hard (under randomized reduction) to approximate this problem to within a factor of (d/2 - o(d)). - It is NP-hard (under randomized reduction) to approximate the problem to within a factor of (d/3 - o(d)). Thanks to a known connection [Pavel Dvorák et al., 2023], we establish the following hardness results for approximating Maximum Independent Set on k-claw-free graphs: - Assuming the Unique Games Conjecture (UGC), it is NP-hard (under randomized reduction) to approximate this problem to within a factor of (k/4 - o(k)). - It is NP-hard (under randomized reduction) to approximate the problem to within a factor of (k/(3 + 2√2) - o(k)) ≥ (k/(5.829) - o(k)). In comparison, known approximation algorithms achieve (k/2 - o(k))-approximation in polynomial time [Meike Neuwohner, 2021; Theophile Thiery and Justin Ward, 2023] and (k/3 + o(k))-approximation in quasi-polynomial time [Marek Cygan et al., 2013].
Cite as

Euiwoong Lee and Pasin Manurangsi. Hardness of Approximating Bounded-Degree Max 2-CSP and Independent Set on k-Claw-Free Graphs. In 15th Innovations in Theoretical Computer Science Conference (ITCS 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 287, pp. 71:1-71:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)

Copy BibTex To Clipboard

@InProceedings{lee_et_al:LIPIcs.ITCS.2024.71,
  author =	{Lee, Euiwoong and Manurangsi, Pasin},
  title =	{{Hardness of Approximating Bounded-Degree Max 2-CSP and Independent Set on k-Claw-Free Graphs}},
  booktitle =	{15th Innovations in Theoretical Computer Science Conference (ITCS 2024)},
  pages =	{71:1--71:17},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-309-6},
  ISSN =	{1868-8969},
  year =	{2024},
  volume =	{287},
  editor =	{Guruswami, Venkatesan},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ITCS.2024.71},
  URN =		{urn:nbn:de:0030-drops-195996},
  doi =		{10.4230/LIPIcs.ITCS.2024.71},
  annote =	{Keywords: Hardness of Approximation, Bounded Degree, Constraint Satisfaction Problems, Independent Set}
}
Document
DOI: 10.4230/LIPIcs.ISAAC.2023.14
Improved Guarantees for the a Priori TSP

Authors: Jannis Blauth, Meike Neuwohner, Luise Puhlmann, and Jens Vygen

Published in: LIPIcs, Volume 283, 34th International Symposium on Algorithms and Computation (ISAAC 2023)

Abstract
We revisit the a priori TSP (with independent activation) and prove stronger approximation guarantees than were previously known. In the a priori TSP, we are given a metric space (V,c) and an activation probability p(v) for each customer v ∈ V. We ask for a TSP tour T for V that minimizes the expected length after cutting T short by skipping the inactive customers. All known approximation algorithms select a nonempty subset S of the customers and construct a master route solution, consisting of a TSP tour for S and two edges connecting every customer v ∈ V⧵S to a nearest customer in S. We address the following questions. If we randomly sample the subset S, what should be the sampling probabilities? How much worse than the optimum can the best master route solution be? The answers to these questions (we provide almost matching lower and upper bounds) lead to improved approximation guarantees: less than 3.1 with randomized sampling, and less than 5.9 with a deterministic polynomial-time algorithm.
Cite as

Jannis Blauth, Meike Neuwohner, Luise Puhlmann, and Jens Vygen. Improved Guarantees for the a Priori TSP. In 34th International Symposium on Algorithms and Computation (ISAAC 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 283, pp. 14:1-14:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)

Copy BibTex To Clipboard

@InProceedings{blauth_et_al:LIPIcs.ISAAC.2023.14,
  author =	{Blauth, Jannis and Neuwohner, Meike and Puhlmann, Luise and Vygen, Jens},
  title =	{{Improved Guarantees for the a Priori TSP}},
  booktitle =	{34th International Symposium on Algorithms and Computation (ISAAC 2023)},
  pages =	{14:1--14:16},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-289-1},
  ISSN =	{1868-8969},
  year =	{2023},
  volume =	{283},
  editor =	{Iwata, Satoru and Kakimura, Naonori},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ISAAC.2023.14},
  URN =		{urn:nbn:de:0030-drops-193161},
  doi =		{10.4230/LIPIcs.ISAAC.2023.14},
  annote =	{Keywords: A priori TSP, random sampling, stochastic combinatorial optimization}
}
Document
DOI: 10.4230/LIPIcs.ESA.2022.80
The Pareto Cover Problem

Authors: Bento Natura, Meike Neuwohner, and Stefan Weltge

Published in: LIPIcs, Volume 244, 30th Annual European Symposium on Algorithms (ESA 2022)

Abstract
We introduce the problem of finding a set B of k points in [0,1]ⁿ such that the expected cost of the cheapest point in B that dominates a random point from [0,1]ⁿ is minimized. We study the case where the coordinates of the random points are independently distributed and the cost function is linear. This problem arises naturally in various application areas where customers' requests are satisfied based on predefined products, each corresponding to a subset of features. We show that the problem is NP-hard already for k = 2 when each coordinate is drawn from {0,1}, and obtain an FPTAS for general fixed k under mild assumptions on the distributions.
Cite as

Bento Natura, Meike Neuwohner, and Stefan Weltge. The Pareto Cover Problem. In 30th Annual European Symposium on Algorithms (ESA 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 244, pp. 80:1-80:12, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)

Copy BibTex To Clipboard

@InProceedings{natura_et_al:LIPIcs.ESA.2022.80,
  author =	{Natura, Bento and Neuwohner, Meike and Weltge, Stefan},
  title =	{{The Pareto Cover Problem}},
  booktitle =	{30th Annual European Symposium on Algorithms (ESA 2022)},
  pages =	{80:1--80:12},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-247-1},
  ISSN =	{1868-8969},
  year =	{2022},
  volume =	{244},
  editor =	{Chechik, Shiri and Navarro, Gonzalo and Rotenberg, Eva 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.2022.80},
  URN =		{urn:nbn:de:0030-drops-170186},
  doi =		{10.4230/LIPIcs.ESA.2022.80},
  annote =	{Keywords: Pareto, Covering, Optimization, Approximation Algorithm}
}
Document
DOI: 10.4230/LIPIcs.STACS.2021.53
An Improved Approximation Algorithm for the Maximum Weight Independent Set Problem in d-Claw Free Graphs

Authors: Meike Neuwohner

Published in: LIPIcs, Volume 187, 38th International Symposium on Theoretical Aspects of Computer Science (STACS 2021)

Abstract
In this paper, we consider the task of computing an independent set of maximum weight in a given d-claw free graph G = (V,E) equipped with a positive weight function w:V → ℝ^+. Thereby, d ≥ 2 is considered a constant. The previously best known approximation algorithm for this problem is the local improvement algorithm SquareImp proposed by Berman [Berman, 2000]. It achieves a performance ratio of d/2+ε in time 𝒪(|V(G)|^(d+1)⋅(|V(G)|+|E(G)|)⋅(d-1)²⋅ (d/(2ε)+1)²) for any ε > 0, which has remained unimproved for the last twenty years. By considering a broader class of local improvements, we obtain an approximation ratio of d/2-(1/63,700,992)+ε for any ε > 0 at the cost of an additional factor of 𝒪(|V(G)|^(d-1)²) in the running time. In particular, our result implies a polynomial time d/2-approximation algorithm. Furthermore, the well-known reduction from the weighted k-Set Packing Problem to the Maximum Weight Independent Set Problem in k+1-claw free graphs provides a (k+1)/2 -(1/63,700,992)+ε-approximation algorithm for the weighted k-Set Packing Problem for any ε > 0. This improves on the previously best known approximation guarantee of (k+1)/2 + ε originating from the result of Berman [Berman, 2000].
Cite as

Meike Neuwohner. An Improved Approximation Algorithm for the Maximum Weight Independent Set Problem in d-Claw Free Graphs. In 38th International Symposium on Theoretical Aspects of Computer Science (STACS 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 187, pp. 53:1-53:20, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)

Copy BibTex To Clipboard

@InProceedings{neuwohner:LIPIcs.STACS.2021.53,
  author =	{Neuwohner, Meike},
  title =	{{An Improved Approximation Algorithm for the Maximum Weight Independent Set Problem in d-Claw Free Graphs}},
  booktitle =	{38th International Symposium on Theoretical Aspects of Computer Science (STACS 2021)},
  pages =	{53:1--53:20},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-180-1},
  ISSN =	{1868-8969},
  year =	{2021},
  volume =	{187},
  editor =	{Bl\"{a}ser, Markus and Monmege, Benjamin},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2021.53},
  URN =		{urn:nbn:de:0030-drops-136982},
  doi =		{10.4230/LIPIcs.STACS.2021.53},
  annote =	{Keywords: d-Claw free Graphs, independent Set, local Improvement, k-Set Packing, weighted}
}
  • Refine by Type
  • 5 Document/PDF
  • 1 Document/HTML

  • Refine by Publication Year
  • 1 2025
  • 1 2024
  • 1 2023
  • 1 2022
  • 1 2021

  • Refine by Author
  • 3 Neuwohner, Meike
  • 1 Blauth, Jannis
  • 1 Ferdous, S M
  • 1 Lee, Euiwoong
  • 1 Manurangsi, Pasin
  • Show More...

  • Refine by Series/Journal
  • 5 LIPIcs

  • Refine by Classification
  • 2 Theory of computation → Approximation algorithms analysis
  • 2 Theory of computation → Packing and covering problems
  • 2 Theory of computation → Problems, reductions and completeness
  • 1 Mathematics of computing → Discrete optimization
  • 1 Mathematics of computing → Graph algorithms
  • Show More...

  • Refine by Keyword
  • 1 A priori TSP
  • 1 Approximation Algorithm
  • 1 Bounded Degree
  • 1 Constraint Satisfaction Problems
  • 1 Covering
  • 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