（12月25日)Min-cost Bipartite Perfect Matching with Delays

报告题目: Min-cost Bipartite Perfect Matching with Delays

报告人：王�弋博士（瑞士苏黎世联邦理工学院）

时间: 12月25日下午4:00-5:00

地点：玉泉校区工商楼2楼报告厅（200-9）

摘要：The problem of min-cost matching with delays is an  online problem defined on an underlying n-point metric space as follows. An  adversary presents real-time requests online at points of the metric space, and  the algorithm is required to match them, possibly after keeping them waiting for  some time. The cost incurred is the sum of the distances between matched pairs  of requests (the connection cost), and the sum of the waiting times of the  requests (the delay cost). This objective exhibits a natural tradeoff between  minimizing the distances and the cost of waiting for better matches. The problem  comes in two flavors: the non-bipartite one (MPMD) and the bipartite one  (MBPMD). In the non-bipartite version, any two requests can be matched, while on  the other hand, in the bipartite version, each request is either positive or  negative, and two requests may be matched only if they have opposite polarities.  The problem of non-bipartite min-cost matching with delays was recently  introduced by Emek et al., (STOC’16). For an n-point metric space in which the  largest distance is $Delta$ times the smallest, Emek et al. give an algorithm  with a competitive ratio $O(log^2{n}+log{Delta})$. We present an improved  algorithm with a competitive ratio of $O(log n)$, removing the dependence on  $Delta$. We also prove a lower bound of  $Omegaleft(rac{log{n}}{log{log{n}}} ight)$ on the competitive ratio of  any randomized algorithm, almost matching the upper bound. For bipartite  min-cost matching with delays, we give an $O(log n)$-competitive algorithm, and  prove a lower bound of  $Omegaleft(sqrt{rac{log{n}}{log{log{n}}}} ight)$.

The core of our algorithms for MPMD and MBPMD are  deterministic algorithms for the respective problems on metrics induced by  edge-weighted trees of height h. The algorithms’ cost is guaranteed to be at  most O(1) times the connection cost plus O(h) times the delay cost of every  feasible solution. The reduction from M(B)PMD on arbitrary metrics to M(B)PMD on  tree metrics is achieved using the result on embedding n-point metric spaces  into distributions over weighted hierarchically separated trees of height $O(log  n$), with distortion $O(log n) $(Fakcharoenphol et al., JCSS’04 and Bansal et  al., JACM’15). Both of our lower bounds are attained on the metric space of n  equally spaced points on a line. 

联系人：郭正初（guozc@zju.edu.cn)