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

DOI10.1007/978-3-031-16081-3_13MaRDI QIDQ6167014zbMATH OpenOpenAlexFDO

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

zbMATH Keywords

knapsackapproximation ratio\(k\)-submodular

Mathematics Subject Classification ID

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

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

Cites work

• A Nearly-Linear Time Algorithm for Submodular Maximization with a Knapsack Constraint
• A note on maximizing a submodular set function subject to a knapsack constraint
• A refined analysis of submodular greedy
• Improved approximation algorithms for \(k\)-submodular function maximization
• Improved randomized algorithm for \(k\)-submodular function maximization
• Improved streaming algorithms for maximizing monotone submodular functions under a knapsack constraint
• Maximizing \(k\)-submodular functions and beyond
• On \(k\)-submodular relaxation
• On maximizing a monotone \(k\)-submodular function subject to a matroid constraint
• On maximizing a monotone \(k\)-submodular function under a knapsack constraint
• Practical budgeted submodular maximization
• Streaming algorithms for maximizing monotone submodular functions under a knapsack constraint
• The budgeted maximum coverage problem
• The generalized maximum coverage problem
• Towards minimizing \(k\)-submodular functions

Cited in

(5)

• \textsc{Greedy+Singleton}: an efficient approximation algorithm for \(k\)-submodular knapsack maximization
• \textsc{Greedy+Max}: an efficient approximation algorithm for \(k\)-submodular knapsack maximization
• An improved analysis of the Greedy+Singleton algorithm for \(k\)-submodular knapsack maximization
• Multiple knapsack-constrained monotone DR-submodular maximization on distributive lattice -- continuous greedy algorithm on median complex --
• Guarantees for maximization of \(k\)-submodular functions with a knapsack and a matroid constraint

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)