Tight approximation bounds for maximum multi-coverage

• 成果类型: Article
• 署名作者: Barman, Siddharth; Fawzi, Omar; Ghoshal, Suprovat; Gurpinar, Emirhan
• 署名单位: Indian Institute of Science (IISC) - Bangalore; Ecole Normale Superieure de Lyon (ENS de LYON); Inria; Centre National de la Recherche Scientifique (CNRS)
• 刊物名称: MATHEMATICAL PROGRAMMING
• ISSN/ISSBN: 0025-5610
• DOI: 10.1007/s10107-021-01677-4
• 发表日期: 2022
• 页码: 443-476
• 关键词: function subject; algorithms

摘要

In the classic maximum coverage problem, we are given subsets T-1,..., T-m of a universe [n] along with an integer k and the objective is to find a subset S subset of [m] of size k that maximizes C(S) := vertical bar boolean OR(i is an element of S) T-i vertical bar. It is well-known that the greedy algorithm for this problem achieves an approximation ratio of (1- e(-1)) and there is a matching inapproximability result. We note that in themaximum coverage problem if an element e is an element of [n] is covered by several sets, it is still counted only once. By contrast, if we change the problem and count each element e as many times as it is covered, then we obtain a linear objective function, C-(infinity)(S) = Sigma(i is an element of S) vertical bar T-i vertical bar, which can be easily maximized under a cardinality constraint. We study the maximum l-multi-coverage problem which naturally interpolates between these two extremes. In this problem, an element can be counted up to l times but no more; hence, we consider maximizing the function C-(l)( S) = Sigma(e is an element of[n]) min{l, |{i is an element of S : e is an element of T-i}|}, subject to the constraint vertical bar S vertical bar <= k. Note that the case of l = 1 corresponds to the standard maximum coverage setting and l =infinity gives us a linear objective. We develop an efficient approximation algorithm that achieves an approximation ratio of 1 - l(l)e-l/l(l) for the l-multi-coverage problem. In particular, when l = 2, this factor is 1 - 2e(-2) approximate to 0.73 and as l grows the approximation ratio behaves as 1 - 1/root 2 pi l. We also prove that this approximation ratio is tight, i.e., establish a matching hardness-of-approximation result, under the Unique Games Conjecture. This problem is motivated by the question of finding a code that optimizes the list-decoding success probability for a given noisy channel. We show how the multi-coverage problem can be relevant in other contexts, such as