报告人：Mingwei Yang, Stanford University

时间：12月10日（星期二）10:00am

地点：静园五院204

Host：王昊泽，图灵班2022级

Abstract

We study the stochastic online metric matching problem. In this problem, m servers and n requests are located in a metric space, where all servers are available upfront and requests arrive one at a time. In particular, servers are adversarially chosen, and requests are independently drawn from a known distribution. Upon the arrival of a new request, it needs to be immediately and irrevocably matched to a free server, resulting in a cost of their distance.  The objective is to minimize the total matching cost.

In this paper, we show that the problem can be reduced to a more accessible setting where both servers and requests are drawn from the same distribution by incurring a moderate cost. Combining our reduction with previous techniques, for [0, 1]ᵈ with various choices of distributions, we achieve improved competitive ratios and nearly optimal regrets in both balanced and unbalanced markets. In particular, we give 𝒪(1)-competitive algorithms for 𝑑 ⩾ 3 in both balanced and unbalanced markets with smooth distributions. Our algorithms improve on the 𝒪((log log log 𝑛)²) competitive ratio of Gupta et al. (ICALP'19) for balanced markets in various regimes, and provide the first positive results for unbalanced markets.

Biography

Mingwei Yang is a second-year Ph.D. student in Operational Research at Stanford University. Prior to joining Stanford, he received his bachelor's degree at Turing Class, Peking University. His research interests broadly lie in theoretical computer science with recent focus on counting and sampling algorithms, online matching algorithms, and fair division.

about CS Peer Talk

作为活动的发起人，我们来自北京大学图灵班科研活动委员会，主要由图灵班各年级同学组成。我们希望搭建一个CS同学交流的平台，促进同学间的交流合作，帮助同学练习展示，同时增进友谊。

目前在计划中的系列包括但不限于：

· 教程系列：学生讲者为主，介绍自己的研究领域

· 研究系列：学生讲者为主，介绍自己的研究成果

· 客座系列：邀请老师做主题报告

除非报告人特别要求，报告默认是非公开的，希望营造一个自由放松但又互相激励的交流氛围。

主讲嘉宾招募

如果你愿意和大家分享你的学术成果、经历经验，总结回顾、触发新思，欢迎报名自荐。

主讲人报名：发邮件至 cs_research_tc@163.com，并抄送 cfcs@pku.edu.cn，写明想讲的题目、内容及时间。