Speaker:

Yike Chen (University of Electronic Science and Technology of China)

Time:

• 16:20-17:20 (Time in Beijing)
• May 22, 2026 (Friday)

Venue:

518, Research Building 4

Abstract:

This talk studies the Unimodal-Cost k-Median problem: given n piecewise-linear
unimodal functions f_1,…,f_n: R -> R, choose k facilities y_1,…,y_k in 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+klog 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((m+nlogn)logm * \min{k,log m\sqrt{klogm},logm*2^{O(\sqrt{log k loglog m})}} )$