Guarantees for maximization of \(k\)-submodular functions with a knapsack and a matroid constraint
From MaRDI portal
Publication:6167015
DOI10.1007/978-3-031-16081-3_14zbMath1527.90192OpenAlexW4296168579MaRDI QIDQ6167015
Qian Liu, Min Li, Unnamed Author, Kemin Yu
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
Approximation methods and heuristics in mathematical programming (90C59) Combinatorial optimization (90C27) Approximation algorithms (68W25)
Related Items (1)
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
- Maximization problems of balancing submodular relevance and supermodular diversity
- Constrained submodular maximization via greedy local search
- On maximizing a monotone \(k\)-submodular function under a knapsack constraint
- Towards Minimizing k-Submodular Functions
- Maximizing a Monotone Submodular Function Subject to a Matroid Constraint
- An analysis of approximations for maximizing submodular set functions—I
- Improved Approximation Algorithms for k-Submodular Function Maximization
- Maximizing k -Submodular Functions and Beyond
- Approximability of Monotone Submodular Function Maximization under Cardinality and Matroid Constraints in the Streaming Model
- 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
- Monotone Submodular Maximization over a Matroid via Non-Oblivious Local Search
- Improved Randomized Algorithm for k-Submodular Function Maximization
This page was built for publication: Guarantees for maximization of \(k\)-submodular functions with a knapsack and a matroid constraint
