Approximation algorithm of maximizing non-monotone non-submodular functions under knapsack constraint
From MaRDI portal
Publication:6201343
DOI10.1016/j.tcs.2024.114409OpenAlexW4391188659MaRDI QIDQ6201343
Publication date: 20 February 2024
Published in: Theoretical Computer Science (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1016/j.tcs.2024.114409
Cites Work
- Maximizing non-monotone submodular set functions subject to different constraints: combined algorithms
- An \(R\)-square coefficient based on final prediction error
- A note on maximizing a submodular set function subject to a knapsack constraint
- The budgeted maximum coverage problem
- Maximizing monotone submodular functions over the integer lattice
- A 1/2-approximation algorithm for maximizing a non-monotone weak-submodular function on a bounded integer lattice
- Bicriteria algorithms to balance coverage and cost in team formation under online model
- Improved prophet inequalities for combinatorial welfare maximization with (approximately) subadditive agents
- Application of Submodular Optimization to Single Machine Scheduling with Controllable Processing Times Subject to Release Dates and Deadlines
- Maximizing Non-monotone Submodular Functions
- An analysis of approximations for maximizing submodular set functions—I
- Optimal Approximation for Submodular and Supermodular Optimization with Bounded Curvature
- Submodularity in Input Node Selection for Networked Linear Systems: Efficient Algorithms for Performance and Controllability
- Non-monotone submodular maximization under matroid and knapsack constraints
- Some optimal inapproximability results
- Approximation guarantees for parallelized maximization of monotone non-submodular function with a cardinality constraint
- Weakly Submodular Function Maximization Using Local Submodularity Ratio.
This page was built for publication: Approximation algorithm of maximizing non-monotone non-submodular functions under knapsack constraint
