ZWZhiang Wu
Zhiang Wu
*This is an algorithmically generated author record based on publicly available information.
Current Organizations / Institutes
The organizations/institutes from the scholar's latest article
Research Subjects
Zhiang Wu has a total of 5 co-authors. Here are the top co-authors by number of shared publications:
- Aocheng Shen
Huazhong University of Science and Technology
2 shared publications - Hanrui Jiang
Huazhong University of Science and Technology
2 shared publications - Junkai Song
The University of Hong Kong
2 shared publications - Qiankun Zhang
School of Cyber Science and Engineering, Huazhong University of Science and Technology, Wuhan, China and Key Laboratory of Cyberspace Security, Ministry of Education of China, Zhengzhou, China
2 shared publications - Zhiyi Huang
The University of Hong Kong
2 shared publications
Latest Publications
- 31 December 2023
- Published by Springer Nature
- p. 384-401
Online Matching with Stochastic Rewards: Advanced Analyses Using Configuration Linear Programs
- 31 December 2023
- Published by Springer Nature
- p. 384-401
Online Matching with Stochastic Rewards: Advanced Analyses Using Configuration Linear Programs
- Open Access
Online Matching with Stochastic Rewards: Advanced Analyses Using Configuration Linear Programs
Mehta and Panigrahi (2012) proposed Online Matching with Stochastic Rewards, which generalizes the Online Bipartite Matching problem of Karp, Vazirani, and Vazirani (1990) by associating the edges with success probabilities. This new feature captures the pay-per-click model in online advertising. Recently, Huang and Zhang (2020) studied this problem under the online primal dual framework using the Configuration Linear Program (LP), and got the best known competitive ratios of the Stochastic Balance algorithm. Their work suggests that the more expressive Configuration LP is more suitable for this problem than the Matching LP. This paper advances the theory of Configuration LP in two directions. Our technical contribution includes a characterization of the joint matching outcome of an offline vertex and \emph{all its neighbors}. This characterization may be of independent interest, and is aligned with the spirit of Configuration LP. By contrast, previous analyses of Ranking generally focus on only one neighbor. Second, we designed a Stochastic Configuration LP that captures a stochastic benchmark proposed by Goyal and Udwani (2020), who used a Path-based LP. The Stochastic Configuration LP is smaller and simpler than the Path-based LP. Moreover, using the new LP we improved the competitive ratio of Stochastic Balance from $0.596$ to $0.611$ when the success probabilities are infinitesimal, and to $0.613$ when the success probabilities are further equal.Open AccessOnline Matching with Stochastic Rewards: Advanced Analyses Using Configuration Linear Programs
Mehta and Panigrahi (2012) proposed Online Matching with Stochastic Rewards, which generalizes the Online Bipartite Matching problem of Karp, Vazirani, and Vazirani (1990) by associating the edges with success probabilities. This new feature captures the pay-per-click model in online advertising. Recently, Huang and Zhang (2020) studied this problem under the online primal dual framework using the Configuration Linear Program (LP), and got the best known competitive ratios of the Stochastic Balance algorithm. Their work suggests that the more expressive Configuration LP is more suitable for this problem than the Matching LP. This paper advances the theory of Configuration LP in two directions. Our technical contribution includes a characterization of the joint matching outcome of an offline vertex and \emph{all its neighbors}. This characterization may be of independent interest, and is aligned with the spirit of Configuration LP. By contrast, previous analyses of Ranking generally focus on only one neighbor. Second, we designed a Stochastic Configuration LP that captures a stochastic benchmark proposed by Goyal and Udwani (2020), who used a Path-based LP. The Stochastic Configuration LP is smaller and simpler than the Path-based LP. Moreover, using the new LP we improved the competitive ratio of Stochastic Balance from $0.596$ to $0.611$ when the success probabilities are infinitesimal, and to $0.613$ when the success probabilities are further equal.