We found a match
Your institution may have access to this item. Find your institution then sign in to continue.
- Title
A Bottleneck Matching Problem with Edge-Crossing Constraints.
- Authors
Carlsson, John Gunnar; Armbruster, Benjamin; Rahul, Saladi; Bellam, Haritha
- Abstract
Motivated by a crane assignment problem, we consider a Euclidean bipartite matching problem with edge-crossing constraints. Specifically, given red points and blue points in the plane, we want to construct a perfect matching between red and blue points that minimizes the length of the longest edge, while imposing a constraint that no two edges may cross each other. We show that the problem cannot be approximately solved within a factor less than 1:277 in polynomial time unless . We give simple dynamic programming algorithms that solve our problem in two special cases, namely (1) the case where the red and blue points form the vertices of a convex polygon and (2) the case where the red points are collinear and the blue points lie to one side of the line through the red points.
- Subjects
MATHEMATICAL models; EUCLIDEAN geometry; APPROXIMATION theory; DYNAMIC programming; ALGORITHMS; CONVEX domains; POLYGONS
- Publication
International Journal of Computational Geometry & Applications, 2015, Vol 25, Issue 4, p245
- ISSN
0218-1959
- Publication type
Article
- DOI
10.1142/S0218195915500144