A threshold of ln n for approximating set cover (preliminary version)

By Uriel Feige. 1996

Given a collection<inline-equation><f> <sc>F</sc></f></inline-equation> of subsets of <?Pub Fmt italic>S<?Pub Fmt /italic> ={1,…,<?Pub Fmt italic>n<?Pub Fmt /italic>}, <?Pub Fmt italic>setcover<?Pub Fmt /italic> is the problem of selecting as few as possiblesubsets from <inline-equation> <f> <sc>F</sc></f></inline-equation> such that their union covers<?Pub Fmt italic>S,<?Pub Fmt /italic>, and <?Pub Fmt italic>maxk-cover<?Pub Fmt /italic> is the problem of selecting<?Pub Fmt italic>k<?Pub Fmt /italic> subsets from<inline-equation> <f> <sc>F</sc></f></inline-equation> such that their union has maximum cardinality. Both these problems areNP-hard. We prove that (1 - <?Pub Fmt italic>o<?Pub Fmt /italic>(1)) ln<?Pub Fmt italic>n<?Pub Fmt /italic> is a threshold below which setcover cannot be approximated efficiently, unless NP has slightlysuperpolynomial time algorithms. This closes the gap (up to low-orderterms) between the ratio of approximation achievable by the greedyalogorithm (which is (1 - <?Pub Fmt italic>o<?Pub Fmt /italic>(1)) lnn), and provious results of Lund and Yanakakis, that showed hardness ofapproximation within a ratio of <inline-equation><f><fen lp="par"><lim align="r"><op><rf>log</rf></op><ll>2</ll></lim>n<rp post="par"></fen>/2≃0.72</f></inline-equation> ln <?Pub Fmt italic>n<?Pub Fmt /italic>. For max<?Pub Fmt italic>k<?Pub Fmt /italic>-cover, we show an approximationthreshold of (1 - 1/<?Pub Fmt italic>e<?Pub Fmt /italic>)(up tolow-order terms), under assumption that <inline-equation><f>P≠NP</f><?Pub Caret></inline-equation>.

Subfields: Optimization & Training

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Optimization & Training

Citations in the corpus

FastText.zip: Compressing text classification models (2016, background): “This problem is directly related to set covering problems that are NP-hard (Feige, 1998).”
Machine Teaching: An Inverse Problem to Machine Learning and an Approach Toward Optimal Education (2015, methodology): “Discrete optimization methods, such as those based on submodularity, may be applicable here (Krause and Golovin 2014; Iyer and Bilmes 2013; Bach 2013; Feige 1998; Krause and Guestrin 2005; Nemhauser, Wolsey, and Fisher 1978).”
An Interpretable Model with Globally Consistent Explanations for Credit Risk (2018, methodology): “This is an instance of the Minimal Set Cover Problem [3, 2].”
Determinantal Point Processes for Machine Learning (2012, background): “…can be minimized in polynomial time [Schrijver, 2000], and many results exist for approximately maximizing monotone submodular functions, which have the special property that supersets always have higher function values than their subsets [Nemhauser et al., 1978, Fisher et al., 1978, Feige, 1998].”
Learning with Submodular Functions: A Convex Optimization Perspective (2011, background): “It has an (1−1/e)-performance guarantee [111] (note that this guarantee cannot be improved in general, as it cannot for set cover, see [44]):”
Streaming Weak Submodularity: Interpreting Neural Networks on the Fly (2017, background): “In general, no polynomial-time algorithm can have a better approximation ratio even for a uniform matroid constraint [Nemhauser andWolsey, 1978; Feige, 1998].”
Maximizing the spread of influence through a social network (2003, background): “It is useful to think of the triggering sets in terms of “live” and “blocked” edges: if node u belongs to the triggering set T v of v , then we declare the edge ( u; v ) to be live, and otherwise we declare it to be blocked.”
Non-monotone submodular maximization under matroid and knapsack constraints (2009, background): “This problem appears in many important optimization problems including cuts in graphs [19, 42, 26], rank function of matroids [12, 16], set covering problems [13], plant location problems [9, 10, 11, 2], certain satisfiability problems [25, 14], and maximum entropy sampling [32, 33].”
A note on maximizing a submodular set function subject to a knapsack constraint (2004, background): “This is the best possible performance guarantee achievable in polynomial time, unless P = NP [1], even in the case when ci = 1, for all i ∈ I.”
Admission control to minimize rejections and online set cover with repetitions (2005, background): “The offline version of the set cover problem is a classic NP-hard problem that was studied extensively, and the best approximation factor achievable for it in polynomial time (assuming P = NP ) is Θ(logn) [12, 13].”
Hanabi is NP-complete, Even for Cheaters who Look at Their Cards (2016, background): “Finding an assignment that satisﬁes such an instance is known to be NP-complete even for κ = 5 [13].”
Some optimal inapproximability results (2001, methodology): “It has later been established [Feige 1998] that we can make each variable appear exactly 5 times even if we require each clause to be of length exactly 3.”
The Multiplicative Weights Update Method: a Meta-Algorithm and Applications (2012, methodology): “In fact, the algorithm can be simpliﬁed so it becomes exactly the classical greedy algorithm, and we obtain a ln n -approximation, which is best-possible for this problem up to constant factors (assuming reasonable complexity-theoretic conjectures [23]).”
Automatic Subspace Clustering of High Dimensional Data (2005, background): “For the general set cover problem , the best known algorithm for approximating the smallest set cover gives an approximation factor of ln n where n is the size of the universe being covered ( Feige , 1996 ; Lund and Yannakakis , 1993 ) .”
Finding Top-k Min-Cost Connected Trees in Databases (2007, background): “The lower bound of performance ratio is O(ln l) [14].”