On maximizing a monotone \(k\)-submodular function under a knapsack constraint

DOI10.1016/j.orl.2021.11.010OpenAlexW3171608239MaRDI QIDQ2670465

Zhongzheng Tang, Hau Chan, Chen-Hao Wang

Publication date: 11 March 2022

Published in: Operations Research Letters (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/2105.15159

zbMATH Keywords

approximation algorithmsknapsack\(k\)-submodularity

Mathematics Subject Classification ID

Operations research, mathematical programming (90-XX)

Related Items (10)

Monotone \(k\)-submodular secretary problems: cardinality and knapsack constraints ⋮ Maximizing \(k\)-submodular functions under budget constraint: applications and streaming algorithms ⋮ Improved approximation algorithms for \(k\)-submodular maximization under a knapsack constraint ⋮ Maximization of \(k\)-submodular function with a matroid constraint ⋮ Maximizing approximately non-\(k\)-submodular monotone set function with matroid constraint ⋮ Weakly \(k\)-submodular maximization under 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 ⋮ \textsc{Greedy+Singleton}: an efficient approximation algorithm for \(k\)-submodular knapsack maximization ⋮ On maximizing monotone or non-monotone \(k\)-submodular functions with the intersection of knapsack and matroid constraints

Cites Work

• A note on maximizing a submodular set function subject to a knapsack constraint
• On maximizing a monotone \(k\)-submodular function subject to a matroid constraint
• The application of the global quasi-linearisation technique to the analysis of the cyclohexane/air mixture autoignition
• On $k$-Submodular Relaxation
• A threshold of ln n for approximating set cover
• 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
• 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: On maximizing a monotone \(k\)-submodular function under a knapsack constraint