中央研究院 資訊科學研究所

活動訊息

友善列印

列印可使用瀏覽器提供的(Ctrl+P)功能

允許延遲的最小費用(二部)完美匹配

:::

允許延遲的最小費用(二部)完美匹配

  • 講者王彧弋 博士 (蘇黎世聯邦理工學院)
    邀請人:鐘楷閔
  • 時間2019-11-04 (Mon.) 10:30 ~ 12:30
  • 地點資訊所新館106演講廳
摘要

我們這個報告談論壹個比較新的問題:允許延遲的最小費用(二部)完美匹配(MBPMD)。在這個問題中,所有的請求,以在線的方式,出現在事先確定的度量空間中的結點上。與傳統的在線匹配問題不同,在壹個請求出現的時候,我們並不要求算法馬上為它服務。當然,延遲的服務要付出相應的時間代價。這個問題的目標是最小化總費用,包括匹配兩點間的空間代價,以及等待所帶來的時間代價。在設計相關算法的時候,我們必須找到壹個合適的折衷辦法。這些折衷的原則在現實場景中經常出現,例如,在使用Uber時,平臺需要在好的匹配和快的匹配中做出選擇。我們的結果包含了很多部分。其中最具壹般性的結果是競爭比為O(log n)的算法,n是度量空間的大小。我們也證明了競爭比的壹個下界Omega(log n / log log n)。在這個報告中,我們主要介紹這個競爭比為O(log n)的算法,同時總結已存在的其他結果。