Derandomization for k-submodular maximization

DOI10.1007/978-3-319-78825-8_8MaRDI QIDQ1642687zbMATH OpenOpenAlexFDO

Authors Hiroki Oshima

Publication date 15 June 2018

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

Mathematics Subject Classification ID

Randomized algorithms (68W20) Combinatorial optimization (90C27) Approximation algorithms (68W25)

Abstract: Submodularity is one of the most important property of combinatorial optimization, and $k$-submodularity is a generalization of submodularity. Maximization of $k$-submodular function is NP-hard, and approximation algorithms are studied. For monotone $k$-submodular function, [Iwata, Tanigawa, and Yoshida 2016] gave $k/(2k-1)$-approximation algorithm. In this paper, we give a deterministic algorithm by derandomizing that algorithm. Derandomization scheme is from [Buchbinder and Feldman 2016]. Our algorithm is $k/(2k-1)$-approximation and polynomial-time algorithm.

Recommendations

• Deterministic algorithms for submodular maximization problems
• Deterministic Algorithms for Submodular Maximization Problems
• Improved randomized algorithm for \(k\)-submodular function maximization
• Maximizing \(k\)-submodular functions and beyond
• Maximizing bisubmodular and \(k\)-submodular functions

Cited in

(7)

• Improved randomized algorithm for \(k\)-submodular function maximization
• Efficient algorithms for \(k\)-submodular function maximization with \(p\)-system and \(d\)-knapsack constraint
• Improved approximation algorithms for \(k\)-submodular maximization under a knapsack constraint
• Deterministic algorithms for submodular maximization problems
• On \(k\)-submodular relaxation
• Maximizing \(k\)-submodular functions under budget constraint: applications and streaming algorithms
• \(k\)-submodular maximization with two kinds of constraints

This page was built for publication: Derandomization for \(k\)-submodular maximization

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