Improved Approximation Algorithms for k-Submodular Function Maximization

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

Mathematics Subject Classification ID

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