An Optimal Hypercube Algorithm for the All Nearest Smaller Values Problem (2007)
Given a sequence of n elements, the All Nearest Smaller Values (ANSV) problem is to find, for each element in the sequence, the nearest element to the left (right) that is smaller, or to report that...
Wolfgang W. Bein, Peter Brucker, Dina Kravets, James K. Park
When restricted to cost arrays possessing the sum Monge property, many combinatorial optimization problems with sum objective functions become significantly easier to solve. (An array A = fa[i; j]g...
Alok Aggarwal, Amotz Bar-noy, Samir Khuller, Dina Kravets, Baruch Schieber
We present efficient algorithms for finding a minimum cost perfect matching, and for solving the transportation problem in bipartite graphs, G = (Sinks [ Sources; Sinks 2 Sources), where jSinksj = n,...
Finding Farthest Neighbors in a Convex Polygon and Related Problems. (1998)
Aggarwal et al. showed how to compute in O(n) time one farthest vertex for every vertex of a convex n-gon. Thesis extends the results of Aggarwal et. al. by developing the following algorithms: 1) An...
All Nearest Smaller Values on the Hypercube (1996)
Given a sequence of n elements, the All Nearest Smaller Values (ANSV) problem is to find, for each element in the sequence, the nearest element to the left (right) that is smaller, or to report that...
An Optimal Hypercube Algorithm for the All Nearest Smaller Values Problem (1994)
Given a sequence of n elements, the All Nearest Smaller Values (ANSV) problem is to find, for each element in the sequence, the nearest element to the left (right) that is smaller, or to report that...
Efficient Minimum Cost Matching and Transportation Using Quadrangle Inequality (1993)
Aggarwal, Alok, Bar-Noy, Amotz, Khuller, Samir, Kravets, Dina, Schieber, Baruch
We present efficient algorithms for finding a minimum cost perfect matching, and for solving the transportation problem in bipartite graphs, G=(\Red\cup \Blue, \Red\times \Blue), where |\Red|=n,...
Efficient Minimum Cost Matching and Transportation Using Quadrangle Inequality (1993)
Aggarwal, Alok, Bar-Noy, Amotz, Khuller, Samir, Kravets, Dina, Schieber, Baruch
We present efficient algorithms for finding a minimum cost perfect matching, and for solving the transportation problem in bipartite graphs, G=(\Red\cup \Blue, \Red\times \Blue), where |\Red|=n,...
Geometric Pattern Matching under Euclidean Motion (1993)
Paul Chew, Michael T. Goodrich, Daniel P. Huttenlocher, Klara Kedem, Jon M. Kleinberg, Dina Kravets
Given two planar sets A and B, we examine the problem of determining the smallest " such that there is a Euclidean motion (rotation and translation) of A that brings each member of A within...
Geometric Pattern Matching under Euclidean Motion (1993)
L. Paul Chew, Michael T. Goodrich, Daniel P. Huttenlocher, Klara Kedem, Jon M. Kleinberg, Dina Kravets
Given two planar sets A and B, we examine the problem of determining the smallest " such that there is a Euclidean motion (rotation and translation) of A that brings each member of A within...
Combinatorial geometric optimization /--by Dina Kravets. (1992)
Thesis (Ph. D.)--Massachusetts Institute of Technology, Dept. of Electrical Engineering and Computer Science, 1992.
Finding farthest neighbors in a convex polygon and related problems /--by Dina Kravets. (1988)
Supervised by Alok Aggarwal and Frank Thomson Leighton.