DROPS

Document

APPROX

DOI: 10.4230/LIPIcs.APPROX/RANDOM.2024.30

Greedy Heuristics and Linear Relaxations for the Random Hitting Set Problem

Authors: Gabriel Arpino, Daniil Dmitriev, and Nicolo Grometto

Published in: LIPIcs, Volume 317, Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2024)

Abstract

Consider the Hitting Set problem where, for a given universe 𝒳 = {1, ..., n} and a collection of subsets 𝒮₁, ..., 𝒮_m, one seeks to identify the smallest subset of 𝒳 which has a nonempty intersection with every element in the collection. We study a probabilistic formulation of this problem, where the underlying subsets are formed by including each element of the universe independently with probability p. We rigorously analyze integrality gaps between linear programming and integer programming solutions to the problem. In particular, we prove the absence of an integrality gap in the sparse regime mp ≲ log(n) and the presence of a non-vanishing integrality gap in the dense regime mp ≫ log{n}. Moreover, for large enough values of n, we look at the performance of Lovász’s celebrated Greedy algorithm [Lovász, 1975] with respect to the chosen input distribution, and prove that it finds optimal solutions up to multiplicative constants. This highlights separation of Greedy performance between average-case and worst-case settings.

Cite as

Gabriel Arpino, Daniil Dmitriev, and Nicolo Grometto. Greedy Heuristics and Linear Relaxations for the Random Hitting Set Problem. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 317, pp. 30:1-30:22, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)

Copy BibTex To Clipboard

@InProceedings{arpino_et_al:LIPIcs.APPROX/RANDOM.2024.30,
  author =	{Arpino, Gabriel and Dmitriev, Daniil and Grometto, Nicolo},
  title =	{{Greedy Heuristics and Linear Relaxations for the Random Hitting Set Problem}},
  booktitle =	{Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2024)},
  pages =	{30:1--30:22},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-348-5},
  ISSN =	{1868-8969},
  year =	{2024},
  volume =	{317},
  editor =	{Kumar, Amit and Ron-Zewi, Noga},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.APPROX/RANDOM.2024.30},
  URN =		{urn:nbn:de:0030-drops-210234},
  doi =		{10.4230/LIPIcs.APPROX/RANDOM.2024.30},
  annote =	{Keywords: Hitting Set, Random Hypergraph, Integrality Gap, Greedy Algorithm}
}

Search Results

Documents authored by Dmitriev, Daniil

Greedy Heuristics and Linear Relaxations for the Random Hitting Set Problem

Abstract

Cite as

Thanks for your feedback!

Could not send message