Tight Bounds for Secretary Matching in General Graphs

• 成果类型: Article; Early Access
• 署名作者: Ezra, Tomer; Feldman, Michal; Gravin, Nikolai; Tang, Zhihao (Gavin)
• 署名单位: Harvard University; Tel Aviv University; Microsoft; MICROSOFT ISRAEL; Shanghai University of Finance & Economics
• 刊物名称: MATHEMATICS OF OPERATIONS RESEARCH
• ISSN/ISSBN: 0364-765X
• DOI: 10.1287/moor.2022.0206
• 发表日期: 2024
• 关键词: online; algorithms; mechanism

摘要

Online algorithms for secretary matching in bipartite weighted graphs have been studied extensively in recent years. We generalize this study to secretary matching in general weighted graphs. In our model, vertices arrive online in a uniformly random order; upon the arrival of a vertex v , the weights of edges from v to all previously arriving vertices are revealed, and the algorithm decides which of these edges, if any, to include in the matching. We provide a tight 5/12-competitive algorithm for this setting. Interestingly, it outperforms the best possible algorithm for secretary matching in bipartite graphs with one-sided arrival, which cannot be better than 1/ e-competitive.