The budgeted maximum coverage problem
From MaRDI portal
Publication:1606925
DOI10.1016/S0020-0190(99)00031-9zbMath1002.68203OpenAlexW2080379754MaRDI QIDQ1606925
Joseph (Seffi) Naor, Anna Moss, Samir Khuller
Publication date: 25 July 2002
Published in: Information Processing Letters (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1016/s0020-0190(99)00031-9
Analysis of algorithms (68W40) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Approximation algorithms (68W25)
Related Items (only showing first 100 items - show all)
Approximation algorithms for the maximum vertex coverage problem on bounded degree graphs ⋮ Approximation of the Clustered Set Covering Problem ⋮ Submodular Maximization Subject to a Knapsack Constraint Under Noise Models ⋮ An approximation algorithm for maximum weight budgeted connected set cover ⋮ Improved Budgeted Connected Domination and Budgeted Edge-Vertex Domination ⋮ Parameterized Algorithms for Partial Vertex Covers in Bipartite Graphs ⋮ On the Parameterized Complexity of the Expected Coverage Problem ⋮ Approximations for restrictions of the budgeted and generalized maximum coverage problems ⋮ On the parameterized complexity of the expected coverage problem ⋮ Dual domination problems in graphs ⋮ Flow intercepting facility location: Problems, models and heuristics ⋮ A new greedy strategy for maximizing monotone submodular function under a cardinality constraint ⋮ Online Allocation and Pricing with Economies of Scale ⋮ Maximizing a non-decreasing non-submodular function subject to various types of constraints ⋮ The parameterized complexity of unique coverage and its variants ⋮ Aerial vehicle search-path optimization: a novel method for emergency operations ⋮ Algorithms for covering multiple submodular constraints and applications ⋮ Gaussian downlink user selection subject to access limit, power budget, and rate demands ⋮ On the fixed-parameter tractability of the partial vertex cover problem with a matching constraint in edge-weighted bipartite graphs ⋮ Multiple voting location and single voting location on trees ⋮ Fast Adaptive Non-Monotone Submodular Maximization Subject to a Knapsack Constraint ⋮ Maximum coverage problem with group budget constraints ⋮ Discrete Stochastic Submodular Maximization: Adaptive vs. Non-adaptive vs. Offline ⋮ Optimization with demand oracles ⋮ Parallel algorithms for minimum general partial dominating set and maximum budgeted dominating set in unit disk graph ⋮ The knapsack problem with neighbour constraints ⋮ Improved approximation algorithms for \(k\)-submodular maximization under a knapsack constraint ⋮ A fast and deterministic algorithm for knapsack-constrained monotone DR-submodular maximization over an integer lattice ⋮ Simple and efficient budget feasible mechanisms for monotone submodular valuations ⋮ Maximum entropy models and subjective interestingness: an application to tiles in binary databases ⋮ Maximization of nonsubmodular functions under multiple constraints with applications ⋮ Constrained Submodular Maximization via a Nonsymmetric Technique ⋮ Welfare maximization with friends-of-friends network externalities ⋮ Improved deterministic algorithms for non-monotone submodular maximization ⋮ Approximation algorithms and hardness results for labeled connectivity problems ⋮ On the partial vertex cover problem in bipartite graphs -- a parameterized perspective ⋮ Submodular optimization problems and greedy strategies: a survey ⋮ Streaming submodular maximization with the chance constraint ⋮ Bicriteria Approximation Tradeoff for the Node-Cost Budget Problem ⋮ Approximation and hardness results for label cut and related problems ⋮ Maximum subset intersection ⋮ Unnamed Item ⋮ Optimizing node discovery on networks: problem definitions, fast algorithms, and observations ⋮ Simpler and better approximation algorithms for the unweighted minimum label \(s\)-\(t\) cut problem ⋮ The multi-budget maximum weighted coverage problem ⋮ A simple deterministic algorithm for symmetric submodular maximization subject to a knapsack constraint ⋮ Tight Approximation Bounds for the Seminar Assignment Problem ⋮ Practical budgeted submodular maximization ⋮ Introducing time series snippets: a new primitive for summarizing long time series ⋮ On the inapproximability of maximum intersection problems ⋮ A note on the set union knapsack problem ⋮ Maximize a monotone function with a generic submodularity ratio ⋮ Improved budgeted connected domination and budgeted edge-vertex domination ⋮ A note on maximizing a submodular set function subject to a knapsack constraint ⋮ Recommending links through influence maximization ⋮ Cut problems in graphs with a budget constraint ⋮ On the computational complexity of measuring global stability of banking networks ⋮ A (1-e^{-1}-ε)-Approximation for the Monotone Submodular Multiple Knapsack Problem ⋮ Exploiting submodularity to quantify near-optimality in multi-agent coverage problems ⋮ Online budgeted maximum coverage ⋮ A note on the clustered set covering problem ⋮ Minimizing the Spread of Rumor Within Budget Constraint in Online Network ⋮ A two-stage stochastic programming approach for influence maximization in social networks ⋮ Maximizing a submodular function with viability constraints ⋮ Maximizing misinformation restriction within time and budget constraints ⋮ An improved approximation algorithm for the most points covering problem ⋮ The generalized maximum coverage problem ⋮ A two-phase greedy algorithm to locate and allocate hubs for fixed-wireless broadband access ⋮ Video distribution under multiple constraints ⋮ 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 ⋮ Bounded-hops power assignment in ad hoc wireless networks ⋮ Critical nodes in interdependent networks with deterministic and probabilistic cascading failures ⋮ Non-monotone submodular function maximization under \(k\)-system constraint ⋮ A continuous knapsack problem with separable convex utilities: approximation algorithms and applications ⋮ Performance bounds with curvature for batched greedy optimization ⋮ On the fuzzy maximal covering location problem ⋮ Analyzing the Optimal Neighborhood: Algorithms for Partial and Budgeted Connected Dominating Set Problems ⋮ Constrained submodular maximization via greedy local search ⋮ Unnamed Item ⋮ Maximum Betweenness Centrality: Approximability and Tractable Cases ⋮ Generalized budgeted submodular set function maximization ⋮ On approximating four covering and packing problems ⋮ A refined analysis of submodular greedy ⋮ Pareto optimization for subset selection with dynamic cost constraints ⋮ A Nearly-Linear Time Algorithm for Submodular Maximization with a Knapsack Constraint ⋮ The Budgeted Unique Coverage Problem and Color-Coding ⋮ A Tight Approximation for Submodular Maximization with Mixed Packing and Covering Constraints ⋮ An almost optimal approximation algorithm for monotone submodular multiple knapsack ⋮ Partial Vertex Cover and Budgeted Maximum Coverage in Bipartite Graphs ⋮ Better streaming algorithms for the maximum coverage problem ⋮ TOWARDS MORE EFFICIENT INFECTION AND FIRE FIGHTING ⋮ Data source selection for approximate query ⋮ On Partial Covering For Geometric Set Systems ⋮ Approximation algorithms for the geometric firefighter and budget fence problems ⋮ Problems and algorithms for covering arrays via set covers ⋮ Online algorithms for the maximum \(k\)-interval coverage problem ⋮ Parameter Estimation in Epidemic Spread Networks Using Limited Measurements ⋮ Maximum coverage with cluster constraints: an LP-based approximation technique ⋮ Improved deterministic algorithms for non-monotone submodular maximization
This page was built for publication: The budgeted maximum coverage problem
