# Two Algorithmic Schemes for Geometric Bipartite Matching and Transportation

## Date

2020

## Authors

## Advisors

## Journal Title

## Journal ISSN

## Volume Title

## Repository Usage Stats

views

downloads

## Abstract

Given n red points and n blue points in d-dimensional space and a distance function, the geometric bipartite matching problem is to find a matching of red points to blue points, such that the sum of distances between the matched pairs is minimized. The general graph problem, minimum-cost bipartite matching, can be solved in polynomial time using the classical Hungarian algorithm, which leads to a cubic algorithm for the geometric matching problem. We present several algorithms for computing optimal and near-optimal geometric bipartite matching and its fractional generalization, geometric transportation. We also present fast algorithms for partial matching, i.e., match only k pairs for a given k <= n.

Finally, we consider the case when red points are allowed to translate (rigidly) and the goal is to find a partial matching minimum-cost matching under all translations of red points. We assume the cost of a matching to be the sum of squares of edge costs (RMS). For a given translation t, let f(t) denote the cost of optimal partial matching (for a fixed k). A long-standing open problem is whether the number of local minima in f(t) is polynomial; the best upper bounds are exponential. We show that there is an approximation g(t) of the function f(t) that has only quadratic number of local minima.

## Type

## Department

## Description

## Provenance

## Citation

## Permalink

## Citation

Xiao, Allen (2020). *Two Algorithmic Schemes for Geometric Bipartite Matching and Transportation*. Dissertation, Duke University. Retrieved from https://hdl.handle.net/10161/21520.

## Collections

Dukes student scholarship is made available to the public using a Creative Commons Attribution / Non-commercial / No derivative (CC-BY-NC-ND) license.