  We investigate the problem of Min-cost Perfect Matching with Delays (MPMD) in
which requests are pairwise matched in an online fashion with the objective to
minimize the sum of space cost and time cost. Though linear-MPMD (i.e., time
cost is linear in delay) has been thoroughly studied in the literature, it does
not well model impatient requests that are common in practice. Thus, we propose
convex-MPMD where time cost functions are convex, capturing the situation where
time cost increases faster and faster. Since the existing algorithms for
linear-MPMD are not competitive any more, we devise a new deterministic
algorithm for convex-MPMD problems. For a large class of convex time cost
functions, our algorithm achieves a competitive ratio of $O(k)$ on any
$k$-point uniform metric space, or $O(k\Delta)$ when the metric space has
aspect ratio $\Delta$. Moreover, we prove lower bounds for the competitive
ratio of deterministic and randomized algorithms, indicating that our
deterministic algorithm is optimal. This optimality uncover a substantial
difference between convex-MPMD and linear-MPMD, since linear-MPMD allows a
deterministic algorithm with constant competitive ratio on any uniform metric
space.
