We study the online stochastic matching problem. Consider a bipartite graph
with offline vertices on one side, and with i.i.d.online vertices on the other
side. The offline vertices and the distribution of online vertices are known to
the algorithm beforehand. The realization of the online vertices, however, is
revealed one at a time, upon which the algorithm immediately decides how to
match it. For maximizing the cardinality of the matching, we give a
$0.711$-competitive online algorithm, which improves the best previous ratio of
$0.706$. When the offline vertices are weighted, we introduce a
$0.7009$-competitive online algorithm for maximizing the total weight of the
matched offline vertices, which improves the best previous ratio of $0.662$.
Conceptually, we find that the analysis of online algorithms simplifies if
the online vertices follow a Poisson process, and establish an approximate
equivalence between this Poisson arrival model and online stochstic matching.
Technically, we propose a natural linear program for the Poisson arrival model,
and demonstrate how to exploit its structure by introducing a converse of
Jensen's inequality. Moreover, we design an algorithmic amortization to replace
the analytic one in previous work, and as a result get the first
vertex-weighted online stochastic matching algorithm that improves the results
in the weaker random arrival model.

研究在线随机匹配问题，提出了基于 Poisson 到达模型的 0.711 竞争性算法和近似等价性证明，应用线性规划和 Jensen 不等式实现算法优化，推出第一个在较弱随机到达模型下的节点加权在线随机匹配算法。

在线随机匹配，泊松到达和自然线性规划

Online Stochastic Matching, Poisson Arrivals, and the Natural Linear  Program

We study the problem of matching agents who arrive at a marketplace over time
and leave after d time periods. Agents can only be matched while they are
present in the marketplace. Each pair of agents can yield a different match
value, and the planner's goal is to maximize the total value over a finite time
horizon. First we study the case in which vertices arrive in an adversarial
order. We provide a randomized 0.25-competitive algorithm building on a result
by Feldman et al. (2009) and Lehman et al. (2006). We extend the model to the
case in which departure times are drawn independently from a distribution with
non-decreasing hazard rate, for which we establish a 1/8-competitive algorithm.
When the arrival order is chosen uniformly at random, we show that a batching
algorithm, which computes a maximum-weighted matching every (d+1) periods, is
0.279-competitive.

研究匹配到一个时间市场上的代理人的问题，该论文提出了不同的算法来解决顺序不同的场景，并在独立抽样的时间场景中实现 1/8-competitive 算法，对于随机顺序情况下提出了一个每 (d+1) 阶段计算最大加权匹配的 batching 算法，并且证明了其 0.279-competitive 的竞争性。

带期限的最大权重在线匹配

Maximum Weight Online Matching with Deadlines

This paper shows that one can be competitive with the k-means objective while
operating online. In this model, the algorithm receives vectors v_1,...,v_n one
by one in an arbitrary order. For each vector the algorithm outputs a cluster
identifier before receiving the next one. Our online algorithm generates ~O(k)
clusters whose k-means cost is ~O(W*). Here, W* is the optimal k-means cost
using k clusters and ~O suppresses poly-logarithmic factors. We also show that,
experimentally, it is not much worse than k-means++ while operating in a
strictly more constrained computational model.

在线聚类算法实现了与 k 均值算法相同的聚类效果，其算法复杂度显著低于 k-means++。

一个在线 K-Means 聚类算法

An Algorithm for Online K-Means Clustering

We study the following vertex-weighted online bipartite matching problem:
$G(U, V, E)$ is a bipartite graph. The vertices in $U$ have weights and are
known ahead of time, while the vertices in $V$ arrive online in an arbitrary
order and have to be matched upon arrival. The goal is to maximize the sum of
weights of the matched vertices in $U$. When all the weights are equal, this
reduces to the classic \emph{online bipartite matching} problem for which Karp,
Vazirani and Vazirani gave an optimal $\left(1-\frac{1}{e}\right)$-competitive
algorithm in their seminal work~\cite{KVV90}. Our main result is an optimal
$\left(1-\frac{1}{e}\right)$-competitive randomized algorithm for general
vertex weights. We use \emph{random perturbations} of weights by appropriately
chosen multiplicative factors. Our solution constitutes the first known
generalization of the algorithm in~\cite{KVV90} in this model and provides new
insights into the role of randomization in online allocation problems. It also
effectively solves the problem of \emph{online budgeted allocations}
\cite{MSVV05} in the case when an agent makes the same bid for any desired
item, even if the bid is comparable to his budget - complementing the results
of \cite{MSVV05, BJN07} which apply when the bids are much smaller than the
budgets.

研究了一种顶点加权的在线二分图匹配算法，使用随机扰动顶点权重的多样化方法，得到了一种最佳 $(1-rac {1} {e})$ 竞争性算法，该算法是现有算法的一般化，为在线资源分配问题提供了新的见解。