Yike Chen: Discrete Unimodal-Cost p-Median on a Line.

Abstract

This talk studies the Unimodal-Cost $k$-Median problem: given $n$ piecewise-linear
unimodal functions $f_1,\ldots,f_n: \mathbb{R} \to \mathbb{R}$, choose $k$ facilities $y_1,\ldots,y_k$ in $\mathbb{R}$ to minimize $\sum_i \min_r f_i(y_r)$. The classical special case $f_i(y)=w_i|y-z_i|$ arises in facility placement and has been well studied [Love 1976; Hassin & Tamir 1991; Chen & Wang 2014]. We consider general unimodal costs, allowing asymmetry.

For $k=2$, we give an $O((n+k\log k)\log n)$ exact algorithm via total monotonicity and divide-and-conquer. For general $k$, we reduce the problem to a minimum-weight $k$-link path with Monge costs, and combine a direct $k$-stage DP with the frameworks of Aggarwal et al. [1993] and Schieber [1998], using batched column-minimum primitives in place of $O(1)$ edge-weight access. With $m$ total breakpoints, the overall time is

$$O\!\left((m+n\log n)\log m \cdot \min\left\{k,\; \log m\sqrt{k\log m},\; \log m\cdot 2^{O(\sqrt{\log k\,\log\log m})}\right\}\right).$$