The budgeted maximum coverage problem
From MaRDI portal
Publication:1606925
DOI10.1016/S0020-0190(99)00031-9zbMath1002.68203MaRDI QIDQ1606925
Joseph (Seffi) Naor, Anna Moss, Samir Khuller
Publication date: 25 July 2002
Published in: Information Processing Letters (Search for Journal in Brave)
68W40: Analysis of algorithms
68Q17: Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.)
68W25: Approximation algorithms
Related Items
Constrained Submodular Maximization via a Nonsymmetric Technique, Unnamed Item, Analyzing the Optimal Neighborhood: Algorithms for Partial and Budgeted Connected Dominating Set Problems, An approximation algorithm for maximum weight budgeted connected set cover, Maximum entropy models and subjective interestingness: an application to tiles in binary databases, On the inapproximability of maximum intersection problems, On the computational complexity of measuring global stability of banking networks, A note on the clustered set covering problem, Maximizing a submodular function with viability constraints, Video distribution under multiple constraints, Approximation and hardness results for label cut and related problems, An improved approximation algorithm for the most points covering problem, Performance bounds with curvature for batched greedy optimization, Flow intercepting facility location: Problems, models and heuristics, Multiple voting location and single voting location on trees, The generalized maximum coverage problem, Algorithms for storage allocation based on client preferences, An \(O(n(\log n)^{2}/\log \log n)\) algorithm for the single maximum coverage location or the \((1,X_p)\)-medianoid problem on trees, On approximating four covering and packing problems, A note on maximizing a submodular set function subject to a knapsack constraint, Maximum coverage problem with group budget constraints, Welfare maximization with friends-of-friends network externalities, Simpler and better approximation algorithms for the unweighted minimum label \(s\)-\(t\) cut problem, Recommending links through influence maximization, Exploiting submodularity to quantify near-optimality in multi-agent coverage problems, A two-stage stochastic programming approach for influence maximization in social networks, Maximizing misinformation restriction within time and budget constraints, A continuous knapsack problem with separable convex utilities: approximation algorithms and applications, The knapsack problem with neighbour constraints, Maximum subset intersection, Critical nodes in interdependent networks with deterministic and probabilistic cascading failures, On the fuzzy maximal covering location problem, Constrained submodular maximization via greedy local search, Better streaming algorithms for the maximum coverage problem, Approximation algorithms for the geometric firefighter and budget fence problems, Problems and algorithms for covering arrays via set covers, The parameterized complexity of unique coverage and its variants, Aerial vehicle search-path optimization: a novel method for emergency operations, Optimization with demand oracles, Approximation algorithms and hardness results for labeled connectivity problems, A note on the set union knapsack problem, Cut problems in graphs with a budget constraint, A two-phase greedy algorithm to locate and allocate hubs for fixed-wireless broadband access, Bounded-hops power assignment in ad hoc wireless networks, TOWARDS MORE EFFICIENT INFECTION AND FIRE FIGHTING, Approximation of the Clustered Set Covering Problem, Discrete Stochastic Submodular Maximization: Adaptive vs. Non-adaptive vs. Offline, Tight Approximation Bounds for the Seminar Assignment Problem, Maximum Betweenness Centrality: Approximability and Tractable Cases, The Budgeted Unique Coverage Problem and Color-Coding, Online Allocation and Pricing with Economies of Scale, Bicriteria Approximation Tradeoff for the Node-Cost Budget Problem
