Monotone k-submodular knapsack maximization: an analysis of the Greedy+Singleton algorithm
DOI10.1007/978-3-031-16081-3_13zbMATH Open1527.90186OpenAlexW4296168139MaRDI QIDQ6167014FDOQ6167014
Authors: Jingwen Chen, Zhongzheng Tang, Chenhao Wang 
Publication date: 7 July 2023
Published in: Algorithmic Aspects in Information and Management (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1007/978-3-031-16081-3_13
Recommendations
- An improved analysis of the Greedy+Singleton algorithm for \(k\)-submodular knapsack maximization
- On maximizing a monotone \(k\)-submodular function under a knapsack constraint
- On maximizing monotone or non-monotone \(k\)-submodular functions with the intersection of knapsack and matroid constraints
- Guarantees for maximization of \(k\)-submodular functions with a knapsack and a matroid constraint
- On maximizing a monotone \(k\)-submodular function subject to a matroid constraint
Approximation methods and heuristics in mathematical programming (90C59) Combinatorial optimization (90C27) Approximation algorithms (68W25)
Cites Work
- The budgeted maximum coverage problem
- A note on maximizing a submodular set function subject to a knapsack constraint
- Maximizing \(k\)-submodular functions and beyond
- Towards minimizing \(k\)-submodular functions
- The generalized maximum coverage problem
- On \(k\)-submodular relaxation
- Improved approximation algorithms for \(k\)-submodular function maximization
- On maximizing a monotone \(k\)-submodular function subject to a matroid constraint
- A refined analysis of submodular greedy
- On maximizing a monotone \(k\)-submodular function under a knapsack constraint
- A Nearly-Linear Time Algorithm for Submodular Maximization with a Knapsack Constraint
- Streaming algorithms for maximizing monotone submodular functions under a knapsack constraint
- Improved streaming algorithms for maximizing monotone submodular functions under a knapsack constraint
- Improved randomized algorithm for \(k\)-submodular function maximization
- Practical budgeted submodular maximization
Cited In (5)
- \textsc{Greedy+Max}: an efficient approximation algorithm for \(k\)-submodular knapsack maximization
- Multiple knapsack-constrained monotone DR-submodular maximization on distributive lattice -- continuous greedy algorithm on median complex --
- \textsc{Greedy+Singleton}: an efficient approximation algorithm for \(k\)-submodular knapsack maximization
- Guarantees for maximization of \(k\)-submodular functions with a knapsack and a matroid constraint
- An improved analysis of the Greedy+Singleton algorithm for \(k\)-submodular knapsack maximization
This page was built for publication: Monotone \(k\)-submodular knapsack maximization: an analysis of the Greedy+Singleton algorithm
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6167014)
