Improved Approximation Algorithms for k-Submodular Function Maximization
From MaRDI portal
Publication:4575607
DOI10.1137/1.9781611974331.ch30zbMath1411.68194arXiv1502.07406OpenAlexW2950365512MaRDI QIDQ4575607
Yuichi Yoshida, Satoru Iwata, Shin-ichi Tanigawa
Publication date: 16 July 2018
Published in: Proceedings of the Twenty-Seventh Annual ACM-SIAM Symposium on Discrete Algorithms (Search for Journal in Brave)
Full work available at URL: https://arxiv.org/abs/1502.07406
Analysis of algorithms and problem complexity (68Q25) Combinatorial optimization (90C27) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Approximation algorithms (68W25)
Related Items
A compact representation for minimizers of \(k\)-submodular functions, Monotone \(k\)-submodular secretary problems: cardinality and knapsack constraints, Maximizing \(k\)-submodular functions under budget constraint: applications and streaming algorithms, On maximizing a monotone \(k\)-submodular function under a knapsack constraint, Improved approximation algorithms for \(k\)-submodular maximization under a knapsack constraint, Maximization of \(k\)-submodular function with a 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, On maximizing a monotone \(k\)-submodular function subject to a matroid constraint, Maximizing monotone submodular functions over the integer lattice, On $k$-Submodular Relaxation, An exact cutting plane method for \(k\)-submodular function maximization, Improved Randomized Algorithm for k-Submodular Function Maximization, k-Submodular maximization with two kinds of constraints