Tight Bounds for Secretary Matching in General Graphs

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. Funding: The work is supported by the National Natural Science Foundation of China (NSFC) [Grant 61932002]. The work of M. Feldman was partially supported by the European Research Council (ERC) under the European Union’s Horizon 2020 research and innovation program [Grant 866132] and by the Israel Science Foundation [Grant 317/17]. Z. (G.) Tang and N. Gravin are partially supported by the Key Laboratory of Interdisciplinary Research of Computation and Economics (Shanghai University of Finance and Economics), Ministry of Education. N. Gravin is also supported by the NSFC [Grant 62150610500]. T. Ezra is supported by the Harvard University Center of Mathematical Sciences and Applications.