Randomization is a fundamental tool used in many theoretical and practical
areas of computer science. We study here the role of randomization in the area
of submodular function maximization. In this area most algorithms are
randomized, and in almost all cases the approximation ratios obtained by
current randomized algorithms are superior to the best results obtained by
known deterministic algorithms. Derandomization of algorithms for general
submodular function maximization seems hard since the access to the function is
done via a value oracle. This makes it hard, for example, to apply standard
derandomization techniques such as conditional expectations. Therefore, an
interesting fundamental problem in this area is whether randomization is
inherently necessary for obtaining good approximation ratios.
In this work we give evidence that randomization is not necessary for
obtaining good algorithms by presenting a new technique for derandomization of
algorithms for submodular function maximization. Our high level idea is to
maintain explicitly a (small) distribution over the states of the algorithm,
and carefully update it using marginal values obtained from an extreme point
solution of a suitable linear formulation. We demonstrate our technique on two
recent algorithms for unconstrained submodular maximization and for maximizing
submodular function subject to a cardinality constraint. In particular, for
unconstrained submodular maximization we obtain an optimal deterministic
$1/2$-approximation showing that randomization is unnecessary for obtaining
optimal results for this setting.

证明了在许多计算机科学中随机化的作用，以及针对次模函数最大化领域的一种新的去随机化算法技术

子模最大化问题的确定性算法

Deterministic Algorithms for Submodular Maximization Problems

A wide variety of problems in machine learning, including exemplar
clustering, document summarization, and sensor placement, can be cast as
constrained submodular maximization problems. A lot of recent effort has been
devoted to developing distributed algorithms for these problems. However, these
results suffer from high number of rounds, suboptimal approximation ratios, or
both. We develop a framework for bringing existing algorithms in the sequential
setting to the distributed setting, achieving near optimal approximation ratios
for many settings in only a constant number of MapReduce rounds. Our techniques
also give a fast sequential algorithm for non-monotone maximization subject to
a matroid constraint.

通过将现有算法从顺序设定应用到分布式设定，仅利用恒定数量的 MapReduce 循环，在许多设置中实现了接近最优的近似比率。我们的技术还为满足矩阵约束的非单调最大化提供了快速的顺序算法。

分布式次模最大化的新框架

A New Framework for Distributed Submodular Maximization

Result diversification is an important aspect in web-based search, document
summarization, facility location, portfolio management and other applications.
Given a set of ranked results for a set of objects (e.g. web documents,
facilities, etc.) with a distance between any pair, the goal is to select a
subset $S$ satisfying the following three criteria: (a) the subset $S$
satisfies some constraint (e.g. bounded cardinality); (b) the subset contains
results of high "quality"; and (c) the subset contains results that are
"diverse" relative to the distance measure. The goal of result diversification
is to produce a diversified subset while maintaining high quality as much as
possible. We study a broad class of problems where the distances are a metric,
where the constraint is given by independence in a matroid, where quality is
determined by a monotone submodular function, and diversity is defined as the
sum of distances between objects in $S$. Our problem is a generalization of the
{\em max sum diversification} problem studied in \cite{GoSh09} which in turn is
a generaliztion of the {\em max sum $p$-dispersion problem} studied extensively
in location theory. It is NP-hard even with the triangle inequality. We propose
two simple and natural algorithms: a greedy algorithm for a cardinality
constraint and a local search algorithm for an arbitary matroid constraint. We
prove that both algorithms achieve constant approximation ratios.

研究了一类问题，该问题的距离是一个度量，约束是一个 matroid 中的独立性，质量则由单调子模函数确定，多样性定义为 S 中物体之间的距离之和，提出了两种算法：基于基数约束的贪心算法和基于任意 matroid 约束的局部搜索算法，并证明了两种算法都达到了恒定的逼近比。