Improved Approximation Algorithms for k-Submodular Function Maximization.

Satoru Iwata Shin-ichi Tanigawa Yuichi Yoshida

Published in: CoRR (2015)

Keyphrases

approximation algorithms
facility location problem
submodular functions
constant factor approximation
np hard
worst case
special case
greedy algorithm
vertex cover
primal dual
randomized algorithms
approximation ratio
objective function
image processing
disjoint paths
set cover
linear programming
graphical models