耐心
计算机科学
匹配(统计)
排名(信息检索)
产品(数学)
二部图
数学优化
数学
人工智能
理论计算机科学
统计
几何学
神学
图形
哲学
作者
Brian Brubach,Nathaniel Grammel,Will Ma,Aravind Srinivasan
出处
期刊:Cornell University - arXiv
日期:2019-07-08
标识
DOI:10.48550/arxiv.1907.03963
摘要
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. We complement these positive results by presenting three additional negative results relating to these problems.
科研通智能强力驱动
Strongly Powered by AbleSci AI