A note on maximizing a submodular set function subject to a knapsack constraint
From MaRDI portal
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)- Lower bounds for matroid optimization problems with a linear constraint
- Decision trees for function evaluation: simultaneous optimization of worst and expected cost
- Separating coverage and submodular: maximization subject to a cardinality constraint
- Stochastic Variance Reduction for DR-Submodular Maximization
- New approximations for monotone submodular maximization with knapsack constraint
- Submodular optimization problems and greedy strategies: a survey
- Submodular maximization subject to a knapsack constraint: combinatorial algorithms with near-optimal adaptive complexity
- The submodular knapsack polytope
- A refined analysis of submodular greedy
- Polynomial-time approximation schemes for maximizing gross substitutes utility under budget constraints
- A continuous knapsack problem with separable convex utilities: approximation algorithms and applications
- Maximization of monotone non-submodular functions with a knapsack constraint over the integer lattice
- Approximation algorithm of maximizing non-submodular functions under non-submodular constraint
- Submodular Maximization Through the Lens of Linear Programming
- Maximize a monotone function with a generic submodularity ratio
- An almost optimal approximation algorithm for monotone submodular multiple knapsack
- 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
- Submodular + supermodular function maximization with knapsack constraint
- Two-stage stochastic max-weight independent set problems
- A note on fast deterministic algorithms for non-monotone submodular maximization under a knapsack constraint
- 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
- Efficient deterministic algorithms for maximizing symmetric submodular functions
- 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
- Randomized approximation algorithms for monotone k-submodular function maximization with 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
- On the fine-grained complexity of approximating max k-coverage
- 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
- Practical parallel algorithms for non-monotone submodular maximization
- Dual domination problems in graphs
- Non-monotone submodular function maximization under k-system constraint
- Optimal experimental design: formulations and computations
- Maximizing a k-submodular function with p-system constraints
- 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
- Enhanced deterministic approximation algorithm for non-monotone submodular maximization under knapsack constraint with linear query complexity
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)
