We consider an assortment optimization problem where a customer chooses a
single item from a sequence of sets shown to her, while limited inventories
constrain the items offered to customers over time. In the special case where
all of the assortments have size one, our problem captures the online
stochastic matching with timeouts problem. For this problem, we derive a
polynomial-time approximation algorithm which earns at least 1-ln(2-1/e), or
0.51, of the optimum. This improves upon the previous-best approximation ratio
of 0.46, and furthermore, we show that it is tight. For the general assortment
problem, we establish the first constant-factor approximation ratio of 0.09 for
the case that different types of customers value items differently, and an
approximation ratio of 0.15 for the case that different customers value each
item the same. Our algorithms are based on rounding an LP relaxation for
multi-stage assortment optimization, and improve upon previous randomized
rounding schemes to derive the tight ratio of 1-ln(2-1/e).

我们考虑了一种混合物优化问题，针对在线随机匹配的情况，我们提出了一种多项式时间近似算法，其近似比为至少 1-ln (2-1 /e) 或 0.51，并基于线性规划松弛进一步改进了以前的随机舍入方案。在一般的混合物问题中，我们建立了第一个常数因子近似比为 0.09 的情况，这种情况下不同类型的客户赋予不同价值，并建立了近似比为 0.15 的情况，即不同客户赋予每个项目相同的价值。

具有库存限制的多阶段多客户组合优化

Multi-stage and Multi-customer Assortment Optimization with Inventory  Constraints

In this paper we consider the Stochastic Matching problem, which is motivated
by applications in kidney exchange and online dating. We are given an
undirected graph in which every edge is assigned a probability of existence and
a positive profit, and each node is assigned a positive integer called timeout.
We know whether an edge exists or not only after probing it. On this random
graph we are executing a process, which one-by-one probes the edges and
gradually constructs a matching. The process is constrained in two ways: once
an edge is taken it cannot be removed from the matching, and the timeout of
node $v$ upper-bounds the number of edges incident to $v$ that can be probed.
The goal is to maximize the expected profit of the constructed matching.
For this problem Bansal et al. (Algorithmica 2012) provided a
$3$-approximation algorithm for bipartite graphs, and a $4$-approximation for
general graphs. In this work we improve the approximation factors to $2.845$
and $3.709$, respectively.
We also consider an online version of the bipartite case, where one side of
the partition arrives node by node, and each time a node $b$ arrives we have to
decide which edges incident to $b$ we want to probe, and in which order. Here
we present a $4.07$-approximation, improving on the $7.92$-approximation of
Bansal et al.
The main technical ingredient in our result is a novel way of probing edges
according to a random but non-uniform permutation. Patching this method with an
algorithm that works best for large probability edges (plus some additional
ideas) leads to our improved approximation factors.

本文研究了随机匹配问题，提出一种能够提高精度的探测边的新方法和其在最大化构建匹配的期望收益中的应用，尤其在求解在线偏二分图情况时取得了显著提升。

随机匹配问题的改进近似算法

Improved Approximation Algorithms for Stochastic Matching

The stochastic matching problem deals with finding a maximum matching in a
graph whose edges are unknown but can be accessed via queries. This is a
special case of stochastic $k$-set packing, where the problem is to find a
maximum packing of sets, each of which exists with some probability. In this
paper, we provide edge and set query algorithms for these two problems,
respectively, that provably achieve some fraction of the omniscient optimal
solution.
Our main theoretical result for the stochastic matching (i.e., $2$-set
packing) problem is the design of an \emph{adaptive} algorithm that queries
only a constant number of edges per vertex and achieves a $(1-\epsilon)$
fraction of the omniscient optimal solution, for an arbitrarily small
$\epsilon>0$. Moreover, this adaptive algorithm performs the queries in only a
constant number of rounds. We complement this result with a \emph{non-adaptive}
(i.e., one round of queries) algorithm that achieves a $(0.5 - \epsilon)$
fraction of the omniscient optimum. We also extend both our results to
stochastic $k$-set packing by designing an adaptive algorithm that achieves a
$(\frac{2}{k} - \epsilon)$ fraction of the omniscient optimal solution, again
with only $O(1)$ queries per element. This guarantee is close to the best known
polynomial-time approximation ratio of $\frac{3}{k+1} -\epsilon$ for the
\emph{deterministic} $k$-set packing problem [Furer and Yu, 2013]
We empirically explore the application of (adaptations of) these algorithms
to the kidney exchange problem, where patients with end-stage renal failure
swap willing but incompatible donors. We show on both generated data and on
real data from the first 169 match runs of the UNOS nationwide kidney exchange
that even a very small number of non-adaptive edge queries per vertex results
in large gains in expected successful matches.

本文提出应用于随机匹配问题和随机集合覆盖问题的边缘和集合查询算法，分别基于自适应和非自适应策略，并将结果扩展到肾脏交换问题等实际问题上，结果表明即使在每个顶点上进行非常少量的非自适应边缘查询，也可以大大提高成功匹配率。

无知几乎是福利：少数查询下几近最优的随机匹配

Ignorance is Almost Bliss: Near-Optimal Stochastic Matching With Few  Queries

Consider a random graph model where each possible edge $e$ is present
independently with some probability $p_e$. Given these probabilities, we want
to build a large/heavy matching in the randomly generated graph. However, the
only way we can find out whether an edge is present or not is to query it, and
if the edge is indeed present in the graph, we are forced to add it to our
matching. Further, each vertex $i$ is allowed to be queried at most $t_i$
times. How should we adaptively query the edges to maximize the expected weight
of the matching? We consider several matching problems in this general
framework (some of which arise in kidney exchanges and online dating, and
others arise in modeling online advertisements); we give LP-rounding based
constant-factor approximation algorithms for these problems. Our main results
are the following:
We give a 4 approximation for weighted stochastic matching on general graphs,
and a 3 approximation on bipartite graphs. This answers an open question from
[Chen etal ICALP 09]. Combining our LP-rounding algorithm with the natural
greedy algorithm, we give an improved 3.46 approximation for unweighted
stochastic matching on general graphs.
We introduce a generalization of the stochastic online matching problem
[Feldman etal FOCS 09] that also models preference-uncertainty and timeouts of
buyers, and give a constant factor approximation algorithm.

本研究研究了一种随机图模型和匹配问题，提出了基于线性规划和贪心的近似算法，并探讨了匹配问题在肾脏交流和在线广告上的应用。