The Budgeted Maximum Coverage Problem

By Samir Khuller, A. Moss, Joseph (Seffi) Naor. 1999

Subfields: Mathematical Optimization, Algorithms & Complexity

How researchers see this paper

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

In Mathematical Optimization

In Algorithms & Complexity

Citations in the corpus

"How do I fool you?": Manipulating User Trust via Misleading Black Box Explanations (2019, neutral): “Exactly solving this problem is NP-Hard [7].”
Interpretable Decision Sets: A Joint Framework for Description and Prediction (2016, background): “Since our objective is to maximize a submodular function, an NP-hard problem [18], we will approximate the solution.”
An Improved Approximation for k-Median and Positive Correlation in Budgeted Optimization (2014, unknown): “We consider two notions in combinatorial optimization: a concrete problem (the classical k-median problem) and a formulation of new types of distributions (generalizations of dependent-rounding techniques); the breakthrough of Li & Svensson on the former [24] uses special cases of the latter.”
Stop-and-Stare: Optimal Sampling Algorithms for Viral Marketing in Billion-scale Networks (2016, methodology): “• Use the greedy algorithm for the Max-coverage problem [28] to find a seed set Ŝk that covers the maximum number of RR sets and return Ŝk as the solution.”
Data Collection and Wireless Communication in Internet of Things (IoT) Using Economic Analysis and Pricing Models: A Survey (2016, methodology): “Maximum Coverage (GBMC) algorithm in [120] to guarantee that the number of selected winners (thus the incentive cost) is minimum while still achieving the same sensing coverage as in [113].”
A Class of Submodular Functions for Document Summarization (2011, background): “In (Lin and Bilmes, 2010), we generalize the work by Khuller et al. (1999) on the budgeted maximum cover problem to the general submodular framework, and show a practical greedy algorithm with a (1 − 1 / √ e ) -approximation factor, where each greedy step adds the unit with the largest ratio of…”
A Note on the Budgeted Maximization of Submodular Functions (2005, methodology): “[2] prove that the simple greedy algorithm with this greedy selection rule has unbounded approximation ratio.”
Fast algorithms for maximizing submodular functions (2014, methodology): “The n(5)-time algorithm from [32, 19] works as follows.”
Faithful and Customizable Explanations of Black Box Models (2019, background): “1 is NP-Hard (Khuller, Moss, and Naor 1999), the specific properties of the problem: non-monotonicity, submodularity, non-normality, non-negativity and the accompanying matroid constraints allow for applying algorithms with provable optimality guarantees.”
How to crowdsource tasks truthfully without sacrificing utility: Online incentive mechanisms with budget constraint (2014, background): “Note that in the line 17, 𝑝 𝑖 is the price paid for user 𝑖 in the previous stage instead of the current stage, so it cannot lead to the overrun of the current stage-budget.”
Influence Maximization on Social Graphs: A Survey (2018, unknown): “Although this approach could provide arbitrary bad solutions, comparing it with the solution returned by running na € ıve greedy selection until the cost has been exhausted (treating the cost for each node is 1) yields a ð 1 (cid:8) 1 e Þ (cid:8) " approximation ratio [3], [50], [51].”
Learning diverse rankings with multi-armed bandits (2008, methodology): “DTIME n(Khuller et al., 1997).”
Incentives for Mobile Crowd Sensing: A Survey (2016, methodology): “Thus they combine RADP with Recruitment mechanism (RADPVPC-RC) [55] and the Greedy Budgeted Maximum Coverage (GBMC) [59] to create a new Greedy Incentive Algorithm (GIA).”
Submodular Maximization with Cardinality Constraints (2014, methodology): “This problem captures several well known optimization problems including Max-k-Coverage [15] [34], Max-Bisection [5] [24], and several variants of Max-Cut in which the cut size is prespecified: undirected graphs [3] [17], directed graphs [2] and hypergraphs [4].”
A Unified Continuous Greedy Algorithm for Submodular Maximization (2011, unknown): “Two such well studied problems are Max-Cut and Maxk-Cover [22], [23], [26], [28], [29], [31], [40], [41], [46].”
Near-optimal Nonmyopic Value of Information in Graphical Models (2005, background): “The following observation identifies the joint entropy as a special case of our setting: Corollary 3.”
Max-cover in map-reduce (2010, background): “Khuller, Moss, and Naor [21] extended the Greedy algorithm to the budgeted case, maintaining the same approximation guarantee.”