The budgeted maximum coverage problem

DOI10.1016/S0020-0190(99)00031-9zbMATH Open1002.68203OpenAlexW2080379754MaRDI QIDQ1606925FDOQ1606925

Authors: A. Moss, Joseph (Seffi) Naor, 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

Recommendations

Generalized budgeted submodular set function maximization
Improved greedy algorithm for maximum coverage problem with group budget constraints
scientific article; zbMATH DE number 6851883
scientific article; zbMATH DE number 1953104
Approximation algorithms for maximum coverage with group budget constraints

zbMATH Keywords

budgeted maximum coverage problem

Mathematics Subject Classification ID

Analysis of algorithms (68W40) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Approximation algorithms (68W25)

Cited In (only showing first 100 items - show all)

Approximation algorithms for the maximum vertex coverage problem on bounded degree graphs
Algorithms for covering multiple submodular constraints and applications
On partial covering for geometric set systems
The generalized maximum coverage problem
Recommending links through influence maximization
An improved approximation algorithm for the most points covering problem
Partial vertex cover and budgeted maximum coverage in bipartite graphs
On approximating four covering and packing problems
Exploiting submodularity to quantify near-optimality in multi-agent coverage problems
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
The Budgeted Unique Coverage Problem and Color-Coding
On the parameterized complexity of the expected coverage problem
Video distribution under multiple constraints
Pareto optimization for subset selection with dynamic cost constraints
An approximation algorithm for maximum weight budgeted connected set cover
Maximizing a non-decreasing non-submodular function subject to various types of constraints
Maximum betweenness centrality: approximability and tractable cases
A note on maximizing a submodular set function subject to a knapsack constraint
Multiple voting location and single voting location on trees
Approximation of the clustered set covering problem
The parameterized complexity of unique coverage and its variants
Maximizing misinformation restriction within time and budget constraints
Maximum weighted independent sets with a budget
Better streaming algorithms for the maximum coverage problem
Tight approximation bounds for maximum multi-coverage
Tight approximation bounds for maximum multi-coverage
Aerial vehicle search-path optimization: a novel method for emergency operations
Performance bounds with curvature for batched greedy optimization
Towards more efficient infection and fire fighting
Title not available (Why is that?)
Bounded-hops power assignment in ad hoc wireless networks
Combination Can Be Hard: Approximability of the Unique Coverage Problem
Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques
On the inapproximability of maximum intersection problems
Problems and algorithms for covering arrays via set covers
A two-stage stochastic programming approach for influence maximization in social networks
Flow intercepting facility location: Problems, models and heuristics
Maximum entropy models and subjective interestingness: an application to tiles in binary databases
The knapsack problem with neighbour constraints
Approximation algorithms for the geometric firefighter and budget fence problems
Maximum subset intersection
Welfare maximization with friends-of-friends network externalities
On the computational complexity of measuring global stability of banking networks
On the fuzzy maximal covering location problem
Maximum coverage problem with group budget constraints
A 6/5-approximation algorithm for the maximum 3-cover problem
Approximation algorithms for maximum coverage with group budget constraints
Improved greedy algorithm for maximum coverage problem with group budget constraints
Parameterized Algorithms for Partial Vertex Covers in Bipartite Graphs
Online algorithms for the maximum \(k\)-interval coverage problem
A refined analysis of submodular greedy
A note on the clustered set covering problem
A continuous knapsack problem with separable convex utilities: approximation algorithms and applications
Title not available (Why is that?)
Maximize a monotone function with a generic submodularity ratio
Approximations for restrictions of the budgeted and generalized maximum coverage problems
Cut problems in graphs with a budget constraint
Efficient approximation algorithms for maximum coverage with group budget constraints
Simpler and better approximation algorithms for the unweighted minimum label \(s\)-\(t\) cut problem
Title not available (Why is that?)
Approximation algorithms and hardness results for labeled connectivity problems
Online budgeted maximum coverage
Approximation and hardness results for label cut and related problems
The multi-budget maximum weighted coverage problem
Online budgeted maximum coverage
Minimizing the Spread of Rumor Within Budget Constraint in Online Network
Optimization with demand oracles
Introducing time series snippets: a new primitive for summarizing long time series
Analyzing the optimal neighborhood: algorithms for partial and budgeted connected dominating set problems
Improved deterministic algorithms for non-monotone submodular maximization
The impact of partial production capacity sharing via production as a service
Accelerated Benders decomposition and local branching for dynamic maximum covering location problems
A Nearly-Linear Time Algorithm for Submodular Maximization with a Knapsack Constraint
On the fixed-parameter tractability of the partial vertex cover problem with a matching constraint in edge-weighted bipartite graphs
A note on the set union knapsack problem
Constrained submodular maximization via a nonsymmetric technique
A Tight Approximation for Submodular Maximization with Mixed Packing and Covering Constraints
On the Parameterized Complexity of the Expected Coverage Problem
On the partial vertex cover problem in bipartite graphs -- a parameterized perspective
Maximum coverage with cluster constraints: an LP-based approximation technique
Parameter estimation in epidemic spread networks using limited measurements
Monotone \(k\)-submodular knapsack maximization: an analysis of the Greedy+Singleton algorithm
Streaming submodular maximization with the chance constraint
Energy-constrained geometric coverage problem
Budget-constrained cost-covering job assignment for a total contribution-maximizing platform
Approximating the optimal sequence of acquisitions and sales with a capped budget
Dual domination problems in graphs
Non-monotone submodular function maximization under \(k\)-system constraint
A 1/2 approximation algorithm for energy-constrained geometric coverage problem
Tight Approximation Bounds for the Seminar Assignment Problem
A (1-e^{-1}-ε)-Approximation for the Monotone Submodular Multiple Knapsack Problem
A new greedy strategy for maximizing monotone submodular function under a cardinality constraint
Behavioral model summarisation for other agents under uncertainty
Submodular Maximization Subject to a Knapsack Constraint Under Noise Models
Improved budgeted connected domination and budgeted edge-vertex domination
On the Minimum Hitting Set of Bundles Problem
Bicriteria Approximation Tradeoff for the Node-Cost Budget Problem
Budgeted maximum coverage with overlapping costs: monitoring the emerging infections network
\textsc{Greedy+Singleton}: an efficient approximation algorithm for \(k\)-submodular knapsack maximization

This page was built for publication: The budgeted maximum coverage problem

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1606925)