Guarantees for maximization of k-submodular functions with a knapsack and a matroid constraint

DOI10.1007/978-3-031-16081-3_14MaRDI QIDQ6167015zbMATH OpenOpenAlexFDO

Authors Kemin Yu, M. Li, Yang Zhou, Qian Liu

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_14

zbMATH Keywords

approximation algorithmknapsack constraintmatroid constraint\(k\)-submodularity

Mathematics Subject Classification ID

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

Recommendations

• On maximizing monotone or non-monotone \(k\)-submodular functions with the intersection of knapsack and matroid constraints
• On maximizing a monotone \(k\)-submodular function under a knapsack constraint
• On maximizing a monotone \(k\)-submodular function subject to a matroid constraint
• An improved analysis of the Greedy+Singleton algorithm for \(k\)-submodular knapsack maximization
• Monotone \(k\)-submodular knapsack maximization: an analysis of the Greedy+Singleton algorithm

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
• An analysis of approximations for maximizing submodular set functions—I
• Approximability of Monotone Submodular Function Maximization under Cardinality and Matroid Constraints in the Streaming Model
• Constrained submodular maximization via greedy local search
• Improved approximation algorithms for \(k\)-submodular function maximization
• Improved randomized algorithm for \(k\)-submodular function maximization
• Maximization problems of balancing submodular relevance and supermodular diversity
• Maximizing \(k\)-submodular functions and beyond
• Maximizing a monotone submodular function subject to a matroid constraint
• Maximizing a monotone submodular function with a bounded curvature under a knapsack constraint
• Monotone submodular maximization over a matroid via non-oblivious local search
• On maximizing a monotone \(k\)-submodular function subject to a matroid constraint
• On maximizing a monotone \(k\)-submodular function under a knapsack constraint
• Towards minimizing \(k\)-submodular functions

Cited in

(6)

• Monotone \(k\)-submodular knapsack maximization: an analysis of the Greedy+Singleton algorithm
• \textsc{Greedy+Max}: an efficient approximation algorithm for \(k\)-submodular knapsack maximization
• \textsc{Greedy+Singleton}: an efficient approximation algorithm for \(k\)-submodular knapsack maximization
• An improved analysis of the Greedy+Singleton algorithm for \(k\)-submodular knapsack maximization
• Random approximation algorithms for monotone \(k\)-submodular function maximization with size constraints
• Approximation guarantees for deterministic maximization of submodular function with a matroid constraint

This page was built for publication: Guarantees for maximization of \(k\)-submodular functions with a knapsack and a matroid constraint

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6167015)