An accelerated continuous greedy algorithm for maximizing strong submodular functions
type: Item
instance of: scholarly article
title: An accelerated continuous greedy algorithm for maximizing strong submodular functions
zbMATH Open document ID: 1334.90150
author: Zengfu Wang
author: Xuezhi Wang
author: Quan Pan
author: W. Moran
published in: Journal of Combinatorial Optimization
publication date: 2015-11-03T00:00:00Z
review text: A submodular function \(f:2^{X} \rightarrow \mathbb{R}_{+}\) is \textit{strong submodular}, if \( \forall A, B \subseteq X, \forall j \in X \setminus (A \cup B)\), \(f(A \cup \{j\})+f(B \cup \{j\})-f((A \cap B) \cup \{j\})-f(A \cup B\cup \{j\}) \leq f(A)+f(B)-f(A \cap B)-f(A \cup B)\). For a submodular and non-decreasing such function \(f\) and a matroid \(M=(X,\mathcal{I})\), the authors consider the optimization problem \(\max \{f(S): S \in \mathcal{I}\}\). Based on the \textit{(standard) continuous greedy algorithm (SCGA)} introduced by \textit{J. Vondrák} [RIMS Kôkyûroku Bessatsu B23, 253--266 (2010; Zbl 1219.68109)], an \textit{accelerated continuous greedy algorithm (ACGA)} is presented, which achieves the same degree of approximation as that of \(SCGA\), namely \(1/c(1-e^{-c}-\epsilon)\) for any \(\epsilon >0\), and where \(c\) is the curvature with respect to the optimum, but which substantially reduces the computational expense by removing redundant computational steps. Comparative computational results are given for weighted set coverage and strong submodular welfare problems.
Mathematics Subject Classification ID: 90C27
Mathematics Subject Classification ID: 90C59
zbMATH DE Number: 6503870
zbMATH Keywords: monotone submodular set function
zbMATH Keywords: matroid
zbMATH Keywords: continuous greedy algorithm
zbMATH Keywords: approximation algorithm
reviewed by: Reinhardt Euler
MaRDI profile type: Publication
full work available at URL: s10878-013-9685-x
OpenAlex ID: W2009120665
cites work: Pipage rounding: a new method of constructing algorithms with proven performance guarantee
cites work: Comments on bases in dependence structures
cites work: Maximizing a Monotone Submodular Function Subject to a Matroid Constraint
cites work: Maximizing non-monotone submodular set functions subject to different constraints: combined algorithms
cites work: A threshold of ln n for approximating set cover
cites work: The power of local search: maximum coverage over a matroid
cites work: Q4196269
cites work: Submodularity, Supermodularity, and Higher-Order Monotonicities of Pseudo-Boolean Functions
cites work: Inapproximability results for combinatorial auctions with submodular utility functions
cites work: Q4633865
cites work: Combinatorial auctions with decreasing marginal utilities
cites work: An analysis of approximations for maximizing submodular set functions—I
cites work: Best Algorithms for Approximating the Maximum of a Submodular Set Function
cites work: A note on maximizing a submodular set function subject to a knapsack constraint
cites work: Q3549686
cites work: Q2999661
DOI: 10.1007/S10878-013-9685-X
Recommended article: Q2999661
Recommended article: Submodular set functions, matroids and the greedy algorithm: Tight worst- case bounds and some generalizations of the Rado-Edmonds theorem
Recommended article: Fast algorithms for maximizing submodular functions
Recommended article: Q3549686
Recommended article: Optimal Approximation for Submodular and Supermodular Optimization with Bounded Curvature
Recommended article: Deterministic \(\boldsymbol{(\unicode{x00BD}+\varepsilon)}\) -Approximation for Submodular Maximization over a Matroid
Recommended article: Deterministic (½ + ε)-Approximation for Submodular Maximization over a Matroid
Recommended article: Maximizing non-monotone submodular set functions subject to different constraints: combined algorithms
description: scientific article; zbMATH DE number 6503870