Guarantees for maximization of k-submodular functions with a knapsack and a matroid constraint
DOI10.1007/978-3-031-16081-3_14zbMATH Open1527.90192OpenAlexW4296168579MaRDI QIDQ6167015FDOQ6167015
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
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
Approximation methods and heuristics in mathematical programming (90C59) Combinatorial optimization (90C27) Approximation algorithms (68W25)
Cites Work
- Monotone submodular maximization over a matroid via non-oblivious local search
- Maximizing a monotone submodular function subject to a matroid constraint
- An analysis of approximations for maximizing submodular set functions—I
- A note on maximizing a submodular set function subject to a knapsack constraint
- Maximizing \(k\)-submodular functions and beyond
- Towards minimizing \(k\)-submodular functions
- Improved approximation algorithms for \(k\)-submodular function maximization
- On maximizing a monotone \(k\)-submodular function subject to a matroid constraint
- On maximizing a monotone \(k\)-submodular function under a knapsack constraint
- A Nearly-Linear Time Algorithm for Submodular Maximization with a Knapsack Constraint
- Maximizing a monotone submodular function with a bounded curvature under a knapsack constraint
- Maximization problems of balancing submodular relevance and supermodular diversity
- Approximability of Monotone Submodular Function Maximization under Cardinality and Matroid Constraints in the Streaming Model
- Improved randomized algorithm for \(k\)-submodular function maximization
- Constrained submodular maximization via greedy local search
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)
