Xiaowei Wu's Homepage

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

Email: xiaoweiwu at um.edu.mo

UM Homepage: https://www.fst.um.edu.mo/personal/xiaoweiwu/

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 in 2019. I received my PhD degree from the University of Hong Kong under the supervision of Dr. Hubert Chan. I received my BEng degree from University of Science and Technology of China.

Openings

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 representative publication.

Students with ACM programming contest experience will have priority.

News

  • Apr. 29, 2021. One paper on budget-feasible fair allocation is accepted by IJCAI 2021.

  • Apri. 19, 2021. Mr. Shengwei Zhou joined our group as a Research Assistant.

  • Apr. 13, 2021. One paper on retroactive data structure is accepted by WADS 2021.

  • Dec.17, 2020. One paper on optimization of bus scheduling is accepted by ICDE 2021 (short paper).

  • Dec.03, 2020. One paper on Stackelberg game on the network is accepted by AAAI 2021.

  • Sep. 30, 2020. One paper on dynamic data structure for set cover is accepted by SODA 2021.

  • July. 10, 2020. One paper on fully online matching is accepted by FOCS 2020.

  • May 20, 2020. One paper on fully online matching is published in JACM 2020.

  • Feb. 07, 2020. One paper on edge-weighted oblivious matching is accepted by STOC 2020.

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, fair allocation problems, game theory and truthful mechanism design.

Seleted Journal Publications (dblp)

(Unless stated otherwise, authors are listed in alphabetical order following the tradition of TCS.)

  • Fully Online Matching

Zhiyi Huang, Ning Kang, Zhihao Gavin Tang, Xiaowei Wu, Yuhao Zhang and Xue Zhu

Journal of the ACM (JACM), 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

ACM Transactions on Algorithms (TALG), 15(3), 38:1-38:15. 2019

  • Diffusion operator and spectral analysis for directed hypergraph Laplacian

T-H. Hubert Chan, Zhihao Gavin Tang, Xiaowei Wu, and Chenzi Zhang

Theoretical Computer Science (TCS), 784: 46-64. 2019

  • Ranking on Arbitrary Graphs: Rematch via Continuous Linear Programming

T-H. Hubert Chan, Fei Chen, Xiaowei Wu, and Zhichao Zhao

SIAM Journal on Computing (SICOMP), 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

ACM Transactions on Algorithms (TALG), 14(2), 12:1–12:25. 2018

  • On (1,\epsilon)-Restricted Max-Min Fair Allocation Problem

T-H. Hubert Chan, Zhihao Gavin Tang, and Xiaowei Wu

Algorithmica, 80(7), 2181–2200. 2018

  • On Minimal Steiner Maximum-Connected Subgraph Queries

Jiafeng Hu, Xiaowei Wu, Reynold Cheng, Siqiang Luo, and Yixiang Fang (by contribution)

IEEE Transactions on Knowledge and Data Engineering (TKDE), 29(11): 2455-2469. 2017


Selected Conference Publications (dblp)

(Unless stated otherwise, authors are listed in alphabetical order following the tradition of TCS.)

  • Budget-feasible Maximum Nash Social Welfare is Almost Envy-free

Xiaowei Wu, Bo Li and Jiarui Gan (by contribution). In IJCAI 2021. (pdf)

  • Upper and Lower Bounds for Fully Retroactive Graph Problems

Monika Henzinger and Xiaowei Wu. In WADS 2021. (pdf)

  • Defending Against Contagious Attacks on a Network with Resource Reallocation

Rufan Bai, Haoxing Lin, Xinyu Yang, Xiaowei Wu, Minming Li and Weijia Jia (by contribution). In AAAI 2021. (pdf)

  • Dynamic Set Cover: Improved Amortized and Worst-Case Update Times

Sayan Bhattacharya, Monika Henzinger, Danupon Nanongkai and Xiaowei Wu. In SODA 2021. (pdf)

  • Fully Online Matching II: Beating Ranking and Water-filling

Zhiyi Huang, Zhihao Gavin Tang, Xiaowei Wu and Yuhao Zhang. In FOCS 2020. (pdf)

  • Towards a Better Understanding of Randomized Greedy Matching

Zhihao Gavin Tang, Xiaowei Wu and Yuhao Zhang. In STOC 2020. (pdf)

  • Defending with Shared Resources on a Network

Minming Li, Long Tran-Thanh and Xiaowei Wu. In AAAI 2020. (pdf)

  • Strategyproof and Approximately Maxmin Fair Share Allocation of Chores

Haris Aziz, Bo Li and Xiaowei Wu. In IJCAI 2019. (pdf)

  • Maximin-Aware Allocations of Indivisible Goods

Hau Chan, Jing Chen, Bo Li and Xiaowei Wu. In IJCAI 2019. (pdf)

  • Well-behaved Online Load Balancing Against Strategic Jobs

Bo Li, Minming Li and Xiaowei Wu. In AAMAS 2019. (pdf)

  • 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. (pdf)

  • Online Makespan Minimization: The Power of Restart

Zhiyi Huang, Ning Kang, Zhihao Gavin Tang, Xiaowei Wu and Yuhao Zhang. In APPROX 2018. (pdf)

  • 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. (pdf)

  • 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. (pdf)

  • 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. (pdf)

  • Maintaining Densest Subsets Efficiently in Evolving Hypergraphs

Shuguang Hu, Xiaowei Wu and T-H. Hubert Chan (by contribution). In CIKM 2017. (pdf)

  • Querying Minimal Steiner Maximum-Connected Subgraphs in Large Graphs

Jiafeng Hu, Xiaowei Wu, Reynold Cheng, Siqiang Luo and Yixiang Fang (by contribution). In CIKM 2016. (pdf)

  • On (1,\epsilon)-Restricted Max-Min Fair Allocation Problem

T-H. Hubert Chan, Zhihao Gavin Tang and Xiaowei Wu. In ISAAC 2016. (pdf)

  • Beating Ratio 0.5 for Weighted Oblivious Matching Problems

Melika Abolhassani, T-H. Hubert Chan, Fei Chen, Hossein Esfandiari, MohammadTaghi Hajiaghayi, Hamid Mahini and Xiaowei Wu. In ESA 2016. (pdf)

  • 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. (pdf)


Research Group

PhD Students:

  • Rufan Bai (2020 - )

Master Students:

  • Xinyu Yang (2020 - )

  • Denghao Wu (2020 - )

Research Assistants:

  • Haoxing Lin (2020 - )

  • Shengwei Zhou (2021 - )


Last Modified: Apr. 30, 2021