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 (17)
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
This page was built for publication: Improved Approximation Algorithms for k-Submodular Function Maximization