A note on maximizing a submodular set function subject to a knapsack constraint
From MaRDI portal
Publication:1433658
DOI10.1016/S0167-6377(03)00062-2zbMath1056.90124OpenAlexW2033885045MaRDI QIDQ1433658
Publication date: 1 July 2004
Published in: Operations Research Letters (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1016/s0167-6377(03)00062-2
Approximation methods and heuristics in mathematical programming (90C59) Combinatorial optimization (90C27)
Related Items
Strategyproof mechanisms for competitive influence in networks, Packing Under Convex Quadratic Constraints, Dual domination problems in graphs, An Optimal Approximation for Submodular Maximization Under a Matroid Constraint in the Adaptive Complexity Model, Multiple knapsack-constrained monotone DR-submodular maximization on distributive lattice -- continuous greedy algorithm on median complex --, Two-stage stochastic max-weight independent set problems, Maximization of monotone non-submodular functions with a knapsack constraint over the integer lattice, A multi-pass streaming algorithm for regularized submodular maximization, Measured continuous greedy with differential privacy, Robust Monotone Submodular Function Maximization, Maximizing a non-decreasing non-submodular function subject to various types of constraints, Maximizing a monotone non-submodular function under a knapsack constraint, C2IM: community based context-aware influence maximization in social networks, Fractional 0-1 programming and submodularity, Algorithms for covering multiple submodular constraints and applications, Maximizing \(k\)-submodular functions under budget constraint: applications and streaming algorithms, Structured Robust Submodular Maximization: Offline and Online Algorithms, Bounds on Double-Sided Myopic Algorithms for Unconstrained Non-monotoneSubmodular Maximization, Decision trees for function evaluation: simultaneous optimization of worst and expected cost, Fast Adaptive Non-Monotone Submodular Maximization Subject to a Knapsack Constraint, On maximizing a monotone \(k\)-submodular function under a knapsack constraint, FPT approximation schemes for maximizing submodular functions, Discrete Stochastic Submodular Maximization: Adaptive vs. Non-adaptive vs. Offline, Optimization with demand oracles, An accelerated continuous greedy algorithm for maximizing strong submodular functions, The knapsack problem with neighbour constraints, Thresholded covering algorithms for robust and max-min optimization, 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, Streaming algorithm for maximizing a monotone non-submodular function under \(d\)-knapsack constraint, Constrained Submodular Maximization via a Nonsymmetric Technique, Submodular Maximization Through the Lens of Linear Programming, Streaming submodular maximization under \(d\)-knapsack constraints, Submodular optimization problems and greedy strategies: a survey, Unnamed Item, Optimizing node discovery on networks: problem definitions, fast algorithms, and observations, 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, On maximizing monotone or non-monotone \(k\)-submodular functions with the intersection of knapsack and matroid constraints, Recent Developments in Discrete Convex Analysis, Practical budgeted submodular maximization, Per-Round Knapsack-Constrained Linear Submodular Bandits, Formulations and Approximation Algorithms for Multilevel Uncapacitated Facility Location, Maximize a monotone function with a generic submodularity ratio, Primal-dual approximation algorithm for the two-level facility location problem via a dual quasi-greedy approach, Budgeted nature reserve selection with diversity feature loss and arbitrary split systems, Cut problems in graphs with a budget constraint, Influence Maximization in Social Networks, Online budgeted maximum coverage, A two-stage stochastic programming approach for influence maximization in social networks, Approximation algorithms for the robust/soft-capacitated 2-level facility location problems, Supermodular covering knapsack polytope, On maximizing a monotone \(k\)-submodular function subject to a matroid constraint, New performance guarantees for the greedy maximization of submodular set functions, Streaming algorithms for maximizing monotone submodular functions under a knapsack constraint, Unnamed Item, Video distribution under multiple constraints, Algorithms for storage allocation based on client preferences, Unnamed Item, Non-monotone submodular function maximization under \(k\)-system constraint, A continuous knapsack problem with separable convex utilities: approximation algorithms and applications, Risk averse submodular utility maximization, Maximizing expected utility over a knapsack constraint, A random algorithm for profit maximization in online social networks, Non-submodular streaming maximization with minimum memory and low adaptive complexity, Robust monotone submodular function maximization, Maximizing monotone submodular functions over the integer lattice, Constrained submodular maximization via greedy local search, Maximum Betweenness Centrality: Approximability and Tractable Cases, Maximizing DR-submodular+supermodular functions on the integer lattice subject to a cardinality constraint, A fast double greedy algorithm for non-monotone DR-submodular function maximization, Streaming algorithms for maximizing monotone submodular functions under a knapsack constraint, Generalized budgeted submodular set function maximization, Budget Feasible Procurement Auctions, ON THE PIPAGE ROUNDING ALGORITHM FOR SUBMODULAR FUNCTION MAXIMIZATION — A VIEW FROM DISCRETE CONVEX ANALYSIS, A refined analysis of submodular greedy, A Nearly-Linear Time Algorithm for Submodular Maximization with a Knapsack Constraint, Worst-Case Mechanism Design via Bayesian Analysis, A Tight Approximation for Submodular Maximization with Mixed Packing and Covering Constraints, Set function optimization, Submodular Maximization with Uncertain Knapsack Capacity, Maximizing a Monotone Submodular Function with a Bounded Curvature under a Knapsack Constraint, An almost optimal approximation algorithm for monotone submodular multiple knapsack, On social envy-freeness in multi-unit markets, Multi-pass streaming algorithms for monotone submodular function maximization, The submodular knapsack polytope, Polynomial-Time Approximation Schemes for Maximizing Gross Substitutes Utility Under Budget Constraints, Fractionally subadditive maximization under an incremental knapsack constraint, Streaming algorithms for monotone non-submodular function maximization under a knapsack constraint on the integer lattice, Submodular maximization of concave utility functions composed with a set-union operator with applications to maximal covering location problems, Approximation algorithms for fragmenting a graph against a stochastically-located threat, Unnamed Item, Budget-Feasible Mechanism Design for Non-monotone Submodular Objectives: Offline and Online, Non-Submodular Maximization with Matroid and Knapsack Constraints, Streaming Algorithms for Maximizing Monotone DR-Submodular Functions with a Cardinality Constraint on the Integer Lattice, Tight Approximation for Unconstrained XOS Maximization, Maximum coverage with cluster constraints: an LP-based approximation technique, An optimal monotone contention resolution scheme for bipartite matchings via a polyhedral viewpoint, Packing under convex quadratic constraints, Submodular Maximization Subject to a Knapsack Constraint Under Noise Models, Improved approximation algorithms for \(k\)-submodular maximization under a knapsack constraint, Improved deterministic algorithms for non-monotone submodular maximization, Unified Greedy Approximability beyond Submodular Maximization, Algorithms for cardinality-constrained monotone DR-submodular maximization with low adaptivity and query complexity, Improved deterministic algorithms for non-monotone submodular maximization, Streaming submodular maximization with the chance constraint, Pervasive domination, Unified greedy approximability beyond submodular maximization, Bicriteria algorithms for maximizing the difference between submodular function and linear function under noise, Monotone \(k\)-submodular knapsack maximization: an analysis of the Greedy+Singleton algorithm, Guarantees for maximization of \(k\)-submodular functions with a knapsack and a matroid constraint, Energy-constrained geometric coverage problem, More effort towards multiagent knapsack, \textsc{Greedy+Singleton}: an efficient approximation algorithm for \(k\)-submodular knapsack maximization, Randomized strategies for robust combinatorial optimization with approximate separation, Approximation algorithm of maximizing non-monotone non-submodular functions under knapsack constraint, Fractionally Subadditive Maximization under an Incremental Knapsack Constraint with Applications to Incremental Flows, A (1-e^{-1}-ε)-Approximation for the Monotone Submodular Multiple Knapsack Problem, Approximation for maximizing monotone non-decreasing set functions with a greedy method, Sequence submodular maximization meets streaming, Fast algorithms for maximizing monotone nonsubmodular functions, Fast algorithms for maximizing monotone nonsubmodular functions, Improved streaming algorithms for maximizing monotone submodular functions under a knapsack constraint
Cites Work
- The budgeted maximum coverage problem
- Constrained Maximum-Entropy Sampling
- A threshold of ln n for approximating set cover
- Maximising Real-Valued Submodular Functions: Primal and Dual Heuristics for Location Problems
- Approximate Algorithms for the 0/1 Knapsack Problem
- An analysis of approximations for maximizing submodular set functions—I
- An Exact Algorithm for Maximum Entropy Sampling
