We study generalizations of online bipartite matching in which each arriving vertex (customer) views a ranked list of offline vertices (products) and matches to (purchases) the first one they deem acceptable. The number of products that the customer has patience to view can be stochastic and dependent on the products seen. We develop a framework that views the interaction with each customer as an abstract resource consumption process, and derive new results for these online matching problems under the adversarial, non-stationary, and IID arrival models, assuming we can (approximately) solve the product ranking problem for each single customer. To that end, we show new results for product ranking under two cascade-click models: an optimal algorithm when each item has its own hazard rate for making the customer depart, and a 1/2-approximate algorithm when the customer has a general item-independent patience distribution. We also present a constant-factor 0.027-approximate algorithm in a new model where items are not initially available and arrive over time. Finally, we present three negative results of interest: one formalizing the notion of a stochasticity gap exhibited by existing approaches to this problem, an example showing the analysis of SimpleGreedy in existing work to be tight, and another one for the single-customer problem in which any constant-factor approximation is impossible when compared to a benchmark that knows the realization of the patience in advance.
翻译:我们研究在线双边对齐的概括性,即每个抵达的顶端(客户)都会看到一个分级的离线脊椎(产品)列表,并与他们认为可接受的第一个(购买)列表相匹配。客户有耐心看的产品数量可以是随机的,取决于所看到的产品数量。我们开发了一个框架,将与每个客户的互动视为一个抽象的资源消耗过程,并在对抗性、非静止和ID抵达模式下为这些在线匹配问题得出新的结果,假设我们能够(约)解决每个客户的产品排名问题。为此,我们展示了两个级联点击模式下产品排名的新结果:当每个项目有其自身危险率使客户离开时,最优化的算法,以及当客户有一个一般性的不依赖性耐心分布时,1/2的近似算法。我们还在一个新的模型中提出一个不变的 0.027 准的算法,在这个新模型中,项目最初没有可用,而且会到达时间。最后,我们展示了三种负面的利息结果:一个正式化概念,在两个级联点下排列的产品排序:当每个项目有其自身的风险率时,一个对现有的简单度分析方法显示一个在目前实现的实现的精确度上,一个比较的精确度的差距,一个对现有的精确度上,一个直观上,一个对一个比较一个比较一个比较一个比较一个比较,一个现有的方法将显示一个比较一个比较一个简单的实现问题在目前的方法,一个比较一个比较。