DROPS

Document

DOI: 10.4230/LIPIcs.ESA.2026.79

Unimodal-Cost k-Median on a Line

Authors: Yike Chen and Chao Xu

Published in: LIPIcs, Volume 388, 34th Annual European Symposium on Algorithms (ESA 2026)

Abstract

Given n piecewise-linear unimodal functions f_1,… ,f_n:ℝ → ℝ and an integer 1 ≤ k ≤ n, the Unimodal-Cost k-Median problem asks for k real numbers y_1,… ,y_k minimizing ∑_{i=1}^n min_{1 ≤ r ≤ k} f_i(y_r). Let m be the number of breakpoints: the total number of affine-piece endpoint occurrences plus one occurrence at a chosen minimizer of each function. We give an exact algorithm running in O((m+nlog n)log m ⋅ min{k, log m√{klog m}, log m⋅ 2^O(√{log k log log m})}) . The first term inside the minimum comes from a direct k-stage dynamic program. The other two use the minimum-weight k-link path algorithms of Aggarwal et al. [Aggarwal et al., 1994] and Schieber [Schieber, 1998] for Monge costs, replacing their O(1) edge-weight access by batched access to the implicit transition costs.

Cite as

Yike Chen and Chao Xu. Unimodal-Cost k-Median on a Line. In 34th Annual European Symposium on Algorithms (ESA 2026). Leibniz International Proceedings in Informatics (LIPIcs), Volume 388, pp. 79:1-79:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2026)

Copy BibTex To Clipboard

@InProceedings{chen_et_al:LIPIcs.ESA.2026.79,
  author =	{Chen, Yike and Xu, Chao},
  title =	{{Unimodal-Cost k-Median on a Line}},
  booktitle =	{34th Annual European Symposium on Algorithms (ESA 2026)},
  pages =	{79:1--79:15},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-445-1},
  ISSN =	{1868-8969},
  year =	{2026},
  volume =	{388},
  editor =	{Bille, Philip and Pettie, Seth and Storandt, Sabine},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ESA.2026.79},
  URN =		{urn:nbn:de:0030-drops-272153},
  doi =		{10.4230/LIPIcs.ESA.2026.79},
  annote =	{Keywords: unimodal-cost k-median, Monge, k-link path, dynamic programming, total monotonicity}
}

Document

DOI: 10.4230/LIPIcs.ISAAC.2025.18

An Optimal Algorithm for the Stacker Crane Problem on Fixed Topologies

Authors: Yike Chen, Ke Shi, and Chao Xu

Published in: LIPIcs, Volume 359, 36th International Symposium on Algorithms and Computation (ISAAC 2025)

Abstract

The Stacker Crane Problem (SCP) is a variant of the Traveling Salesman Problem. In SCP, pairs of pickup and delivery points are designated on a graph, and a crane must visit these points to move objects from each pickup location to its respective delivery point. The goal is to minimize the total distance traveled. SCP is known to be NP-hard, even on trees. The only positive results, in terms of polynomial-time solvability, apply to graphs that are topologically equivalent to a path or a cycle. We propose an algorithm that is optimal for each fixed topology, running in near-linear time. This is achieved by demonstrating that the problem is fixed-parameter tractable (FPT) when parameterized by both the cycle rank and the number of branch vertices.

Cite as

Yike Chen, Ke Shi, and Chao Xu. An Optimal Algorithm for the Stacker Crane Problem on Fixed Topologies. In 36th International Symposium on Algorithms and Computation (ISAAC 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 359, pp. 18:1-18:12, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{chen_et_al:LIPIcs.ISAAC.2025.18,
  author =	{Chen, Yike and Shi, Ke and Xu, Chao},
  title =	{{An Optimal Algorithm for the Stacker Crane Problem on Fixed Topologies}},
  booktitle =	{36th International Symposium on Algorithms and Computation (ISAAC 2025)},
  pages =	{18:1--18:12},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-408-6},
  ISSN =	{1868-8969},
  year =	{2025},
  volume =	{359},
  editor =	{Chen, Ho-Lin and Hon, Wing-Kai and Tsai, Meng-Tsung},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ISAAC.2025.18},
  URN =		{urn:nbn:de:0030-drops-249269},
  doi =		{10.4230/LIPIcs.ISAAC.2025.18},
  annote =	{Keywords: Stacker Crane Problem, Fixed-Parameter Tractable, Min-Cost Circulation}
}

Search Results

Documents authored by Chen, Yike

Unimodal-Cost k-Median on a Line

Abstract

Cite as

An Optimal Algorithm for the Stacker Crane Problem on Fixed Topologies

Abstract

Cite as

Thanks for your feedback!

Could not send message