Publications and Manuscripts
"

"
indicates a recently added or updated entry.
-
Minimum cut and minimum k-cut in
hypergraphs via branching contractions.
With Debmalya Panigrahi and Fred Zhang.
Proceedings of the 30th Annual ACM-SIAM Symposium
on Discrete Algorithms (SODA),
881–896, 2019.
-
An efficient algorithm for computing high
quality paths amid polygonal obstacles.
With Pankaj K. Agarwal and Oren Salzman.
ACM Transactions on Algorithms (TALG),
14(4), Article No. 46, 2018.
Preliminary version appeared in
Proceedings of the 27th Annual ACM-SIAM Symposium
on Discrete Algorithms (SODA),
1179–1192, 2016.
SODA 2016 presentation slides available in
Keynote
and
pdf.
Duke University Algorithms Seminar presentation slides available in
Keynote
and
pdf.
-
Trajectory planning for an articulated probe.
With Ovidiu Daescu and Ka Yaw Teo.
Proceedings of the 30th Canadian Conference on
Computational Geometry (CCCG),
296–303, 2018.
-
Holiest minimum-cost paths and flows in surface
graphs.
With Jeff Erickson and Luvsandondov Lkhamsuren.
Proceedings of the 50th Annual ACM Symposium on Theory of
Computing (STOC),
1319–1332, 2018.
-
Subtrajectory clustering: models and algorithms.
With Pankaj K. Agarwal, Kamesh Munagala, Abhinandan Nath, Jiangwei Pan, and Erin
Taylor.
Proceedings of the 37th ACM Symposium on Principles of Database
Systems (PODS),
75–87, 2018.
-
Computing the Gromov-Hausdorff distance for
metric trees.
With Pankaj K. Agarwal, Abhinandan Nath, Anastasios Sidiropoulos,
and Yusu Wang.
ACM Transactions on Algorithms (TALG),
14(2), Article No. 24, 2018.
Preliminary version appeared in
Proceedings of the 26th International Symposium
on Algorithms and Computation (ISAAC),
529–540, 2015.
-
Energy efficient scheduling of parallelizable
jobs.
With Sungjin Im and Benjamin Moseley.
Theoretical Computer Science (TCS),
726:30–40, 2018.
Preliminary version appeared in
Proceedings of the 24th Annual ACM-SIAM Symposium on Discrete
Algorithms (SODA),
948–957, 2013.
-
Geometric optimization revisited.
With Pankaj K. Agarwal and Esther Ezra.
Survey to appear in
Lecture Notes in Computer Science Volume 10000,
Bernhard Steffen and Gerhard Woeginger, editors,
2018.
-
Maintaining Reeb graphs of triangulated 2-manifolds.
With Pankaj K. Agarwal and Abhinandan Nath.
Proceedings of the 37th Conference on Foundations of Software
Technology and Theoretical Computer Science (FSTTCS 2017),
8:1–8:14, 2018.
-
Faster algorithms for the geometric
transportation problem.
With Pankaj K. Agarwal, Debmalya Panigrahi, Kasturi R. Varadarajan,
and Allen Xiao.
Proceedings of the 33rd International Symposium
on Computational Geometry (SoCG),
7:1–7:16, 2017.
Schloss Dagstuhl 17171 presentation slides available in
Keynote
and
pdf.
-
Minimum cycle and homology bases of surface
embedded graphs.
With Glencora Borradaile, Erin Wolf Chambers, and Amir Nayyeri.
Journal of Computational Geometry (JoCG),
8(2):58–79, 2017,
special issue of invited papers from the 32nd International Symposium on
Computational Geometry.
Preliminary version appeared in
Proceedings of the 32nd International Symposium
on Computational Geometry (SoCG),
23:1–23:15, 2016.
SoCG 2016 presentation slides available in
Keynote
and
pdf.
-
A simple efficient approximation algorithm for
dynamic time warping.
Rex Ying, Jiangwei Pan,
Kyle Fox,
and Pankaj K. Agarwal.
Proceedings of the 24th ACM SIGSPATIAL
International Conference on Advances in Geographic Information
Systems (ACM SIGSPATIAL),
Article No. 21, 2016.
-
Massively parallel algorithms for computing TIN
DEMs and contour trees for large terrains.
Abhinandan Nath,
Kyle Fox,
Pankaj K. Agarwal, and Kamesh Munagala.
Proceedings of the 24th ACM SIGSPATIAL
International Conference on Advances in Geographic Information
Systems (ACM SIGSPATIAL),
Article No. 25, 2016.
-
Integrating and sampling cuts in bounded
treewidth graphs.
With Ivona Bezáková and Erin W. Chambers.
Advances in the Mathematical Sciences: Research
from the 2015 Association for Women in Mathematics Symposium,
401–425, 2016.
-
Parallel algorithms for constructing range and
nearest-neighbor search data structures.
With Pankaj K. Agarwal, Kamesh Munagala, and Abhinandan Nath.
Proceedings of the 35th Annual Symposium on
Principles of Database Systems (PODS),
429–440, 2016.
-
Approximating dynamic time warping and edit
distance for a pair of point sequences.
With Pankaj K. Agarwal, Jiangwei Pan, and Rex Ying.
Proceedings of the 32nd International Symposium
on Computational Geometry (SoCG),
6:1–6:16, 2016.
-
A polynomial-time bicriteria approximation
scheme for planar bisection.
With Philip N. Klein and Shay Mozes.
Proceedings of the 47th Annual ACM
Symposium on Theory of Computing (STOC),
841–850, 2015.
STOC 2015 presentation slides available in
Keynote
and
pdf.
-
Counting and sampling minimum cuts in genus
g graphs.
With Erin W. Chambers and Amir Nayyeri.
Discrete & Computational Geometry,
52(3):450–475, 2014,
special issue of invited papers from the 29th Annual Symposium on
Computational Geometry.
Preliminary version appeared in
Proceedings of the 29th Annual Symposium on
Computational Geometry (SoCG),
249–258, 2013.
SoCG 2013 presentation slides (recommended) available in
Keynote
and
pdf.
UIUC Theory Seminar presentation slides available in
Keynote
and
pdf.
-
Spanning paths in Fibonacci-sum graphs.
With William B. Kinnersley, Daniel McDonald, Nathan Orlow,
and Gregory Puleo.
The Fibonacci Quarterly,
52(1):46–49, 2014.
-
Fast algorithms for surface embedded
graphs via homology.
Ph.D. Dissertation, Department of Computer Science,
University of Illinois at Urbana-Champaign, December 2013.
Dissertation defense slides available in
Keynote
and
pdf.
-
Packet forwarding algorithms in a
line network.
With Antonios Antoniadis, Neal Barcelo, Daniel Cole,
Benjamin Moseley, Michael Nugent, and Kirk Pruhs.
Proceedings of the 11th Annual Latin
American Theoretical Informatics (LATIN),
610–621, 2014.
-
Online non-clairvoyant scheduling to
simultaneously minimize all convex functions.
With Sungjin Im, Janardhan Kulkarni, and Benjamin Moseley.
Proceedings of the International Workshop
on Approximation Algorithms for Combinatorial Optimization
Problems (APPROX),
142–157, 2013.
-
Weighted flowtime on capacitated machines.
With Madhukar Korupolu.
Proceedings of the 24th Annual ACM-SIAM Symposium
on Discrete Algorithms (SODA),
129–143, 2013.
-
Shortest non-trivial cycles in directed
and undirected surface graphs.
Proceedings of the 24th Annual ACM-SIAM Symposium
on Discrete Algorithms (SODA),
352–364, 2013.
SODA 2013 presentation slides (recommended) available in
Keynote
and
pdf.
Some results given at the Computational Geometry:
Young Researcher Forum. Presentation slides available in
Keynote
and
pdf.
Some results given at the Washington University Combinatorics
Seminar. Presentation slides available in
Keynote
and
pdf.
-
Global minimum cuts in surface embedded
graphs.
With Jeff Erickson and Amir Nayyeri.
Proceedings of the 23rd Annual ACM-SIAM Symposium
on Discrete Algorithms (SODA),
1309–1318, 2012.
SODA 2012 presentation slides (recommended) available in
Keynote
and
pdf.
UIUC Theory Seminar presentation slides available in
Keynote
and
pdf.
-
Upper bounds for maximally greedy binary
search trees.
Proceedings of the Algorithms and Data Structures
Symposium (WADS),
411–422, 2011.
WADS 2011 presentation slides available in
Keynote
and
pdf.
-
Online scheduling on
identical machines using SRPT.
With Benjamin Moseley.
Proceedings of the 22nd Annual ACM-SIAM Symposium
on Discrete Algorithms (SODA),
120–128, 2011.
Revised as my Masters thesis for the Department of Computer Science,
University of Illinois at Urbana-Champaign, December 2010,
available in
pdf.
SODA 2011 presentation slides available in
Keynote
and
pdf.
-
Archon: Facilitating global access to
collections in small archives.
Scott Schwartz, Chris Prom, Kyle Fox,
Paul Sorensen.
Proceedings of the 74th Annual IFLA General
Conference and Council (WLIC),
2008.
-
A unified platform for archival
description and access.
Chris Prom, Chris Rishel, Scott Schwartz,
Kyle Fox.
Proceedings of the ACM/IEEE Joint Conference on
Digital Libraries (JCDL),
157–166, 2007.
-
Archon: A unified information storage and
retrieval system for lone archivists, special collections
librarians and curators.
Scott Schwartz, Chris Prom, Chris Rishel,
Kyle Fox.
Partnership: The Canadian Journal of Library and
Information Practice and Research, 1–17, 2007.