（12月25日)Min-cost Bipartite Perfect Matching with Delays
 来源： 陈黎   发布时间：2017-12-19   阅读次数：709
 报告题目: 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 $\Omega\left(\frac{\log{n}}{\log{\log{n}}}\right)$ 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 $\Omega\left(\sqrt{\frac{\log{n}}{\log{\log{n}}}}\right)$. 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.  联系人：郭正初（