A note on maximizing a submodular set function subject to a knapsack constraint

Cites work

A threshold of ln n for approximating set cover
An analysis of approximations for maximizing submodular set functions—I
An Exact Algorithm for Maximum Entropy Sampling
Approximate Algorithms for the 0/1 Knapsack Problem
Constrained maximum-entropy sampling
Maximising Real-Valued Submodular Functions: Primal and Dual Heuristics for Location Problems
The budgeted maximum coverage problem

Cited in

(only showing first 100 items - show all)

The submodular knapsack polytope
Decision trees for function evaluation: simultaneous optimization of worst and expected cost
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
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
Bounds on double-sided myopic algorithms for unconstrained non-monotone submodular maximization
Discrete stochastic submodular maximization: adaptive vs. non-adaptive vs. offline
Distributed submodular maximization
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
Thresholded covering algorithms for robust and max-min optimization
Approximate submodularity and its applications: subset selection, sparse approximation and dictionary selection
Primal-dual approximation algorithm for the two-level facility location problem via a dual quasi-greedy approach
Budget feasible procurement auctions
Worst-case mechanism design via Bayesian analysis
Streaming algorithms for maximizing monotone submodular functions under a knapsack constraint
Generalized budgeted submodular set function maximization
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
Generalized assignment via submodular optimization with reserved capacity
Structured Robust Submodular Maximization: Offline and Online Algorithms
A Nearly-Linear Time Algorithm for Submodular Maximization with a Knapsack Constraint
A Tight Approximation for Submodular Maximization with Mixed Packing and Covering Constraints
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
New performance guarantees for the greedy maximization of submodular set functions
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
Video distribution under multiple constraints
Budget-feasible mechanism design for non-monotone submodular objectives: offline and online
A (1-e^{-1}-ε)-Approximation for the Monotone Submodular Multiple Knapsack Problem
Submodular Maximization Subject to a Knapsack Constraint Under Noise Models
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

This page was built for publication: A note on maximizing a submodular set function subject to a knapsack constraint

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