2026-09-08T02:21:24Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:26418 2026-09-05T19:42:54Z ddc:004 open_access

A 4.509-Approximation Algorithm for Generalized Min Sum Set Cover Bhangale, Amey Zhang, Yezhou Generalized Min Sum Set Cover Approximation Algorithm Min latency set cover Linear programming Knapsack cover inequalities We study the generalized min-sum set cover (GMSSC) problem, where given a collection of hyperedges E with arbitrary covering requirements {k_e ∈ ℤ^+ : e ∈ E}, the objective is to find an ordering of the vertices that minimizes the total cover time of the hyperedges. A hyperedge e is considered covered at the first time when k_e of its vertices appear in the ordering. We present a 4.509-approximation algorithm for GMSSC, improving upon the previous best-known guarantee of 4.642 [Nikhil Bansal et al., 2021]. Our approach retains the general LP-based framework of Bansal, Batra, Farhadi, and Tetali [Nikhil Bansal et al., 2021] but provides an improved analysis that narrows the gap toward the lower bound of 4-approximation assuming P≠NP. Our analysis takes advantage of the constraints of the linear program in a nontrivial way, along with new lower-tail bounds for the sums of independent Bernoulli random variables, which could be of independent interest. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Amey Bhangale and Yezhou Zhang 2026 Is Part Of LIPIcs, Volume 374, 53rd International Colloquium on Automata, Languages, and Programming (ICALP 2026) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.ICALP.2026.29 urn:nbn:de:0030-drops-264185 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2026.29 eng https://creativecommons.org/licenses/by/4.0/legalcode