Publications
2024
-
Fully Scalable Massively Parallel Algorithms for Embedded Planar Graphs
(SODA 2024)
Y.-J. Chang and Da Wei Zheng, “Fully Scalable Massively Parallel Algorithms for Embedded Planar Graphs,” in Proceedings of the 2024 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), 2024, pp. 4410–4450. -
An Optimal Algorithm for Higher-Order Voronoi Diagrams in the Plane:
The Usefulness of Nondeterminism
(SODA 2024)
T. M. Chan, P. Cheng, and Da Wei Zheng, “An Optimal Algorithm for Higher-Order Voronoi Diagrams in the Plane: The Usefulness of Nondeterminism,” in Proceedings of the 2024 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), 2024, pp. 4451–4463.
2023
-
Halving by a Thousand Cuts or Punctures
(SODA 2023)
S. Har-Peled and Da Wei Zheng, “Halving by a Thousand Cuts or Punctures,” in Proceedings of the 2023 ACM-SIAM Symposium on Discrete Algorithms, SODA 2023, Florence, Italy, January 22-25, 2023, 2023, pp. 1385–1397. -
Simplex Range Searching Revisited: How to Shave Logs in Multi-Level
Data Structures
(SODA 2023)
T. M. Chan and Da Wei Zheng, “Simplex Range Searching Revisited: How to Shave Logs in Multi-Level Data Structures,” in Proceedings of the 2023 ACM-SIAM Symposium on Discrete Algorithms, SODA 2023, Florence, Italy, January 22-25, 2023, 2023, pp. 1493–1511. -
Multiplicative Auction Algorithm for Approximate Maximum Weight Bipartite
Matching
(IPCO 2023)
Da Wei Zheng and M. Henzinger, “Multiplicative Auction Algorithm for Approximate Maximum Weight Bipartite Matching,” in Integer Programming and Combinatorial Optimization - 24th International Conference, IPCO 2023, Madison, WI, USA, June 21-23, 2023, Proceedings, 2023, vol. 13904, pp. 453–465. -
Conflict Optimization for Binary CSP Applied to Minimum Partition
into Plane Subgraphs and Graph Coloring
(JEA 2023)
Crombez Loı̈c, G. D. da Fonseca, F. Fontan, Y. Gerard, A. Gonzalez-Lorenzo, P. Lafourcade, L. Libralesso, B. Momège, J. Spalding-Jamieson, B. Zhang, and Da Wei Zheng, “Conflict Optimization for Binary CSP Applied to Minimum Partition into Plane Subgraphs and Graph Coloring,” CoRR, vol. abs/2303.09632, 2023. -
Faster Submodular Maximization for Several Classes of Matroids
(ICALP 2023)
M. Henzinger, P. Liu, J. Vondrák, and Da Wei Zheng, “Faster Submodular Maximization for Several Classes of Matroids,” in 50th International Colloquium on Automata, Languages, and Programming, ICALP 2023, July 10-14, 2023, Paderborn, Germany, 2023, vol. 261, pp. 74:1–74:18.
2022
-
Hopcroft’s Problem, Log-Star Shaving, 2D Fractional Cascading, and
Decision Trees
(SODA 2022)
T. M. Chan and Da Wei Zheng, “Hopcroft’s Problem, Log-Star Shaving, 2D Fractional Cascading, and Decision Trees,” in Proceedings of the 2022 ACM-SIAM Symposium on Discrete Algorithms, SODA 2022, Virtual Conference / Alexandria, VA, USA, January 9 - 12, 2022, 2022, pp. 190–210. -
Conflict-Based Local Search for Minimum Partition into Plane Subgraphs
(SoCG 2022)
J. Spalding-Jamieson, B. Zhang, and Da Wei Zheng, “Conflict-Based Local Search for Minimum Partition into Plane Subgraphs,” in 38th International Symposium on Computational Geometry (SoCG 2022), Dagstuhl, Germany, 2022, vol. 224, pp. 72:1–72:6.
2021
-
Coordinated Motion Planning Through Randomized k-Opt (CG Challenge)
(SoCG 2021)
P. Liu, J. Spalding-Jamieson, B. Zhang, and Da Wei Zheng, “Coordinated Motion Planning Through Randomized k-Opt (CG Challenge),” in 37th International Symposium on Computational Geometry, SoCG 2021, June 7-11, 2021, Buffalo, NY, USA (Virtual Conference), 2021, vol. 189, pp. 64:1–64:8.
2020
-
Scheduling queries to moving entities to certify many are distant from a region
Da Wei Zheng, “Scheduling queries to moving entities to certify many are distant from a region,” Master's thesis, University of British Columbia, 2020. -
Computing Low-Cost Convex Partitions for Planar Point Sets with Randomized
Local Search and Constraint Programming (CG Challenge)
(SoCG 2020)
Da Wei Zheng, J. Spalding-Jamieson, and B. Zhang, “Computing Low-Cost Convex Partitions for Planar Point Sets with Randomized Local Search and Constraint Programming (CG Challenge),” in 36th International Symposium on Computational Geometry, SoCG 2020, June 23-26, 2020, Zürich, Switzerland, 2020, vol. 164, pp. 83:1–83:7.