  Let $A$ and $B$ be two point sets in the plane of sizes $r$ and $n$
respectively (assume $r \leq n$), and let $k$ be a parameter. A matching
between $A$ and $B$ is a family of pairs in $A \times B$ so that any point of
$A \cup B$ appears in at most one pair. Given two positive integers $p$ and
$q$, we define the cost of matching $M$ to be $c(M) = \sum_{(a, b) \in
M}\|{a-b}\|_p^q$ where $\|{\cdot}\|_p$ is the $L_p$-norm. The geometric partial
matching problem asks to find the minimum-cost size-$k$ matching between $A$
and $B$.
  We present efficient algorithms for geometric partial matching problem that
work for any powers of $L_p$-norm matching objective: An exact algorithm that
runs in $O((n + k^2) {\mathop{\mathrm{polylog}}} n)$ time, and a $(1 +
\varepsilon)$-approximation algorithm that runs in $O((n + k\sqrt{k})
{\mathop{\mathrm{polylog}}} n \cdot \log\varepsilon^{-1})$ time. Both
algorithms are based on the primal-dual flow augmentation scheme; the main
improvements involve using dynamic data structures to achieve efficient flow
augmentations. With similar techniques, we give an exact algorithm for the
planar transportation problem running in $O(\min\{n^2, rn^{3/2}\}
{\mathop{\mathrm{polylog}}} n)$ time.
