Monotone \(k\)-submodular knapsack maximization: an analysis of the Greedy+Singleton algorithm

DOI10.1007/978-3-031-16081-3_13zbMath1527.90186OpenAlexW4296168139MaRDI QIDQ6167014

Zhongzheng Tang, Jingwen Chen, Chen-Hao 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

zbMATH Keywords

knapsackapproximation ratio\(k\)-submodular

Mathematics Subject Classification ID

Approximation methods and heuristics in mathematical programming (90C59) Combinatorial optimization (90C27) Approximation algorithms (68W25)

Related Items (1)

\textsc{Greedy+Singleton}: an efficient approximation algorithm for \(k\)-submodular knapsack maximization

Cites Work

• The generalized maximum coverage problem
• A note on maximizing a submodular set function subject to a knapsack constraint
• The budgeted maximum coverage problem
• 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
• Practical budgeted submodular maximization
• On $k$-Submodular Relaxation
• Towards Minimizing k-Submodular Functions
• Improved Approximation Algorithms for k-Submodular Function Maximization
• Maximizing k -Submodular Functions and Beyond
• Streaming algorithms for maximizing monotone submodular functions under a knapsack constraint
• A Nearly-Linear Time Algorithm for Submodular Maximization with a Knapsack Constraint
• Improved Randomized Algorithm for k-Submodular Function Maximization
• Improved streaming algorithms for maximizing monotone submodular functions under a knapsack constraint

This page was built for publication: Monotone \(k\)-submodular knapsack maximization: an analysis of the Greedy+Singleton algorithm