{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,28]],"date-time":"2025-10-28T03:14:08Z","timestamp":1761621248025},"reference-count":8,"publisher":"World Scientific Pub Co Pte Lt","issue":"04","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Int. J. Comput. Geom. Appl."],"published-print":{"date-parts":[[2015,12]]},"abstract":"<jats:p> Motivated by a crane assignment problem, we consider a Euclidean bipartite matching problem with edge-crossing constraints. Specifically, given [Formula: see text] red points and [Formula: see text] 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 [Formula: see text]. 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. <\/jats:p>","DOI":"10.1142\/s0218195915500144","type":"journal-article","created":{"date-parts":[[2016,2,1]],"date-time":"2016-02-01T03:32:48Z","timestamp":1454297568000},"page":"245-261","source":"Crossref","is-referenced-by-count":8,"title":["A Bottleneck Matching Problem with Edge-Crossing Constraints"],"prefix":"10.1142","volume":"25","author":[{"given":"John Gunnar","family":"Carlsson","sequence":"first","affiliation":[{"name":"Epstein Department of Industrial and Systems Engineering, University of Southern California, 3715 McClintock Ave, Los Angeles, California 90089-0193, USA"}]},{"given":"Benjamin","family":"Armbruster","sequence":"additional","affiliation":[{"name":"Department of Industrial Engineering and Management Sciences, Northwestern University, 2145 Sheridan Road, Evanston, Illinois 60208, USA"}]},{"given":"Saladi","family":"Rahul","sequence":"additional","affiliation":[{"name":"Department of Computer Science and Engineering, University of Minnesota, 200 Union Street Southeast, Minneapolis, Minnesota 55455, USA"}]},{"given":"Haritha","family":"Bellam","sequence":"additional","affiliation":[{"name":"Department of Computer Science and Engineering, University of Minnesota, 200 Union Street Southeast, Minneapolis, Minnesota 55455, USA"}]}],"member":"219","published-online":{"date-parts":[[2016,1,27]]},"reference":[{"key":"p_2","doi-asserted-by":"publisher","DOI":"10.1007\/BF01990536"},{"key":"p_3","doi-asserted-by":"publisher","DOI":"10.1016\/0012-365X(93)90124-C"},{"key":"p_4","doi-asserted-by":"publisher","DOI":"10.1016\/S0012-365X(99)00201-0"},{"key":"p_5","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-33090-2_5"},{"key":"p_6","doi-asserted-by":"publisher","DOI":"10.1002\/nav.10124"},{"key":"p_7","doi-asserted-by":"publisher","DOI":"10.1057\/palgrave.jors.2602110"},{"key":"p_8","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539700373520"},{"key":"p_9","doi-asserted-by":"publisher","DOI":"10.1137\/0211025"}],"container-title":["International Journal of Computational Geometry &amp; Applications"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.worldscientific.com\/doi\/pdf\/10.1142\/S0218195915500144","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,8,7]],"date-time":"2019-08-07T13:53:18Z","timestamp":1565185998000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.worldscientific.com\/doi\/abs\/10.1142\/S0218195915500144"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2015,12]]},"references-count":8,"journal-issue":{"issue":"04","published-online":{"date-parts":[[2016,1,27]]},"published-print":{"date-parts":[[2015,12]]}},"alternative-id":["10.1142\/S0218195915500144"],"URL":"https:\/\/doi.org\/10.1142\/s0218195915500144","relation":{},"ISSN":["0218-1959","1793-6357"],"issn-type":[{"value":"0218-1959","type":"print"},{"value":"1793-6357","type":"electronic"}],"subject":[],"published":{"date-parts":[[2015,12]]}}}