1 Search Results for "Liu, Xingwu"


Document
Impatient Online Matching

Authors: Xingwu Liu, Zhida Pan, Yuyi Wang, and Roger Wattenhofer

Published in: LIPIcs, Volume 123, 29th International Symposium on Algorithms and Computation (ISAAC 2018)


Abstract
We investigate the problem of Min-cost Perfect Matching with Delays (MPMD) in which requests are pairwise matched in an online fashion with the objective to minimize the sum of space cost and time cost. Though linear-MPMD (i.e., time cost is linear in delay) has been thoroughly studied in the literature, it does not well model impatient requests that are common in practice. Thus, we propose convex-MPMD where time cost functions are convex, capturing the situation where time cost increases faster and faster. Since the existing algorithms for linear-MPMD are not competitive any more, we devise a new deterministic algorithm for convex-MPMD problems. For a large class of convex time cost functions, our algorithm achieves a competitive ratio of O(k) on any k-point uniform metric space. Moreover, our deterministic algorithm is asymptotically optimal, which uncover a substantial difference between convex-MPMD and linear-MPMD which allows a deterministic algorithm with constant competitive ratio on any uniform metric space.

Cite as

Xingwu Liu, Zhida Pan, Yuyi Wang, and Roger Wattenhofer. Impatient Online Matching. In 29th International Symposium on Algorithms and Computation (ISAAC 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 123, pp. 62:1-62:12, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)


Copy BibTex To Clipboard

@InProceedings{liu_et_al:LIPIcs.ISAAC.2018.62,
  author =	{Liu, Xingwu and Pan, Zhida and Wang, Yuyi and Wattenhofer, Roger},
  title =	{{Impatient Online Matching}},
  booktitle =	{29th International Symposium on Algorithms and Computation (ISAAC 2018)},
  pages =	{62:1--62:12},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-094-1},
  ISSN =	{1868-8969},
  year =	{2018},
  volume =	{123},
  editor =	{Hsu, Wen-Lian and Lee, Der-Tsai and Liao, Chung-Shou},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ISAAC.2018.62},
  URN =		{urn:nbn:de:0030-drops-100107},
  doi =		{10.4230/LIPIcs.ISAAC.2018.62},
  annote =	{Keywords: online algorithm, online matching, convex function, competitive analysis, lower bound}
}
  • Refine by Author
  • 1 Liu, Xingwu
  • 1 Pan, Zhida
  • 1 Wang, Yuyi
  • 1 Wattenhofer, Roger

  • Refine by Classification
  • 1 Theory of computation → Online algorithms

  • Refine by Keyword
  • 1 competitive analysis
  • 1 convex function
  • 1 lower bound
  • 1 online algorithm
  • 1 online matching

  • Refine by Type
  • 1 document

  • Refine by Publication Year
  • 1 2018

Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail