Publications

2023

• S. Har-Peled and D. W. 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. doi: 10.1137/1.9781611977554.ch49.
  Bibtex

  @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},
    timestamp = {Fri, 17 Feb 2023 09:28:57 +0100},
    biburl = {https://dblp.org/rec/conf/soda/Har-PeledZ23.bib},
    bibsource = {dblp computer science bibliography, https://dblp.org},
    arxiv = {https://arxiv.org/abs/2208.11275}
  }
  

• T. M. Chan and D. W. 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. doi: 10.1137/1.9781611977554.ch54.
  Bibtex

  @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},
    timestamp = {Fri, 17 Feb 2023 09:28:57 +0100},
    biburl = {https://dblp.org/rec/conf/soda/ChanZ23.bib},
    bibsource = {dblp computer science bibliography, https://dblp.org},
    arxiv = {https://arxiv.org/abs/2210.10172}
  }
  

• D. W. Zheng and M. Henzinger, “Multiplicative Auction Algorithm for Approximate Maximum Weight Bipartite Matching,” CoRR, vol. abs/2301.09217, 2023, doi: 10.48550/arXiv.2301.09217.
  Bibtex

  @article{ZhengH23,
    author = {Zheng, Da Wei and Henzinger, Monika},
    title = {Multiplicative Auction Algorithm for Approximate Maximum Weight Bipartite
                   Matching},
    journal = {CoRR},
    volume = {abs/2301.09217},
    year = {2023},
    url = {https://doi.org/10.48550/arXiv.2301.09217},
    doi = {10.48550/arXiv.2301.09217},
    eprinttype = {arXiv},
    eprint = {2301.09217},
    timestamp = {Thu, 26 Jan 2023 15:26:31 +0100},
    biburl = {https://dblp.org/rec/journals/corr/abs-2301-09217.bib},
    bibsource = {dblp computer science bibliography, https://dblp.org},
    note = {To appear in the Conference on Integer Programming and Combinatorial Optimization (IPCO 2023).},
    arxiv = {https://arxiv.org/abs/2301.09217}
  }
  

2022

• T. M. Chan and D. W. 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. doi: 10.1137/1.9781611977073.10.
  Bibtex

  @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},
    timestamp = {Tue, 12 Apr 2022 11:24:57 +0200},
    biburl = {https://dblp.org/rec/conf/soda/ChanZ22.bib},
    bibsource = {dblp computer science bibliography, https://dblp.org},
    arxiv = {https://arxiv.org/abs/2111.03744}
  }
  

• J. Spalding-Jamieson, B. Zhang, and D. W. 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. doi: 10.4230/LIPIcs.SoCG.2022.72.
  Bibtex

  @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},
    annote = {Keywords: local search, planar graph, graph colouring, geometric graph, conflict optimizer}
  }
  

 

2021

• P. Liu, J. Spalding-Jamieson, B. Zhang, and D. W. 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. doi: 10.4230/LIPIcs.SoCG.2021.64.
  Bibtex

  @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},
    timestamp = {Fri, 04 Jun 2021 19:47:03 +0200},
    biburl = {https://dblp.org/rec/conf/compgeom/LiuSZZ21.bib},
    bibsource = {dblp computer science bibliography, https://dblp.org},
    arxiv = {https://arxiv.org/abs/2103.15062}
  }
  

 

2020

• D. W. Zheng, “Scheduling queries to moving entities to certify many are distant from a region,” Master's thesis, University of British Columbia, 2020. doi: http://dx.doi.org/10.14288/1.0392883.
  Bibtex

  @mastersthesis{Zheng,
    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+}
  }
  

• D. W. 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. doi: 10.4230/LIPIcs.SoCG.2020.83.
  Bibtex

  @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},
    timestamp = {Wed, 16 Jun 2021 12:02:54 +0200},
    biburl = {https://dblp.org/rec/conf/compgeom/ZhengSZ20.bib},
    bibsource = {dblp computer science bibliography, https://dblp.org}
  }
  

 

2019

• J. M. Scurll et al., “StormGraph: An automated graph-based algorithm for quantitative clustering analysis of single-molecule localization microscopy data,” bioRxiv, 2019, doi: 10.1101/515627.
  Bibtex

  @article{Scurll,
    author = {Scurll, Joshua M. and Abraham, Libin and Zheng, Da Wei and Tafteh, Reza and Chou, Keng C. and Gold, Michael R. and Coombs, Daniel},
    title = {StormGraph: An automated graph-based algorithm for quantitative clustering analysis of single-molecule localization microscopy data},
    elocation-id = {515627},
    year = {2019},
    doi = {10.1101/515627},
    publisher = {Cold Spring Harbor Laboratory},
    url = {https://www.biorxiv.org/content/early/2019/01/09/515627},
    eprint = {https://www.biorxiv.org/content/early/2019/01/09/515627.full.pdf},
    journal = {bioRxiv},
    notes = {Available at \url{https://www.biorxiv.org/content/10.1101/515627v3}}
  }