Scholarlink

The min-cost perfect matching with delays problem on two sources (2-MPMD) captures the critical trade-off between match and wait, and has been extensively studied recently. A 3-competitive deterministic algorithm and a 2-competitive randomized algorithm were proposed, where 2 is also the lower bound. In this paper, we consider a variation where an algorithm is allowed to look ahead for certain time, exploring the power of future knowledge in online decisions. We devise a \(\frac{3+\tau }{1+\tau }\) -competitive deterministic algorithm and a randomized algorithm which is \(\left( 2-(2\sqrt{2}-2)\tau \right) \) -competitive when \(\tau \le \frac{1}{2}\) and \(\left( 2 + 2\tau -\sqrt{4\tau ^2 + 4\tau - 1}\right) \) -competitive otherwise, where \(\tau \) is the length of the foreseen time period.

错误：搜索内容不能为空，请输入英文关键词
错误：关键词超出字数限制，请精简
高级检索

MPMD on Two Sources with Lookahead

  • 会议论文

  • 发表日期：

    2025年

查看全文
  • Enze Sun,
  • Bo Wang,
  • Quan Xue,
  • Mengshi Zhao,
  • Zixuan Zhu

摘要

The min-cost perfect matching with delays problem on two sources (2-MPMD) captures the critical trade-off between match and wait, and has been extensively studied recently. A 3-competitive deterministic algorithm and a 2-competitive randomized algorithm were proposed, where 2 is also the lower bound. In this paper, we consider a variation where an algorithm is allowed to look ahead for certain time, exploring the power of future knowledge in online decisions. We devise a \(\frac{3+\tau }{1+\tau }\) -competitive deterministic algorithm and a randomized algorithm which is \(\left( 2-(2\sqrt{2}-2)\tau \right) \) -competitive when \(\tau \le \frac{1}{2}\) and \(\left( 2 + 2\tau -\sqrt{4\tau ^2 + 4\tau - 1}\right) \) -competitive otherwise, where \(\tau \) is the length of the foreseen time period.