5 papers
Dynamic Dyck and Tree Edit Distance: Decompositions and Reductions to String Edit Distance
Debarati Das, Jacob Gilbert, MohammadTaghi Hajiaghayi +2
We present the first dynamic algorithms for Dyck and tree edit distances with subpolynomial update times. Dyck edit distance measures how far a parenthesis string is from a well-pa…
Weighted Edit Distance Computation: Strings, Trees and Dyck
Debarati Das, Jacob Gilbert, MohammadTaghi Hajiaghayi +2
Given two strings of length over alphabet , and an upper bound on their edit distance, the algorithm of Myers (Algorithmica'86) and Landau and Vishkin (JCSS'88) computes…
-time Algorithm for Bounded Tree Edit Distance
Debarati Das, Jacob Gilbert, MohammadTaghi Hajiaghayi +3
Computing the edit distance of two strings is one of the most basic problems in computer science and combinatorial optimization. Tree edit distance is a natural generalization of e…
Generalized Stochastic Matching
Alireza Farhadi, Jacob Gilbert, MohammadTaghi Hajiaghayi
In this paper, we generalize the recently studied Stochastic Matching problem to more accurately model a significant medical process, kidney exchange, and several other application…
Competitively Pricing Parking in a Tree
Max Bender, Jacob Gilbert, Aditya Krishnan +1
Motivated by demand-responsive parking pricing systems we consider posted-price algorithms for the online metrical matching problem and the online metrical searching problem in a t…