Fox, Kyle J.

Permanent URI for this collectionhttps://hdl.handle.net/10735.1/6559

Kyle J. Fox is an Assistant Professor in the Department of Computer Science. His research interests include:

  • Algorithms and theory
  • Computational Geometry and topology
  • Combinatorial optimization and graph algorithms

News

2020 recipient of a five-year, $586,654 National Science Foundation Faculty Early Career Development (CAREER) Award to explore how the mathematical field of topology can be used to design more efficient and faster algorithms to solve difficult problems. Read more.

Browse

Recent Submissions

Now showing 1 - 3 of 3
  • Thumbnail Image
    Item
    Holiest Minimum-Cost Paths and Flows in Surface Graphs
    (Association for Computing Machinery) Erickson, J.; Fox, Kyle J.; Lkhamsuren, L.; Fox, Kyle J.
    Let G be an edge-weighted directed graph with n vertices embedded on an orientable surface of genus g. We describe a simple deterministic lexicographic perturbation scheme that guarantees uniqueness of minimum-cost flows and shortest paths in G. The perturbations take O(gn) time to compute. We use our perturbation scheme in a black box manner to derive a deterministic O(n log log n) time algorithm for minimum cut in directed edge-weighted planar graphs and a deterministic O(g² n log n) time proprocessing scheme for the multiple-source shortest paths problem of computing a shortest path oracle for all vertices lying on a common face of a surface embedded graph. The latter result yields faster deterministic near-linear time algorithms for a variety of problems in constant genus surface embedded graphs. Finally, we open the black box in order to generalize a recent linear-time algorithm for multiple-source shortest paths in unweighted undirected planar graphs to work in arbitrary orientable surfaces. Our algorithm runs in O(g² n log g) time in this setting, and it can be used to give improved linear time algorithms for several problems in unweighted undirected surface embedded graphs of constant genus including the computation of minimum cuts, shortest topologically non-trivial cycles, and minimum homology bases.
  • Thumbnail Image
    Item
    An Efficient Algorithm for Computing High-Quality Paths Amid Polygonal Obstacles
    (Association for Computing Machinery) Agarwal, P. K.; Fox, Kyle J.; Salzman, O.; Fox, Kyle J.
    We study a path-planning problem amid a set O of obstacles in R², in which we wish to compute a short path between two points while also maintaining a high clearance from O; the clearance of a point is its distance from a nearest obstacle in O. Specifically, the problem asks for a path minimizing the reciprocal of the clearance integrated over the length of the path. We present the first polynomial-time approximation scheme for this problem. Let n be the total number of obstacle vertices and let ε ∈ (0, 1]. Our algorithm computes in time O(n²/ε² log n/ε) a path of total cost at most (1 + ε) times the cost of the optimal path.
  • Thumbnail Image
    Item
    Computing the Gromov-Hausdorff Distance for Metric Trees
    (Association for Computing Machinery) Agarwal, P. K.; Fox, Kyle J.; Nath, A.; Sidiropoulos, A.; Wang, Y.; Fox, Kyle J.
    The Gromov-Hausdorff (GH) distance is a natural way to measure distance between two metric spaces. We prove that it is NP-hard to approximate the GH distance better than a factor of 3 for geodesic metrics on a pair of trees. We complement this result by providing a polynomial time O(min{n, rn})-approximation algorithm for computing the GH distance between a pair of metric trees, where r is the ratio of the longest edge length in both trees to the shortest edge length. For metric trees with unit length edges, this yields an O_{√n}-approximation algorithm.1

Works in Treasures @ UT Dallas are made available exclusively for educational purposes such as research or instruction. Literary rights, including copyright for published works held by the creator(s) or their heirs, or other third parties may apply. All rights are reserved unless otherwise indicated by the copyright owner(s).