DROPS

Document

Track A: Algorithms, Complexity and Games

DOI: 10.4230/LIPIcs.ICALP.2026.29

A 4.509-Approximation Algorithm for Generalized Min Sum Set Cover

Authors: Amey Bhangale and Yezhou Zhang

Published in: LIPIcs, Volume 374, 53rd International Colloquium on Automata, Languages, and Programming (ICALP 2026)

Abstract

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.

Cite as

Amey Bhangale and Yezhou Zhang. A 4.509-Approximation Algorithm for Generalized Min Sum Set Cover. In 53rd International Colloquium on Automata, Languages, and Programming (ICALP 2026). Leibniz International Proceedings in Informatics (LIPIcs), Volume 374, pp. 29:1-29:22, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2026)

Copy BibTex To Clipboard

@InProceedings{bhangale_et_al:LIPIcs.ICALP.2026.29,
  author =	{Bhangale, Amey and Zhang, Yezhou},
  title =	{{A 4.509-Approximation Algorithm for Generalized Min Sum Set Cover}},
  booktitle =	{53rd International Colloquium on Automata, Languages, and Programming (ICALP 2026)},
  pages =	{29:1--29:22},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-428-4},
  ISSN =	{1868-8969},
  year =	{2026},
  volume =	{374},
  editor =	{Bhattacharya, Sayan and Nanongkai, Danupon and Benedikt, Michael and Puppis, Gabriele},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2026.29},
  URN =		{urn:nbn:de:0030-drops-264185},
  doi =		{10.4230/LIPIcs.ICALP.2026.29},
  annote =	{Keywords: Generalized Min Sum Set Cover, Approximation Algorithm, Min latency set cover, Linear programming, Knapsack cover inequalities}
}

Document

Track A: Algorithms, Complexity and Games

DOI: 10.4230/LIPIcs.ICALP.2026.30

Optimal Inapproximability of Generalized Linear Equations over a Finite Group

Authors: Amey Bhangale and Yezhou Zhang

Published in: LIPIcs, Volume 374, 53rd International Colloquium on Automata, Languages, and Programming (ICALP 2026)

Abstract

Constraint satisfaction problems (CSPs) consist of a set of variables taking values from some finite domain and a set of local constraints on these variables. The objective is to find an assignment to the variables that maximizes the fraction of satisfied constraints. In this work, we study the CSP where the constraints are generalized linear equations over a finite group G. More specifically, for a given S ⊆ G, the constraints in this CSP are of the form addition of the values to the variables (similarly, product for non-abelian groups) belongs to the set S. We give an approximation algorithm for this problem on satisfiable instances and show that it is optimal for certain S assuming 𝐏≠ NP. This natural predicate is one of the very few known predicates that are approximation resistant on almost satisfiable instances, assuming 𝐏≠ NP, but admits a non-trivial approximation algorithm on satisfiable instances.

Cite as

Amey Bhangale and Yezhou Zhang. Optimal Inapproximability of Generalized Linear Equations over a Finite Group. In 53rd International Colloquium on Automata, Languages, and Programming (ICALP 2026). Leibniz International Proceedings in Informatics (LIPIcs), Volume 374, pp. 30:1-30:23, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2026)

Copy BibTex To Clipboard

@InProceedings{bhangale_et_al:LIPIcs.ICALP.2026.30,
  author =	{Bhangale, Amey and Zhang, Yezhou},
  title =	{{Optimal Inapproximability of Generalized Linear Equations over a Finite Group}},
  booktitle =	{53rd International Colloquium on Automata, Languages, and Programming (ICALP 2026)},
  pages =	{30:1--30:23},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-428-4},
  ISSN =	{1868-8969},
  year =	{2026},
  volume =	{374},
  editor =	{Bhattacharya, Sayan and Nanongkai, Danupon and Benedikt, Michael and Puppis, Gabriele},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2026.30},
  URN =		{urn:nbn:de:0030-drops-264193},
  doi =		{10.4230/LIPIcs.ICALP.2026.30},
  annote =	{Keywords: Constraint satisfaction problems, inapproximability, approximation algorithms, non-abelian groups, Fourier analysis}
}

Search Results

Documents authored by Zhang, Yezhou

A 4.509-Approximation Algorithm for Generalized Min Sum Set Cover

Abstract

Cite as

Optimal Inapproximability of Generalized Linear Equations over a Finite Group

Abstract

Cite as

Thanks for your feedback!

Could not send message