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

DOI10.1016/j.tcs.2023.114320OpenAlexW4389060545MaRDI QIDQ6180752

Zhongzheng Tang, Chen-Hao Wang, Jingwen Chen

Publication date: 2 January 2024

Published in: Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.tcs.2023.114320

zbMATH Keywords

approximation algorithmgreedy algorithmsubmodularityknapsack

Mathematics Subject Classification ID

Theory of computing (68Qxx)

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
• An exact cutting plane method for \(k\)-submodular function maximization
• Monotone \(k\)-submodular secretary problems: cardinality and knapsack constraints
• Maximizing \(k\)-submodular functions under budget constraint: applications and streaming algorithms
• The application of the global quasi-linearisation technique to the analysis of the cyclohexane/air mixture autoignition
• 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
• On $k$-Submodular Relaxation
• Towards Minimizing k-Submodular Functions
• Maximising Real-Valued Submodular Functions: Primal and Dual Heuristics for Location Problems
• Improved Approximation Algorithms for k-Submodular Function Maximization
• Maximizing k -Submodular Functions and Beyond
• Improved Randomized Algorithm for k-Submodular Function Maximization
• Maximization of \(k\)-submodular function with a matroid constraint
• Monotone \(k\)-submodular knapsack maximization: an analysis of the Greedy+Singleton algorithm
• Guarantees for maximization of \(k\)-submodular functions with a knapsack and a matroid constraint

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