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.90124MaRDI 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
90C59: Approximation methods and heuristics in mathematical programming
90C27: Combinatorial optimization
Related Items
Unnamed Item, Unnamed Item, Streaming algorithms for maximizing monotone submodular functions under a knapsack constraint, Unnamed Item, Budget Feasible Procurement Auctions, Worst-Case Mechanism Design via Bayesian Analysis, 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, Packing Under Convex Quadratic Constraints, An Optimal Approximation for Submodular Maximization Under a Matroid Constraint in the Adaptive Complexity Model, Structured Robust Submodular Maximization: Offline and Online Algorithms, Fast Adaptive Non-Monotone Submodular Maximization Subject to a Knapsack Constraint, Constrained Submodular Maximization via a Nonsymmetric Technique, Submodular Maximization Through the Lens of Linear Programming, Formulations and Approximation Algorithms for Multilevel Uncapacitated Facility Location, A fast double greedy algorithm for non-monotone DR-submodular function maximization, A Nearly-Linear Time Algorithm for Submodular Maximization with a Knapsack Constraint, A Tight Approximation for Submodular Maximization with Mixed Packing and Covering Constraints, Submodular Maximization with Uncertain Knapsack Capacity, Maximizing a Monotone Submodular Function with a Bounded Curvature under a Knapsack Constraint, Polynomial-Time Approximation Schemes for Maximizing Gross Substitutes Utility Under Budget Constraints, Per-Round Knapsack-Constrained Linear Submodular Bandits, Budget-Feasible Mechanism Design for Non-monotone Submodular Objectives: Offline and Online, Thresholded covering algorithms for robust and max-min optimization, Primal-dual approximation algorithm for the two-level facility location problem via a dual quasi-greedy approach, New performance guarantees for the greedy maximization of submodular set functions, Video distribution under multiple constraints, Budgeted nature reserve selection with diversity feature loss and arbitrary split systems, Approximation algorithms for the robust/soft-capacitated 2-level facility location problems, An accelerated continuous greedy algorithm for maximizing strong submodular functions, Algorithms for storage allocation based on client preferences, The submodular knapsack polytope, Decision trees for function evaluation: simultaneous optimization of worst and expected cost, FPT approximation schemes for maximizing submodular functions, A two-stage stochastic programming approach for influence maximization in social networks, Supermodular covering knapsack polytope, On maximizing a monotone \(k\)-submodular function subject to a matroid 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, Robust monotone submodular function maximization, Maximizing monotone submodular functions over the integer lattice, The knapsack problem with neighbour constraints, Online budgeted maximum coverage, Non-monotone submodular function maximization under \(k\)-system constraint, Non-submodular streaming maximization with minimum memory and low adaptive complexity, Maximizing DR-submodular+supermodular functions on the integer lattice subject to a cardinality constraint, Generalized budgeted submodular set function maximization, A refined analysis of submodular greedy, An almost optimal approximation algorithm for monotone submodular multiple knapsack, Multi-pass streaming algorithms for monotone submodular function maximization, 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, 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, Dual domination problems in graphs, 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, 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, Simple and efficient budget feasible mechanisms for monotone submodular valuations, Streaming algorithm for maximizing a monotone non-submodular function under \(d\)-knapsack constraint, Submodular optimization problems and greedy strategies: a survey, Optimizing node discovery on networks: problem definitions, fast algorithms, and observations, A simple deterministic algorithm for symmetric submodular maximization subject to a knapsack constraint, Maximize a monotone function with a generic submodularity ratio, A random algorithm for profit maximization in online social networks, Constrained submodular maximization via greedy local search, Streaming algorithms for maximizing monotone submodular functions under a knapsack constraint, Set function optimization, On social envy-freeness in multi-unit markets, Approximation algorithms for fragmenting a graph against a stochastically-located threat, Strategyproof mechanisms for competitive influence in networks, Optimization with demand oracles, Cut problems in graphs with a budget constraint, On maximizing a monotone \(k\)-submodular function under a knapsack constraint, A fast and deterministic algorithm for knapsack-constrained monotone DR-submodular maximization over an integer lattice, Streaming submodular maximization under \(d\)-knapsack constraints, The multi-budget maximum weighted coverage problem, On maximizing monotone or non-monotone \(k\)-submodular functions with the intersection of knapsack and matroid constraints, Practical budgeted submodular maximization, Unnamed Item, Bounds on Double-Sided Myopic Algorithms for Unconstrained Non-monotoneSubmodular Maximization, Discrete Stochastic Submodular Maximization: Adaptive vs. Non-adaptive vs. Offline, Tight Approximation Bounds for the Seminar Assignment Problem, Recent Developments in Discrete Convex Analysis, Maximum Betweenness Centrality: Approximability and Tractable Cases, Robust Monotone Submodular Function Maximization, Influence Maximization in Social Networks, ON THE PIPAGE ROUNDING ALGORITHM FOR SUBMODULAR FUNCTION MAXIMIZATION — A VIEW FROM DISCRETE CONVEX ANALYSIS, 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, Submodular Maximization Subject to a Knapsack Constraint Under Noise Models, A (1-e^{-1}-ε)-Approximation for the Monotone Submodular Multiple Knapsack Problem, 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
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
