Greedy Heuristics and Linear Relaxations for the Random Hitting Set Problem
OPEN ACCESS
Loading...
Author / Producer
Date
2023-05-09
Publication Type
Working Paper
ETH Bibliography
yes
Citations
Altmetric
OPEN ACCESS
Data
Rights / License
Abstract
Consider the Hitting Set problem where, for a given universe $\mathcal{X} = \left\{ 1, ... , n \right\}$ and a collection of subsets $\mathcal{S}_1, ... , \mathcal{S}_m$, one seeks to identify the smallest subset of $\mathcal{X}$ which has 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 with probability $p$, independently of one another. For large enough values of $n$, we rigorously analyse the average case performance of Lovász's celebrated greedy algorithm (Lovász, 1975) with respect to the chosen input distribution. In addition, we study integrality gaps between linear programming and integer programming solutions of the problem.
Permanent link
Publication status
published
Editor
Book title
Journal / series
Volume
Pages / Article No.
2305.05565
Publisher
Cornell University
Event
Edition / version
v1
Methods
Software
Geographic location
Date collected
Date created
Subject
Probability (math.PR); Discrete Mathematics (cs.DM); Data Structures and Algorithms (cs.DS); Optimization and Control (math.OC); FOS: Mathematics; FOS: Computer and information sciences
Organisational unit
09679 - Bandeira, Afonso / Bandeira, Afonso
09652 - Yang, Fan / Yang, Fan
02219 - ETH AI Center / ETH AI Center