Last Modified: Nov 24, 2023
Xiaowei Wu (吴晓伟)
Room N21-5011a
State Key Laboratory in the Internet of Things for Smart City (IOTSC)
Faculty of Science and Technology, University of Macau
Google Site: https://sites.google.com/site/wxw0711/ (Up-to-date)
Email: xiaoweiwu AT um.edu.mo
Short Biography. I’m currently an Assistant Professor in the Department of Computer and Information Science with the State Key Laboratory of Internet of Things for Smart City (IOTSC) at University of Macau.
Before joining the University of Macau, I worked as a Postdoctoral Fellow with Prof. Monika Henzinger at the Faculty of Computer Science, University of Vienna. I received my PhD degree from the University of Hong Kong (HKU) under the supervision of Dr. Hubert Chan. I received my BEng degree from University of Science and Technology of China (USTC).
Opennings
Postdoc, PhD, & Research Assistant at University of Macau
We regularly have several positions for Postdoc, Phd, and Research Assistant (visiting scholar) each year. If you are interested in my research and want to join our group, please don’t hesitate to send me an email with your CV and research interests.
Students with ACM programming contest experience will have priority.
Teaching
- CISC2006 Algorithm Design and Analysis: Spring 2022, Spring 2023, Spring 2024
- CISC7007 Design and Analysis of Algorithms: Spring 2021, Fall 2022, Fall 2023
- CISC3027 Special Topics in Computer and Information Science: Fall 2020, Fall 2021
Research Interests
I am broadly interested in theoretical computer science and algorithmic game theory. My research interests span various topics in online algorithms, approximation algorithms, dynamic data structure, computational social choice, game theory and truthful mechanism design.
Seleted Journal Publications
Check dblp for the full list of publications.
* Authors are listed in alphabetical order (why?).
Towards a Better Understanding of Randomized Greedy Matching
Zhihao Gavin Tang, Xiaowei Wu* and Yuhao Zhang
JACM 2023: Journal of the ACM, Accepted. 2023
Deterministic Near-Optimal Approximation Algorithms for Dynamic Set Cover
Sayan Bhattacharya, Monika Henzinger, Danupon Nanongkai and Xiaowei Wu*
SICOMP 2023: SIAM Journal on Computing, 52(5): 1132-1192. 2023
Fully Online Matching
Zhiyi Huang, Ning Kang, Zhihao Gavin Tang, Xiaowei Wu*, Yuhao Zhang and Xue Zhu
JACM 2020: Journal of the ACM, 67(3): 17:1-17:25. 2020
Online Vertex Weighted Bipartite Matching: Beating 1-1/e with Random Arrivals
Zhiyi Huang, Zhihao Gavin Tang, Xiaowei Wu* and Yuhao Zhang
TALG 2019: ACM Transactions on Algorithms, 15(3), 38:1-38:15. 2019
Ranking on Arbitrary Graphs: Rematch via Continuous Linear Programming
T-H. Hubert Chan, Fei Chen, Xiaowei Wu*, and Zhichao Zhao
SICOMP 2018: SIAM Journal on Computing, 47(4), 1529–1546. 2018
Analyzing Node-Weighted Oblivious Matching Problem via Continuous LP with Jump Discontinuity
T-H. Hubert Chan, Fei Chen, and Xiaowei Wu*
TALG 2018: ACM Transactions on Algorithms, 14(2), 12:1–12:25. 2018
Selected Conference Publications
Check dblp for the full list of publications.
* Authors are listed in alphabetical order (why?).
- Improved Competitive Ratio for Edge-Weighted Online Stochastic Matching
Guoliang Qiu, Yilong Feng, Shengwei Zhou and Xiaowei Wu. In WINE 2023.
- Prophet Inequality on I.I.D. Distributions: Beating 1-1/e with a Single Query
Bo Li, Xiaowei Wu* and Yutong Wu. In WINE 2023.
- One Quarter Each (on Average) Ensures Proportionality
Xiaowei Wu*, Shengwei Zhou and Cong Zhang. In WINE 2023.
- Weighted EF1 Allocations for Indivisible Chores
Xiaowei Wu*, Shengwei Zhou and Cong Zhang. In EC 2023.
- Multiagent MST Cover: Pleasing All Optimally via A Simple Voting Rule
Bo Li, Xiaowei Wu*, Chenyang Xu and Ruilong Zhang. In AAAI 2023.
- Approximately EFX Allocations for Indivisible Chores
Shengwei Zhou and Xiaowei Wu. In IJCAI 2022.
- Mixed Strategies for Security Games with General Defending Requirements
Rufan Bai, Haoxing Lin, Xinyu Yang, Xiaowei Wu, Minming Li, Weijia Jia. In IJCAI 2022.
- Almost (Weighted) Proportional Allocations for Indivisible Chores
Bo Li, Yingkai Li and Xiaowei Wu*. In WWW 2022.
- Budget-feasible Maximum Nash Social Welfare is Almost Envy-free
Xiaowei Wu, Bo Li and Jiarui Gan. In IJCAI 2021.
- Defending Against Contagious Attacks on a Network with Resource Reallocation
Rufan Bai, Haoxing Lin, Xinyu Yang, Xiaowei Wu, Minming Li, Weijia Jia. In AAAI 2021.
- Dynamic Set Cover: Improved Amortized and Worst-Case Update Times
Sayan Bhattacharya, Monika Henzinger, Danupon Nanongkai and Xiaowei Wu*. In SODA 2021.
- Fully Online Matching II: Beating Ranking and Water-filling
Zhiyi Huang, Zhihao Gavin Tang, Xiaowei Wu* and Yuhao Zhang. In FOCS 2020.
- Towards a Better Understanding of Randomized Greedy Matching
Zhihao Gavin Tang, Xiaowei Wu* and Yuhao Zhang. In STOC 2020.
- Defending with Shared Resources on a Network
Minming Li, Long Tran-Thanh and Xiaowei Wu*. In AAAI 2020.
- Strategyproof and Approximately Maxmin Fair Share Allocation of Chores
Haris Aziz, Bo Li and Xiaowei Wu*. In IJCAI 2019.
- Maximin-Aware Allocations of Indivisible Goods
Hau Chan, Jing Chen, Bo Li and Xiaowei Wu*. In IJCAI 2019.
- Tight Competitive Ratios of Classic Matching Algorithms in the Fully Online Model
Zhiyi Huang, Binghui Peng, Zhihao Gavin Tang, Runzhou Tao, Xiaowei Wu* and Yuhao Zhang. In SODA 2019.
- Online Makespan Minimization: The Power of Restart
Zhiyi Huang, Ning Kang, Zhihao Gavin Tang, Xiaowei Wu* and Yuhao Zhang. In APPROX 2018.
- Online Vertex Weighted Bipartite Matching: Beating 1-1/e with Random Arrivals
Zhiyi Huang, Zhihao Gavin Tang, Xiaowei Wu* and Yuhao Zhang. In ICALP 2018.
- How to Match when All Vertices Arrive Online
Zhiyi Huang, Ning Kang, Zhihao Gavin Tang, Xiaowei Wu*, Yuhao Zhang and Xue Zhu. In STOC 2018.
- Online Submodular Maximization Problem with Vector Packing Constraint
T-H. Hubert Chan, Shaofeng H.-C. Jiang, Zhihao Gavin Tang and Xiaowei Wu*. In ESA 2017.
- Beating Ratio 0.5 for Weighted Oblivious Matching Problems
Melika Abolhassani, T-H. Hubert Chan, Fei Chen, Hossein Esfandiari, M. Hajiaghayi, Hamid Mahini and Xiaowei Wu*. In ESA 2016.
- Ranking on Arbitrary Graphs: Rematch via Continuous LP with Monotone and Boundary Condition Constraints
T-H. Hubert Chan, Fei Chen, Xiaowei Wu* and Zhichao Zhao. In SODA 2014.
Research Group
PhD Students:
- Yilong Feng (2023 – )
- Cong Zhang (2022 – )
- Shengwei Zhou (2021 – )
- Rufan Bai (2020 – 2023)
Master Students:
- Yang Gao (2023 – )
- Haolong Li (2023 – )
- Jiawei Qiu (2022 – )
- Yilong Feng (2022 – 2023)
- Tathim Lei (2021 – 2022)
- Xinyu Yang (2020 – 2022)
- Denghao Wu (2020 – 2021)
Research Assistants:
- Sijia Dai (2023.05 – 2023.08)
- Huahua Miao (2023.05 – 2023.08)
- Guoliang Qiu (2022.10 – 2023.02)
- Ruilong Zhang (2022.05 – 2022.09)
- Shengwei Zhou (2021.04 – 2021.07)
- Haoxing Lin (2020.08 – 2021.07)