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) Approximation algorithms (68W25) Combinatorial optimization (90C27)

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

(12)

• Maximizing \(k\)-submodular functions under budget constraint: applications and streaming algorithms
• On \(k\)-submodular relaxation
• Deterministic algorithms for submodular maximization problems
• \(k\)-submodular maximization with two kinds of constraints
• Improved randomized algorithm for k-submodular function maximization
• Improved approximation algorithms for \(k\)-submodular maximization under a knapsack constraint
• Efficient algorithms for k-submodular function maximization with p-system and d-knapsack constraint
• On maximizing k-submodular functions under p-system and d-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
• Streaming algorithms for maximizing k-submodular functions under a partition matroid constraint
• k-submodular maximization under individual knapsack constraints: applications and streaming algorithm

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)