Publications

2024

1. Online Matching Meets Sampling Without Replacement

   Zhiyi Huang, Chui Shan Lee, Jianqiao Lu, and Xinkai Shu

   In Proceedings of the 20th Conference on Web and Internet Economics (WINE 2024), Edinburgh, United Kingdom, December 2-5, 2024

   Abs arXiv

   Sampling without replacement is a natural online rounding strategy for converting fractional bipartite matching into an integral one. In Online Bipartite Matching, we can use the Balance algorithm to fractionally match each online vertex, and then sample an unmatched offline neighbor with probability proportional to the fractional matching. In Online Stochastic Matching, we can take the solution to a linear program relaxation as a reference, and then match each online vertex to an unmatched offline neighbor with probability proportional to the fractional matching of the online vertex’s type. On the one hand, we find empirical evidence that online matching algorithms based on sampling without replacement outperform existing algorithms. On the other hand, the literature offers little theoretical understanding of the power of sampling without replacement in online matching problems. This paper fills the gap in the literature by giving the first non-trivial competitive analyses of sampling without replacement for online matching problems. In Online Stochastic Matching, we develop a potential function analysis framework to show that sampling without replacement is at least \(0.707\)-competitive. The new analysis framework further allows us to derandomize the algorithm to obtain the first polynomial-time deterministic algorithm that breaks the \(1-\frac1e\) barrier. In Online Bipartite Matching, we show that sampling without replacement provides provable online correlated selection guarantees when the selection probabilities correspond to the fractional matching chosen by the Balance algorithm. As a result, we prove that sampling without replacement is at least \(0.513\)-competitive for Online Bipartite Matching.

2023

1. Online Nash Welfare Maximization Without Predictions

   Zhiyi Huang, Minming Li, Xinkai Shu, and Tianze Wei

   In Proceedings of the 19th Conference on Web and Internet Economics (WINE 2023), Shanghai, China, December 4-8, 2023

   Abs arXiv HTML

   The maximization of Nash welfare, which equals the geometric mean of agents’ utilities, is widely studied because it balances efficiency and fairness in resource allocation problems. Banerjee, Gkatzelis, Gorokh, and Jin (2022) recently introduced the model of online Nash welfare maximization for \(T\) divisible items and \(N\) agents with additive utilities with predictions of each agent’s utility for receiving all items. They gave online algorithms whose competitive ratios are logarithmic. We initiate the study of online Nash welfare maximization without predictions, assuming either that the agents’ utilities for receiving all items differ by a bounded ratio, or that their utilities for the Nash welfare maximizing allocation differ by a bounded ratio. We design online algorithms whose competitive ratios only depend on the logarithms of the aforementioned ratios of agents’ utilities and the number of agents.

2. A Randomized Algorithm for Single-Source Shortest Path on Undirected Real-Weighted Graphs

   Ran Duan, Jiayi Mao, Xinkai Shu, and Longhui Yin

   In Proceedings of the 64th IEEE Symposium on Foundations of Computer Science (FOCS 2023), Santa Cruz, USA, November 6-9, 2023

   Abs arXiv HTML

   In undirected graphs with real non-negative weights, we give a new randomized algorithm for the single-source shortest path (SSSP) problem with running time \(O(m\sqrt{\log n⋅\log\log n})\) in the comparison-addition model. This is the first algorithm to break the \(O(m+n\log n)\) time bound for real-weighted sparse graphs by Dijkstra’s algorithm with Fibonacci heaps. Previous undirected non-negative SSSP algorithms give time bound of \(O(mα(m,n)+\min{n\log n,n\log\log r})\) in comparison-addition model, where \(α\) is the inverse-Ackermann function and \(r\) is the ratio of the maximum-to-minimum edge weight [Pettie & Ramachandran 2005], and linear time for integer edge weights in RAM model [Thorup 1999]. Note that there is a proposed complexity lower bound of \(Ω(m+\min{n\log n,n\log\log r})\) for hierarchy-based algorithms for undirected real-weighted SSSP [Pettie & Ramachandran 2005], but our algorithm does not obey the properties required for that lower bound. As a non-hierarchy-based approach, our algorithm shows great advantage with much simpler structure, and is much easier to implement.

2022

1. The Power of Multiple Choices in Online Stochastic Matching

   Zhiyi Huang, Xinkai Shu, and Shuyi Yan

   In Proceedings of the 54th Annual ACM SIGACT Symposium on Theory of Computing (STOC 2022), Rome, Italy, June 20-24, 2022

   Abs arXiv HTML

   We study the power of multiple choices in online stochastic matching. Despite a long line of research, existing algorithms still only consider two choices of offline neighbors for each online vertex because of the technical challenge in analyzing multiple choices. This paper introduces two approaches for designing and analyzing algorithms that use multiple choices. For unweighted and vertex-weighted matching, we adopt the online correlated selection (OCS) technique into the stochastic setting, and improve the competitive ratios to \(0.716\), from \(0.711\) and \(0.7\) respectively. For edge-weighted matching with free disposal, we propose the Top Half Sampling algorithm. We directly characterize the progress of the whole matching instead of individual vertices, through a differential inequality. This improves the competitive ratio to \(0.706\), breaking the \(1-\frac1e\) barrier in this setting for the first time in the literature. Finally, for the harder edge-weighted problem without free disposal, we prove that no algorithms can be \(0.703\)-competitive, separating this setting from the aforementioned three.

2021

1. Online Stochastic Matching, Poisson Arrivals, and the Natural Linear Program

   Zhiyi Huang, and Xinkai Shu

   In Proceedings of the 53rd Annual ACM SIGACT Symposium on Theory of Computing (STOC 2021), Rome, Italy (virtually), June 21-25, 2021

   Abs arXiv HTML

   We study the online stochastic matching problem. Consider a bipartite graph with offline vertices on one side, and with i.i.d.online vertices on the other side. The offline vertices and the distribution of online vertices are known to the algorithm beforehand. The realization of the online vertices, however, is revealed one at a time, upon which the algorithm immediately decides how to match it. For maximizing the cardinality of the matching, we give a \(0.711\)-competitive online algorithm, which improves the best previous ratio of \(0.706\). When the offline vertices are weighted, we introduce a \(0.7009\)-competitive online algorithm for maximizing the total weight of the matched offline vertices, which improves the best previous ratio of \(0.662\). Conceptually, we find that the analysis of online algorithms simplifies if the online vertices follow a Poisson process, and establish an approximate equivalence between this Poisson arrival model and online stochstic matching. Technically, we propose a natural linear program for the Poisson arrival model, and demonstrate how to exploit its structure by introducing a converse of Jensen’s inequality. Moreover, we design an algorithmic amortization to replace the analytic one in previous work, and as a result get the first vertex-weighted online stochastic matching algorithm that improves the results in the weaker random arrival model.