Publications

2025

Subquadratic algorithms in minor-free digraphs: (weighted) distance oracles, decremental reachability, and more
(To appear at SODA 2025) Adam Karczmarz and Da Wei Zheng
```
@inproceedings{KarczmarzZ24,
  author = {Karczmarz, Adam and Zheng, Da Wei},
  title = {Subquadratic algorithms in minor-free digraphs: (weighted)
                    distance oracles, decremental reachability, and more},
  journal = {CoRR},
  volume = {abs/2410.12003},
  year = {2025},
  url = {https://doi.org/10.48550/arXiv.2410.12003},
  doi = {10.48550/ARXIV.2410.12003},
  eprinttype = {arXiv},
  eprint = {2410.12003},
  conference = {To appear at SODA 2025},
  arxiv = {https://doi.org/10.48550/arXiv.2410.12003}
}
```

2024

A Simple Approximation Scheme for Bipartite Geometric Many-to-Many Matching
(In submission) Da Wei Zheng
```
@article{Zheng24,
  author = {Zheng, Da Wei},
  title = {A Simple Approximation Scheme for Bipartite Geometric Many-to-Many Matching},
  year = {2024},
  conference = {In submission},
  note = {In submission}
}
```
MOPBucket
(In submission) Jack Spalding-Jamieson, Eliot W. Robson, and Da Wei Zheng
```
@article{SpaldingJamiesonRZ24,
  author = {Spalding-Jamieson, Jack and Robson, Eliot W. and Zheng, Da Wei},
  title = {MOPBucket},
  year = {2024},
  conference = {In submission},
  note = {In submission}
}
```

Shortest Path Separators in Unit Disk Graphs
(ESA 2024) Elfarouk Harb, Zhengcheng Huang, and Da Wei Zheng

@inproceedings{HarbHZ24,
  author = {Harb, Elfarouk and Huang, Zhengcheng and Zheng, Da Wei},
  title = {{Shortest Path Separators in Unit Disk Graphs}},
  booktitle = {32nd Annual European Symposium on Algorithms (ESA 2024)},
  pages = {66:1--66:14},
  series = {Leibniz International Proceedings in Informatics (LIPIcs)},
  isbn = {978-3-95977-338-6},
  issn = {1868-8969},
  year = {2024},
  volume = {308},
  editor = {Chan, Timothy and Fischer, Johannes and Iacono, John and Herman, Grzegorz},
  publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address = {Dagstuhl, Germany},
  url = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ESA.2024.66},
  urn = {urn:nbn:de:0030-drops-211375},
  doi = {10.4230/LIPIcs.ESA.2024.66},
  conference = {ESA 2024},
  arxiv = {https://doi.org/10.48550/arXiv.2407.15980}
}

From Directed Steiner Tree to Directed Polymatroid Steiner Tree in Planar Graphs
(ESA 2024) Chandra Chekuri, Rhea Jain, Shubhang Kulkarni, Da Wei Zheng, and Weihao Zhu

@inproceedings{ChekuriJKZZ24,
  author = {Chekuri, Chandra and Jain, Rhea and Kulkarni, Shubhang and Zheng, Da Wei and Zhu, Weihao},
  title = {{From Directed Steiner Tree to Directed Polymatroid Steiner Tree in Planar Graphs}},
  booktitle = {32nd Annual European Symposium on Algorithms (ESA 2024)},
  pages = {42:1--42:19},
  series = {Leibniz International Proceedings in Informatics (LIPIcs)},
  isbn = {978-3-95977-338-6},
  issn = {1868-8969},
  year = {2024},
  volume = {308},
  editor = {Chan, Timothy and Fischer, Johannes and Iacono, John and Herman, Grzegorz},
  publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address = {Dagstuhl, Germany},
  url = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ESA.2024.42},
  urn = {urn:nbn:de:0030-drops-211134},
  doi = {10.4230/LIPIcs.ESA.2024.42},
  conference = {ESA 2024},
  arxiv = {https://doi.org/10.48550/arXiv.2407.01904}
}

Carving Polytopes with Saws in 3D
(CCCG 2024) Eliot W. Robson, Jack Spalding-Jamieson, and Da Wei Zheng

@inproceedings{RobsonSZ24,
  author = {Robson, Eliot W. and Spalding-Jamieson, Jack and Zheng, Da Wei},
  title = {Carving Polytopes with Saws in {3D}},
  booktitle = {Proceedings of the 36th Canadian Conference on Computational Geometry,
                    {CCCG} 2024, Brock University, St. Catherines, Ontario, Canada, July
                    17 - July 19, 2024},
  pages = {145--151},
  year = {2024},
  conference = {CCCG 2024},
  url = {https://cosc.brocku.ca/~rnishat/CCCG_2024_proceedings.pdf},
  arxiv = {https://doi.org/10.48550/arXiv.2407.15981}
}

Semialgebraic Range Stabbing, Ray Shooting, and Intersection Counting in the Plane
(SoCG 2024) Timothy M. Chan, Pingan Cheng, and Da Wei Zheng

@inproceedings{ChanCZb24,
  author = {Chan, Timothy M. and Cheng, Pingan and Zheng, Da Wei},
  editor = {Mulzer, Wolfgang and Phillips, Jeff M.},
  title = {Semialgebraic Range Stabbing, Ray Shooting, and Intersection Counting
                    in the Plane},
  booktitle = {40th International Symposium on Computational Geometry, SoCG 2024,
                    June 11-14, 2024, Athens, Greece},
  series = {LIPIcs},
  volume = {293},
  pages = {33:1--33:15},
  publisher = {Schloss Dagstuhl - Leibniz-Zentrum f{\"{u}}r Informatik},
  year = {2024},
  url = {https://doi.org/10.4230/LIPIcs.SoCG.2024.33},
  doi = {10.4230/LIPICS.SOCG.2024.33},
  biburl = {https://dblp.org/rec/conf/compgeom/ChanCZ24.bib},
  bibsource = {dblp computer science bibliography, https://dblp.org},
  conference = {SoCG 2024},
  arxiv = {https://doi.org/10.48550/arXiv.2403.12303}
}

Fully Scalable Massively Parallel Algorithms for Embedded Planar Graphs
(SODA 2024) Yi-Jun Chang and Da Wei Zheng

@inproceedings{ChangZ24,
  author = {Chang, Yi{-}Jun and Zheng, Da Wei},
  editor = {Woodruff, David P.},
  title = {Fully Scalable Massively Parallel Algorithms for Embedded Planar Graphs},
  booktitle = {Proceedings of the 2024 {ACM-SIAM} Symposium on Discrete Algorithms,
                    {SODA} 2024, Alexandria, VA, USA, January 7-10, 2024},
  pages = {4410--4450},
  publisher = {{SIAM}},
  year = {2024},
  url = {https://doi.org/10.1137/1.9781611977912.155},
  doi = {10.1137/1.9781611977912.155},
  biburl = {https://dblp.org/rec/conf/soda/ChangZ24.bib},
  bibsource = {dblp computer science bibliography, https://dblp.org},
  conference = {SODA 2024},
  arxiv = {https://arxiv.org/abs/2304.07441},
  slides = {assets/soda24_mpc.pdf}
}

An Optimal Algorithm for Higher-Order Voronoi Diagrams in the Plane: The Usefulness of Nondeterminism
(SODA 2024) Timothy M. Chan, Pingan Cheng, and Da Wei Zheng

@inproceedings{ChanCZ24,
  author = {Chan, Timothy M. and Cheng, Pingan and Zheng, Da Wei},
  editor = {Woodruff, David P.},
  title = {An Optimal Algorithm for Higher-Order Voronoi Diagrams in the Plane:
                    The Usefulness of Nondeterminism},
  booktitle = {Proceedings of the 2024 {ACM-SIAM} Symposium on Discrete Algorithms,
                    {SODA} 2024, Alexandria, VA, USA, January 7-10, 2024},
  pages = {4451--4463},
  publisher = {{SIAM}},
  year = {2024},
  url = {https://doi.org/10.1137/1.9781611977912.156},
  doi = {10.1137/1.9781611977912.156},
  biburl = {https://dblp.org/rec/conf/soda/ChanCZ24.bib},
  bibsource = {dblp computer science bibliography, https://dblp.org},
  conference = {SODA 2024},
  arxiv = {https://arxiv.org/abs/2310.15363},
  slides = {assets/soda24_voronoi_slides.pdf}
}

2023

Multiplicative Auction Algorithm for Approximate Maximum Weight Bipartite Matching
(IPCO 2023) Da Wei Zheng and Monika Henzinger

@inproceedings{ZhengH23,
  author = {Zheng, Da Wei and Henzinger, Monika},
  editor = {Pia, Alberto Del and Kaibel, Volker},
  title = {Multiplicative Auction Algorithm for Approximate Maximum Weight Bipartite
                    Matching},
  booktitle = {Integer Programming and Combinatorial Optimization - 24th International
                    Conference, {IPCO} 2023, Madison, WI, USA, June 21-23, 2023, Proceedings},
  series = {Lecture Notes in Computer Science},
  volume = {13904},
  pages = {453--465},
  publisher = {Springer},
  year = {2023},
  url = {https://doi.org/10.1007/978-3-031-32726-1\_32},
  doi = {10.1007/978-3-031-32726-1\_32},
  biburl = {https://dblp.org/rec/conf/ipco/ZhengH23.bib},
  bibsource = {dblp computer science bibliography, https://dblp.org},
  conference = {IPCO 2023},
  arxiv = {https://arxiv.org/abs/2301.09217},
  slides = {assets/matching_auction_slides.pdf}
}

Conflict Optimization for Binary CSP Applied to Minimum Partition into Plane Subgraphs and Graph Coloring
(JEA 2023) Crombez Loı̈c, Guilherme Dias da Fonseca, Florian Fontan, Yan Gerard, Aldo Gonzalez-Lorenzo, Pascal Lafourcade, Luc Libralesso, Benjamin Momège, Jack Spalding-Jamieson, Brandon Zhang, and Da Wei Zheng

@article{CrombezFFGGLLMSZZ23,
  author = {Crombez, Lo{\"{\i}}c and da Fonseca, Guilherme Dias and Fontan, Florian and Gerard, Yan and Gonzalez{-}Lorenzo, Aldo and Lafourcade, Pascal and Libralesso, Luc and Mom{\`{e}}ge, Benjamin and Spalding{-}Jamieson, Jack and Zhang, Brandon and Zheng, Da Wei},
  title = {Conflict Optimization for Binary {CSP} Applied to Minimum Partition
                 into Plane Subgraphs and Graph Coloring},
  journal = {CoRR},
  volume = {abs/2303.09632},
  year = {2023},
  url = {https://doi.org/10.48550/arXiv.2303.09632},
  doi = {10.48550/arXiv.2303.09632},
  eprinttype = {arXiv},
  eprint = {2303.09632},
  biburl = {https://dblp.org/rec/journals/corr/abs-2303-09632.bib},
  bibsource = {dblp computer science bibliography, https://dblp.org},
  conference = {JEA 2023},
  arxiv = {https://arxiv.org/abs/2303.09632}
}

Faster Submodular Maximization for Several Classes of Matroids
(ICALP 2023) Monika Henzinger, Paul Liu, Jan Vondrák, and Da Wei Zheng

@inproceedings{HenzingerLVZ23,
  author = {Henzinger, Monika and Liu, Paul and Vondr{\'{a}}k, Jan and Zheng, Da Wei},
  editor = {Etessami, Kousha and Feige, Uriel and Puppis, Gabriele},
  title = {Faster Submodular Maximization for Several Classes of Matroids},
  booktitle = {50th International Colloquium on Automata, Languages, and Programming,
                    {ICALP} 2023, July 10-14, 2023, Paderborn, Germany},
  series = {LIPIcs},
  volume = {261},
  pages = {74:1--74:18},
  publisher = {Schloss Dagstuhl - Leibniz-Zentrum f{\"{u}}r Informatik},
  year = {2023},
  url = {https://doi.org/10.4230/LIPIcs.ICALP.2023.74},
  doi = {10.4230/LIPIcs.ICALP.2023.74},
  biburl = {https://dblp.org/rec/conf/icalp/HenzingerLVZ23.bib},
  bibsource = {dblp computer science bibliography, https://dblp.org},
  conference = {ICALP 2023},
  arxiv = {https://arxiv.org/abs/2305.00122},
  slides = {assets/icalp2023_submod.pdf}
}

Halving by a Thousand Cuts or Punctures
(SODA 2023) Sariel Har-Peled and Da Wei Zheng

@inproceedings{HarPeledZ23,
  author = {Har{-}Peled, Sariel and Zheng, Da Wei},
  editor = {Bansal, Nikhil and Nagarajan, Viswanath},
  title = {Halving by a Thousand Cuts or Punctures},
  booktitle = {Proceedings of the 2023 {ACM-SIAM} Symposium on Discrete Algorithms,
                 {SODA} 2023, Florence, Italy, January 22-25, 2023},
  pages = {1385--1397},
  publisher = {{SIAM}},
  year = {2023},
  url = {https://doi.org/10.1137/1.9781611977554.ch49},
  doi = {10.1137/1.9781611977554.ch49},
  biburl = {https://dblp.org/rec/conf/soda/Har-PeledZ23.bib},
  bibsource = {dblp computer science bibliography, https://dblp.org},
  conference = {SODA 2023},
  arxiv = {https://arxiv.org/abs/2208.11275},
  slides = {assets/SODA23_Cuts_Punctures.pdf}
}

Simplex Range Searching Revisited: How to Shave Logs in Multi-Level Data Structures
(SODA 2023) Timothy M. Chan and Da Wei Zheng

@inproceedings{ChanZ23,
  author = {Chan, Timothy M. and Zheng, Da Wei},
  editor = {Bansal, Nikhil and Nagarajan, Viswanath},
  title = {Simplex Range Searching Revisited: How to Shave Logs in Multi-Level
                 Data Structures},
  booktitle = {Proceedings of the 2023 {ACM-SIAM} Symposium on Discrete Algorithms,
                 {SODA} 2023, Florence, Italy, January 22-25, 2023},
  pages = {1493--1511},
  publisher = {{SIAM}},
  year = {2023},
  url = {https://doi.org/10.1137/1.9781611977554.ch54},
  doi = {10.1137/1.9781611977554.ch54},
  biburl = {https://dblp.org/rec/conf/soda/ChanZ23.bib},
  bibsource = {dblp computer science bibliography, https://dblp.org},
  conference = {SODA 2023},
  arxiv = {https://arxiv.org/abs/2210.10172},
  slides = {assets/SODA23_Multilevel_slides.pdf}
}

2022

Conflict-Based Local Search for Minimum Partition into Plane Subgraphs
(SoCG 2022) Jack Spalding-Jamieson, Brandon Zhang, and Da Wei Zheng

@inproceedings{SpaldingJamiesonZZ22,
  author = {Spalding-Jamieson, Jack and Zhang, Brandon and Zheng, Da Wei},
  title = {{Conflict-Based Local Search for Minimum Partition into Plane Subgraphs}},
  booktitle = {38th International Symposium on Computational Geometry (SoCG 2022)},
  pages = {72:1--72:6},
  series = {Leibniz International Proceedings in Informatics (LIPIcs)},
  isbn = {978-3-95977-227-3},
  issn = {1868-8969},
  year = {2022},
  volume = {224},
  editor = {Goaoc, Xavier and Kerber, Michael},
  publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address = {Dagstuhl, Germany},
  url = {https://drops.dagstuhl.de/opus/volltexte/2022/16080},
  urn = {urn:nbn:de:0030-drops-160807},
  doi = {10.4230/LIPIcs.SoCG.2022.72},
  conference = {SoCG 2022},
  annote = {Keywords: local search, planar graph, graph colouring, geometric graph, conflict optimizer}
}

Hopcroft’s Problem, Log-Star Shaving, 2D Fractional Cascading, and Decision Trees
(SODA 2022) Timothy M. Chan and Da Wei Zheng

@inproceedings{ChanZ22,
  author = {Chan, Timothy M. and Zheng, Da Wei},
  editor = {Naor, Joseph (Seffi) and Buchbinder, Niv},
  title = {Hopcroft's Problem, Log-Star Shaving, 2D Fractional Cascading, and
                 Decision Trees},
  booktitle = {Proceedings of the 2022 {ACM-SIAM} Symposium on Discrete Algorithms,
                 {SODA} 2022, Virtual Conference / Alexandria, VA, USA, January 9 -
                 12, 2022},
  pages = {190--210},
  publisher = {{SIAM}},
  year = {2022},
  url = {https://doi.org/10.1137/1.9781611977073.10},
  doi = {10.1137/1.9781611977073.10},
  biburl = {https://dblp.org/rec/conf/soda/ChanZ22.bib},
  bibsource = {dblp computer science bibliography, https://dblp.org},
  conference = {SODA 2022},
  arxiv = {https://arxiv.org/abs/2111.03744},
  slides = {assets/SODA22_Hopcroft_Slides.pdf}
}

2021

Coordinated Motion Planning Through Randomized k-Opt (CG Challenge)
(SoCG 2021) Paul Liu, Jack Spalding-Jamieson, Brandon Zhang, and Da Wei Zheng

@inproceedings{LiuSZZ21,
  author = {Liu, Paul and Spalding{-}Jamieson, Jack and Zhang, Brandon and Zheng, Da Wei},
  editor = {Buchin, Kevin and {\'{E}}ric Colin de Verdi{\`{e}}re},
  title = {Coordinated Motion Planning Through Randomized k-Opt {(CG} Challenge)},
  booktitle = {37th International Symposium on Computational Geometry, SoCG 2021,
                 June 7-11, 2021, Buffalo, NY, {USA} (Virtual Conference)},
  series = {LIPIcs},
  volume = {189},
  pages = {64:1--64:8},
  publisher = {Schloss Dagstuhl - Leibniz-Zentrum f{\"{u}}r Informatik},
  year = {2021},
  url = {https://doi.org/10.4230/LIPIcs.SoCG.2021.64},
  doi = {10.4230/LIPIcs.SoCG.2021.64},
  biburl = {https://dblp.org/rec/conf/compgeom/LiuSZZ21.bib},
  bibsource = {dblp computer science bibliography, https://dblp.org},
  conference = {SoCG 2021},
  arxiv = {https://arxiv.org/abs/2103.15062}
}

2020

Scheduling queries to moving entities to certify many are distant from a region
(Master’s Thesis) Da Wei Zheng
```
@mastersthesis{ZhengMasters,
  series = {Electronic Theses and Dissertations (ETDs) 2008+},
  title = {Scheduling queries to moving entities to certify many are distant from a region},
  url = {https://open.library.ubc.ca/collections/ubctheses/24/items/1.0392883},
  doi = {http://dx.doi.org/10.14288/1.0392883},
  school = {University of British Columbia},
  author = {Zheng, Da Wei},
  year = {2020},
  collection = {Electronic Theses and Dissertations (ETDs) 2008+},
  conference = {Master's Thesis}
}
```

Computing Low-Cost Convex Partitions for Planar Point Sets with Randomized Local Search and Constraint Programming (CG Challenge)
(SoCG 2020) Da Wei Zheng, Jack Spalding-Jamieson, and Brandon Zhang

@inproceedings{ZhengSZ20,
  author = {Zheng, Da Wei and Spalding{-}Jamieson, Jack and Zhang, Brandon},
  editor = {Cabello, Sergio and Chen, Danny Z.},
  title = {Computing Low-Cost Convex Partitions for Planar Point Sets with Randomized
                 Local Search and Constraint Programming {(CG} Challenge)},
  booktitle = {36th International Symposium on Computational Geometry, SoCG 2020,
                 June 23-26, 2020, Z{\"{u}}rich, Switzerland},
  series = {LIPIcs},
  volume = {164},
  pages = {83:1--83:7},
  publisher = {Schloss Dagstuhl - Leibniz-Zentrum f{\"{u}}r Informatik},
  year = {2020},
  url = {https://doi.org/10.4230/LIPIcs.SoCG.2020.83},
  doi = {10.4230/LIPIcs.SoCG.2020.83},
  biburl = {https://dblp.org/rec/conf/compgeom/ZhengSZ20.bib},
  conference = {SoCG 2020},
  bibsource = {dblp computer science bibliography, https://dblp.org}
}