Improved approximation algorithms for k-submodular function maximization

DOI10.1137/1.9781611974331.CH30MaRDI QIDQ4575607zbMATH OpenOpenAlexFDO

Authors Satoru Iwata, Shin-Ichi Tanigawa, Yuichi Yoshida

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

Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Analysis of algorithms and problem complexity (68Q25) Approximation algorithms (68W25) Combinatorial optimization (90C27)

Abstract: This paper presents a polynomial-time $1/2$-approximation algorithm for maximizing nonnegative $k$-submodular functions. This improves upon the previous $max1/3,1/(1+a)$-approximation by Ward and v{Z}ivn'y~(SODA'14), where $a=max1,sqrt(k-1)/4$. We also show that for monotone $k$-submodular functions there is a polynomial-time $k/(2k-1)$-approximation algorithm while for any $varepsilon>0$ a $((k+1)/2k+varepsilon)$-approximation algorithm for maximizing monotone $k$-submodular functions would require exponentially many queries. In particular, our hardness result implies that our algorithms are asymptotically tight. We also extend the approach to provide constant factor approximation algorithms for maximizing skew-bisubmodular functions, which were recently introduced as generalizations of bisubmodular functions.

Recommendations

• Improved randomized algorithm for k-submodular function maximization
• Maximizing k-submodular functions and beyond
• On maximizing a monotone \(k\)-submodular function subject to a matroid constraint
• Maximizing bisubmodular and \(k\)-submodular functions
• \(k\)-submodular maximization with two kinds of constraints

Cited in

(38)

• A compact representation for minimizers of k-submodular functions
• On maximizing a monotone \(k\)-submodular function subject to a matroid constraint
• An exact cutting plane method for k-submodular function maximization
• Monotone k-submodular secretary problems: cardinality and knapsack constraints
• Maximizing \(k\)-submodular functions under budget constraint: applications and streaming algorithms
• Improved approximation algorithms for the Min-Max selecting items problem
• On maximizing a monotone \(k\)-submodular function under a knapsack constraint
• On maximizing monotone or non-monotone k-submodular functions with the intersection of knapsack and matroid constraints
• On \(k\)-submodular relaxation
• scientific article; zbMATH DE number 5670654 (Why is no real title available?)
• Maximizing k-submodular functions and beyond
• \(k\)-submodular maximization with two kinds of constraints
• Maximizing bisubmodular and \(k\)-submodular functions
• Improved randomized algorithm for k-submodular function maximization
• 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
• An improved analysis of the Greedy+Singleton algorithm for \(k\)-submodular knapsack maximization
• Random approximation algorithms for monotone \(k\)-submodular function maximization with size constraints
• Efficient algorithms for k-submodular function maximization with p-system and d-knapsack constraint
• \textsc{Greedy+Max}: an efficient approximation algorithm for \(k\)-submodular knapsack maximization
• k-submodular and approximately non-k-submodular maximization under p-system and knapsack constraints
• On maximizing k-submodular functions under p-system and d-knapsack constraints
• Approximately non-k-submodular maximization under p-system and knapsack constraints
• Fast algorithms combining threshold-decreasing and greedy methods for maximizing constraint k-submodular functions
• Randomized approximation algorithms for monotone k-submodular function maximization with constraints
• Maximizing a k-submodular function with p-system constraints
• Greedy algorithms for stochastic monotone k-submodular maximization under full-bandit feedback
• Streaming algorithms for maximizing k-submodular functions with the multi-knapsack constraint
• Streaming algorithms for maximizing k-submodular functions under a partition matroid constraint
• Approximation algorithms for k-submodular maximization subject to a knapsack constraint
• k-submodular maximization under individual knapsack constraints: applications and streaming algorithm
• Approximation algorithms for k-submodular maximization under fairness constraints and size constraints
• Deterministic algorithms for k-submodular maximization with the chance constraint
• An exponential value-oracle lower bound for k-submodular function minimization

This page was built for publication: Improved approximation algorithms for \(k\)-submodular function maximization

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4575607)