Improved randomized algorithm for k-submodular function maximization

DOI10.1137/19M1277692MaRDI QIDQ5855531zbMATH OpenFDO

Authors Hiroki Oshima

Publication date 18 March 2021

Published in SIAM Journal on Discrete Mathematics (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1907.12942

zbMATH Keywords

\(k\)-submodular functionapproximationrandomized algorithmsubmodular function

Mathematics Subject Classification ID

Combinatorial optimization (90C27)

Abstract: Submodularity is one of the most important properties in combinatorial optimization, and $k$-submodularity is a generalization of submodularity. Maximization of a $k$-submodular function requires an exponential number of value oracle queries, and approximation algorithms have been studied. For unconstrained $k$-submodular maximization, Iwata et al. gave randomized $k/(2k-1)$-approximation algorithm for monotone functions, and randomized $1/2$-approximation algorithm for nonmonotone functions. In this paper, we present improved randomized algorithms for nonmonotone functions. Our algorithm gives $frac{k}^2+12k^2+1$-approximation for $kgeq3$. We also give a randomized $fracsqrt17-32$-approximation algorithm for $k=3$. We use the same framework used in Iwata et al. and Ward and v{Z}ivn'{y} with different probabilities.

Recommendations

• Derandomization for k-submodular maximization
• Improved approximation algorithms 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

Cites work

• A combinatorial algorithm minimizing submodular functions in strongly polynomial time.
• A tight linear time (1/2)-approximation for unconstrained submodular maximization
• An Algorithm for Submodular Functions on Graphs
• Deterministic algorithms for submodular maximization problems
• Improved approximation algorithms for \(k\)-submodular function maximization
• Maximizing k-submodular functions and beyond
• Maximizing Non-monotone Submodular Functions
• The ellipsoid method and its consequences in combinatorial optimization
• Theory of submodular programs: A fenchel-type min-max theorem and subgradients of submodular functions
• Towards minimizing k-submodular functions

Cited in

(21)

• Derandomization for k-submodular maximization
• On maximizing a monotone \(k\)-submodular function subject to a matroid constraint
• Monotone k-submodular secretary problems: cardinality and knapsack constraints
• 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
• scientific article; zbMATH DE number 5670654 (Why is no real title available?)
• Improved approximation algorithms for \(k\)-submodular function maximization
• Maximizing k-submodular functions and beyond
• \(k\)-submodular maximization with two kinds of constraints
• Maximizing bisubmodular and \(k\)-submodular functions
• 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
• \textsc{Greedy+Max}: an efficient approximation algorithm for \(k\)-submodular knapsack maximization
• Fast algorithms combining threshold-decreasing and greedy methods for maximizing constraint k-submodular functions
• Streaming algorithms for maximizing k-submodular functions with the multi-knapsack constraint
• Approximation algorithms for k-submodular maximization subject to a knapsack constraint

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

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