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 Exact Algorithm for Maximum Entropy Sampling
An analysis of approximations for maximizing submodular set functions—I
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)

Multi-pass streaming algorithms for monotone submodular function maximization
A multi-pass streaming algorithm for regularized submodular maximization
Cut problems in graphs with a budget constraint
Streaming algorithm for maximizing a monotone non-submodular function under \(d\)-knapsack constraint
Worst-case mechanism design via Bayesian analysis
Fast algorithms for maximizing monotone nonsubmodular functions
Fast algorithms for maximizing monotone nonsubmodular functions
Influence Maximization in Social Networks
Supermodular covering knapsack polytope
Streaming algorithms for maximizing monotone submodular functions under a knapsack constraint
Streaming algorithms for maximizing monotone submodular functions under a knapsack constraint
Budgeted nature reserve selection with diversity feature loss and arbitrary split systems
Guarantees for maximization of \(k\)-submodular functions with a knapsack and a matroid constraint
Practical budgeted submodular maximization
Non-submodular maximization with matroid and knapsack constraints
Recent developments in discrete convex analysis
Fractionally subadditive maximization under an incremental knapsack constraint
Streaming algorithms for monotone non-submodular function maximization under a knapsack constraint on the integer lattice
An improved analysis of the Greedy+Singleton algorithm for \(k\)-submodular knapsack maximization
Random approximation algorithms for monotone \(k\)-submodular function maximization with size constraints
Two-stage stochastic max-weight independent set problems
scientific article; zbMATH DE number 7525506 (Why is no real title available?)
Optimizing node discovery on networks: problem definitions, fast algorithms, and observations
A simple deterministic algorithm for symmetric submodular maximization subject to a knapsack constraint
Online budgeted maximum coverage
Formulations and Approximation Algorithms for Multilevel Uncapacitated Facility Location
The multi-budget maximum weighted coverage problem
A fast double greedy algorithm for non-monotone DR-submodular function maximization
Tight approximation for unconstrained XOS maximization
Streaming submodular maximization under \(d\)-knapsack constraints
New performance guarantees for the greedy maximization of submodular set functions
Submodular maximization with uncertain knapsack capacity
Improved deterministic algorithms for non-monotone submodular maximization
Optimization with demand oracles
Submodular maximization of concave utility functions composed with a set-union operator with applications to maximal covering location problems
Packing under convex quadratic constraints
Algorithms for covering multiple submodular constraints and applications
Packing under convex quadratic constraints
Improved deterministic algorithms for non-monotone submodular maximization
Approximation for maximizing monotone non-decreasing set functions with a greedy method
ON THE PIPAGE ROUNDING ALGORITHM FOR SUBMODULAR FUNCTION MAXIMIZATION — A VIEW FROM DISCRETE CONVEX ANALYSIS
Per-round knapsack-constrained linear submodular bandits
A Nearly-Linear Time Algorithm for Submodular Maximization with a Knapsack Constraint
Algorithms for cardinality-constrained monotone DR-submodular maximization with low adaptivity and query complexity
Unified Greedy Approximability beyond Submodular Maximization
Constrained submodular maximization via a nonsymmetric technique
A Tight Approximation for Submodular Maximization with Mixed Packing and Covering Constraints
Pervasive domination
Bounds on double-sided myopic algorithms for unconstrained non-monotone submodular maximization
Maximum coverage with cluster constraints: an LP-based approximation technique
An optimal monotone contention resolution scheme for bipartite matchings via a polyhedral viewpoint
Algorithms for storage allocation based on client preferences
Video distribution under multiple constraints
Maximizing expected utility over a knapsack constraint
Monotone \(k\)-submodular knapsack maximization: an analysis of the Greedy+Singleton algorithm
Maximizing a non-decreasing non-submodular function subject to various types of constraints
Approximation algorithms for fragmenting a graph against a stochastically-located threat
Maximum betweenness centrality: approximability and tractable cases
Streaming submodular maximization with the chance constraint
Robust monotone submodular function maximization
Profit maximization for competitive influence spread in social networks
On maximizing a monotone \(k\)-submodular function subject to a matroid constraint
Approximation algorithms for the robust/soft-capacitated 2-level facility location problems
Thresholded covering algorithms for robust and max-min optimization
C2IM: community based context-aware influence maximization in social networks
Bicriteria algorithms for maximizing the difference between submodular function and linear function under noise
Energy-constrained geometric coverage problem
Dual domination problems in graphs
Non-monotone submodular function maximization under \(k\)-system constraint
Optimal experimental design: formulations and computations
More effort towards multiagent knapsack
Maximizing a monotone non-submodular function under a knapsack constraint
Tight Approximation Bounds for the Seminar Assignment Problem
Maximizing the differences between a monotone DR-submodular function and a linear function on the integer lattice
Set function optimization
A (1-e^{-1}-ε)-Approximation for the Monotone Submodular Multiple Knapsack Problem
Submodular Maximization Subject to a Knapsack Constraint Under Noise Models
Strategyproof mechanisms for competitive influence in networks
Multiple knapsack-constrained monotone DR-submodular maximization on distributive lattice -- continuous greedy algorithm on median complex --
Streaming algorithms for maximizing monotone DR-submodular functions with a cardinality constraint on the integer lattice
Unified greedy approximability beyond submodular maximization
\textsc{Greedy+Singleton}: an efficient approximation algorithm for \(k\)-submodular knapsack maximization
Randomized strategies for robust combinatorial optimization with approximate separation
Improved approximation algorithms for \(k\)-submodular maximization under a knapsack constraint
An accelerated continuous greedy algorithm for maximizing strong submodular functions
A two-stage stochastic programming approach for influence maximization in social networks
Structured Robust Submodular Maximization: Offline and Online Algorithms
Measured continuous greedy with differential privacy
On maximizing a monotone \(k\)-submodular function under a knapsack constraint
Risk averse submodular utility maximization
Non-submodular streaming maximization with minimum memory and low adaptive complexity
Budget-feasible mechanism design for non-monotone submodular objectives: offline and online
Constrained submodular maximization via greedy local search
Improved streaming algorithms for maximizing monotone submodular functions under a knapsack constraint
Distributed submodular maximization
Fractional 0-1 programming and submodularity
Maximizing a monotone submodular function with a bounded curvature under a knapsack constraint
Maximizing DR-submodular+supermodular functions on the integer lattice subject to a cardinality constraint
A fast and deterministic algorithm for knapsack-constrained monotone DR-submodular maximization over an integer lattice
The knapsack problem with neighbour constraints

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)