REVIEW 2 major objections 6 minor 47 references
Planar p-center problems are solvable in polynomial time when clustering a Pareto Front
T0 review · 2 major / 6 minor · reviewed 2026-08-14 · deepseek-v4-flash
Pith's one-line read Planar K-center clustering, NP-hard in general, is solvable in polynomial time for two-dimensional Pareto fronts via a dynamic program that cuts the front into contiguous blocks.
desk verdict The paper has a credible DP design and improved complexity bounds for p-center on 2D Pareto fronts, but the proof of the load-bearing interval-optimality lemma has a false containment and needs a real fix before the main theorem is supported. read the letter →
The pith
A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.
The reading
What carries the argument
The load-bearing object is the interval property induced by the Pareto order. Because any two points of a 2D Pareto front are comparable in the sense $x_i \prec x_j$ when both coordinates order oppositely, sorting by one objective totally orders the front, and Euclidean distances from either endpoint grow monotonically along the order. This makes the cost of a cluster depend only on its extreme indices—for the continuous 1-center, exactly half the distance between the extremes—and it lets the paper restrict dynamic programming to clusters that are contiguous index intervals. Inside each DP line, the cost as a function of the split point is first decreasing then increasing (unimodal), so a binary search finds each $C_{i,k}$ in $O(\log i)$ cost evaluations; a memory-efficient backtracking pass then recovers an optimal partition in $O(N\log N)$ time.
What would settle it
Take a small random 2D Pareto front (for example $N=8$, $K=3$), compute the exact discrete K-center optimum by exhaustive enumeration of all partitions, and compare it with the DP restricted to interval clusters; any instance where the interval optimum is strictly larger would disprove Proposition 3 and break Theorem 1 for the discrete case.
Extended reading notes
Core claim
The paper's central claim is Theorem 1: for a set $E=\{x_1,\ldots,x_N\}$ of pairwise Pareto-incomparable points in $\mathbb{R}^2$, both the continuous and discrete K-center problems—cover the points with K equal-radius disks, with centers anywhere or restricted to the point set, minimizing the radius—admit exact polynomial-time solutions. The mechanism is Proposition 3, which states that there exists an optimal solution whose clusters are intervals $C_{i,i'} = \{x_j : i\le j\le i'\}$ in the total order induced by sorting on the first coordinate. With interval clusters, the recurrence $C_{i,k} = \min_j \max(C_{j-1,k-1}, f^\gamma(C_{j,i}))$ computes optimal values by dynamic programming; each line of the DP table is computed by logarithmic dichotomic search, because the objective is unimodal in $j$. The stated complexities are $O(KN\log N)$ time and $O(N)$ space for the continuous case, and $O(KN\log^2 N)$ time and $O(N)$ space for the discrete case with $K\ge 3$, with special cases $O(N)$ for 1-center and $O(N\log N)$ for discrete 2-center.
Load-bearing premise
The whole algorithm stands on Proposition 3, which says that after sorting, some optimal clustering uses only contiguous index blocks; the proof of that proposition in Section 4.3 contains a step where the final block is treated as a subset of the original final cluster when it is actually a superset, so an additional geometric argument is needed to justify the interval property in the discrete case.
Editorial extensions
If this is right
- Bi-objective optimizers can replace heuristic archiving of nondominated solutions with exact K-center summaries, giving a provably smallest covering radius for any chosen K.
- The same DP handles continuous and discrete variants, so users can choose between arbitrary centers and centers restricted to the front without reimplementing the algorithm.
- The $O(N)$ memory footprint and near-linear per-K costs make repeated runs for different K practical for elbow analysis of the optimal radius.
- Special cases improve on general planar bounds: 1-center in $O(N)$, discrete 2-center in $O(N\log N)$, and continuous 2-center in $O(N\log N)$.
- Computing all k-center values up to a bound $K'$ costs $O(NK'\log^{1+\gamma}N)$, which keeps the DP useful for sweeping K when the user does not know the right number of clusters in advance.
Reading between the lines
- This structure suggests the same DP should extend to other geometries whose cluster cost depends only on the extreme points, such as the $L_\infty$ norm; random-front experiments would confirm the extension.
- Because each line of the DP table is independent once the previous line is known, the $O(N)$-space version should parallelize well on GPUs, with the biggest wall-clock gain in the discrete $\log^2 N$ case.
- For a decision-maker, the near-linear runtime would make the elbow curve of optimal radius versus $K$ interactive even for large fronts, an operational use the paper mentions only briefly.
- The gap between the continuous and discrete bounds comes entirely from computing each discrete cluster cost by binary search over candidate centers, so a faster discrete cluster-cost data structure would immediately sharpen the discrete complexity.
Signed reviews
Editorial analysis
A structured set of objections, weighed in public.
Referee Report
Summary. The paper considers the continuous and discrete K-center clustering problems for a set E of N points in R^2 that are pairwise incomparable under Pareto dominance (a 2D Pareto front). It claims that both problems are solvable in polynomial time, with O(KN log N) time and O(N) space for the continuous case (K >= 2), and O(KN log^2 N) time and O(N) space for the discrete case (K >= 3), with special cases for 1-center and 2-center. The algorithmic core is a dynamic program (Section 5, Eq. (18)) whose validity rests on Proposition 3, a structural result asserting that there exists an optimal partition in which every cluster is a contiguous index interval C_{i,i'} = {x_j : i <= j <= i'}.
Significance. If the main result is correct, it is a significant contribution: planar p-center problems are NP-hard in general, and identifying the Pareto-front restriction as a polynomially solvable class is both natural and useful for multi-objective optimization applications. The proposed unified DP has attractive near-linear running times and linear memory. However, the central structural claim (Proposition 3) is not proved as written, and the correctness of the DP is exactly contingent on that claim. The paper does provide useful intermediate observations (e.g., O(1) continuous cluster costs via extremes, O(log n) discrete cluster costs) and a plausible algorithmic framework, but the current proof gap must be resolved before the main theorem can be accepted.
major comments (2)
- [Section 4.3, Proposition 3] The proof of Proposition 3 contains a false containment. It defines C'_K = {x_j : i <= j <= N} and asserts "for all k, C'_k ⊂ C_k" to conclude via Lemma 5 that f_gamma(C'_k) <= f_gamma(C_k) <= OPT. For k = K, however, C'_K is a superset of C_K, not a subset, because C_K is the cluster containing x_N and i is the smallest index in C_K, but C'_K includes every Pareto point with index between i and N, including points that may belong to other clusters. Lemma 5 gives f(C'_K) >= f(C_K), so the needed bound f(C'_K) <= OPT does not follow. Since the DP recurrence in Section 5, Eq. (18), restricts attention to interval clusters and is justified solely by Proposition 3, the central polynomial-time claim is not established by the proof as written. The interval property may be true and recoverable by a different exchange or induction argument, but no such argument is supplied. This is a load-bearing gap, not a cosmetic issue.
- [Section 6.2] The paper remarks that "Many optimal solutions may be nested, i.e. non verifying the Proposition 3." This does not contradict Proposition 3, which only asserts existence of at least one optimal interval solution. But it underscores that the proof must construct such a solution without relying on the false containment. The current proof does not do so, and the remark does not repair the derivation.
minor comments (6)
- [Section 4.3, Proposition 3 proof] The text writes "f_gamma(C'_k) ⊂ f_gamma(C_k)"; the subset symbol should be the inequality "<=".
- [Section 5.2, Proposition 5] The statement "O(log^gamma i)" is inconsistent with the surrounding analysis; it should be "O(log^{1+gamma} i)" (i.e., O(log i) for continuous, O(log^2 i) for discrete), matching the complexity proof of Theorem 1.
- [Algorithm 1 (Section 4.4)] In the line "Compute idMid = floor((i+i')/2)", the midpoint should be computed from the current search bounds idInf and idSup, not from the original endpoints i and i'. As printed, the dichotomic search would not narrow correctly.
- [Algorithm 4 (Section 5.3)] The while loop contains "minId = minId", which is an infinite loop. Presumably the intent is to decrement minId (minId <- minId - 1) or similar; without this fix, Algorithm 4 does not terminate and Proposition 6 is unsupported.
- [Appendix A, Lemma 10 proof] After translating the origin to the midpoint x_0 = (x_i + x_j)/2, the coordinates of x_0 should be (0,0), not (1/2 sqrt(2) diam, 1/2 sqrt(2) diam). The proof of equation (21) needs to be reworked; the conclusion of Lemma 3 is standard, but the proof as printed is garbled.
- [Appendix A, Lemma 6 proof] The proof refers to "Proposition 2" when it means "Lemma 2" (the monotonic distance lemma).
Circularity Check
No circularity: the parameter-free DP derivation is self-contained; the false-containment issue in Proposition 3 is a proof gap, not a reduction of the result to its own inputs.
full rationale
The paper's central claim is that planar p-center clustering on a 2D Pareto front is polynomial-time solvable via a dynamic program over contiguous index intervals. No parameter is fitted and then renamed as a prediction; the cluster-cost formulas in Lemmas 3 and 4 are derived from the hypotheses, and the DP recurrence in Equation (18) is a direct consequence of the stated definitions. The only potentially load-bearing appeal to prior work is to the authors' earlier clustering papers [14,15,16], but those citations are used for context and comparison, not to prove the new complexity theorem. The induction in Proposition 3 does contain a genuine mathematical error: the text asserts C'_k subset C_k for all k, but for k=K the constructed interval C'_K is a superset of the original cluster C_K, so the inequality f(C'_K) <= OPT is not established by Lemma 5 as written. That is a correctness and proof-completeness defect that weakens the justification of the interval-clustering property, but it is not a circularity: the paper does not define its conclusion into its assumptions, does not fit a parameter to the target quantity, and does not import its central claim from a self-citation. Since no circular step can be exhibited under the required standard, the appropriate circularity finding is 0, with the proof gap flagged separately as a correctness risk rather than as circular reasoning.
Assumptions & free parameters
assumptions (4)
- domain assumption All points in E are pairwise Pareto-incomparable, so ordering by first coordinate implies the second coordinate is strictly decreasing.
- standard math Euclidean distance in R2 and the triangle inequality hold.
- standard math Cluster cost is monotone under inclusion of point sets.
- domain assumption Discrete centers must be chosen among the points of the cluster.
Cite this review
Pith. "Pith review of Planar p-center problems are solvable in polynomial time when clustering a Pareto Front." pith.science (2026). https://pith.science/paper/42AKTFYS
@misc{pith2026190809648,
author = {Pith},
title = {Pith review of: Planar p-center problems are solvable in polynomial time when clustering a Pareto Front},
year = {2026},
howpublished = {\url{https://pith.science/paper/42AKTFYS}},
note = {Machine review of arXiv:1908.09648}
}
abstract
This paper is motivated by real-life applications of bi-objective optimization. Having many non dominated solutions, one wishes to cluster the Pareto front using Euclidian distances. The p-center problems, both in the discrete and continuous versions, are proven solvable in polynomial time with a common dynamic programming algorithm. Having $N$ points to partition in $K\geqslant 3$ clusters, the complexity is proven in $O(KN\log N)$ (resp $O(KN\log^2 N)$) time and $O(KN)$ memory space for the continuous (resp discrete) $K$-center problem. $2$-center problems have complexities in $O(N\log N)$. To speed-up the algorithm, parallelization issues are discussed. A posteriori, these results allow an application inside multi-objective heuristics to archive partial Pareto Fronts.
Figures
Reference graph
Works this paper leans on
-
[1]
P. Agarwal and C. Procopiuc. Exact and approximation alg orithms for clustering. Algo- rithmica, 33(2):201–226, 2002
work page 2002
-
[2]
P. Agarwal, M. Sharir, and E. W elzl. The discrete 2-cente r problem. Discrete & Com- putational Geometry , 20(3):287–305, 1998
work page 1998
- [3]
-
[4]
P. Brass, C. Knauer, H. Na, C. Shin, and A. Vigneron. Compu ting k-centers on a line. arXiv preprint arXiv:0902.3282 , 2009
work page Pith review arXiv 2009
-
[5]
K. Bringmann, S. Cabello, and M. Emmerich. Maximum volum e subset selection for anchored boxes. arXiv preprint arXiv:1803.00849 , 2018
arXiv 2018
-
[6]
K. Bringmann, T. Friedrich, and P. Klitzke. Two-dimensi onal subset selection for hy- pervolume and epsilon-indicator. In Annual Conference on Genetic and Evolutionary Computation, pages 589–596. ACM, 2014
work page 2014
- [7]
-
[8]
H. Calik and B. Tansel. Double bound method for solving th e p-center location problem. Computers & operations research , 40(12):2991–2999, 2013
work page 2013
Show all 47 references
-
[9]
Callaghan, S
B. Callaghan, S. Salhi, and G. Nagy. Speeding up the optim al method of Drezner for the p-centre problem in the plane. European Journal of Operational Research , 257(3):722– 734, 2017
2017
-
[10]
Network and discrete location: models, algorithms and appl ications
M Daskin. Network and discrete location: models, algorithms and appl ications. Wiley, 1995
1995
-
[11]
The p-centre problemheuristic and optima l algorithms
Zvi Drezner. The p-centre problemheuristic and optima l algorithms. Journal of the Operational Research Society, 35(8):741–748, 1984
1984
-
[12]
On the rectangular p-center problem
Zvi Drezner. On the rectangular p-center problem. Naval Research Logistics (NRL) , 34(2):229–234, 1987
1987
-
[13]
N. Dupin. Mod´ elisation et r´ esolution de grands probl` emes stochastiques combinatoires: application ` a la gestion de production d’´ electricit´ e. PhD thesis, Univ. Lille 1, 2015
2015
-
[14]
Dupin, F
N. Dupin, F. Nielsen, and E. Talbi. Dynamic programming heuristic for k-means cluster- ing among a 2-dimensional pareto frontier. 7th International Conference on Metaheuris- tics and Nature Inspired Computing , pages 1–8, 2018. 16
2018
-
[15]
Dupin, F
N. Dupin, F. Nielsen, and E. Talbi. k-medoids clusterin g is solvable in polynomial time for a 2d Pareto front. In World Congress on Global Optimization , pages 790–799. Springer, 2019
2019
-
[16]
Dupin and E
N. Dupin and E. Talbi. Clustering in a 2-dimensional Par eto Front: p-median and p- center are solvable in polynomial time. arXiv preprint arXiv:1806.02098 , 2018
2018 arXiv
-
[17]
Ehrgott and X
M. Ehrgott and X. Gandibleux. Multiobjective combinat orial optimization - theory, methodology, and applications. In Multiple criteria optimization: State of the art anno- tated bibliographic surveys , pages 369–444. Springer, 2003
2003
-
[18]
Elloumi, M
S. Elloumi, M. Labb´ e, and Y. Pochet. A new formulation a nd resolution method for the p-center problem. INFORMS Journal on Computing , 16(1):84–94, 2004
2004
-
[19]
Elshaikh, S
A. Elshaikh, S. Salhi, and G. Nagy. The continuous p-cen tre problem: An investiga- tion into variable neighbourhood search with memory. European Journal of Operational Research, 241(3):606–621, 2015
2015
-
[20]
Eppstein
D. Eppstein. Faster construction of planar two-center s. In SODA, volume 97, pages 131–138, 1997
1997
-
[21]
Ferone, P
D. Ferone, P. Festa, A. Napoletano, and M. Resende. A new local search for the p-center problem based on the critical vertex concept. In Internat. Conference on Learning and Intelligent Optimization , pages 79–92. Springer, 2017
2017
-
[22]
Gonzalez
T. Gonzalez. Clustering to minimize the maximum interc luster distance. Theoretical Computer Science , 38:293 – 306, 1985
1985
-
[23]
Grønlund et al
A. Grønlund et al. Fast exact k-means, k-medians and Bre gman divergence clustering in 1d. arXiv preprint arXiv:1701.07204 , 2017
2017 arXiv
-
[24]
Guo-Hui and G
L. Guo-Hui and G. Xue. K-center and k-median problems in graded distances. Theoretical computer science, 207(1):181–192, 1998
1998
-
[25]
Hochbaum
D.S. Hochbaum. When are NP-hard location problems easy ? Annals of Operations Research, 1(3):201–214, 1984
1984
-
[26]
Hochbaum and D.B
D.S. Hochbaum and D.B. Shmoys. A best possible heuristi c for the k-center problem. Mathematics of operations research , 10(2):180–184, 1985
1985
-
[27]
Hsu and G
W. Hsu and G. Nemhauser. Easy and hard bottleneck locati on problems. Discrete Applied Mathematics , 1(3):209–215, 1979
1979
-
[28]
Hwang, R
R. Hwang, R. Lee, and R. Chang. The slab dividing approac h to solve the Euclidean P-Center problem. Algorithmica, 9(1):1–22, 1993
1993
-
[29]
Karmakar, S
A. Karmakar, S. Das, S. Nandy, and B. Bhattacharya. Some variations on constrained minimum enclosing circle problem. Journal of Combinatorial Optimization , 25(2):176– 190, 2013
2013
-
[30]
T. Kuhn, C. Fonseca, L. Paquete, S. Ruzika, M. Duarte, an d J. Figueira. Hypervol- ume subset selection in two dimensions: Formulations and al gorithms. Evolutionary Computation, 24(3):411–425, 2016
2016
-
[31]
Mahajan, P
M. Mahajan, P. Nimbhorkar, and K. Varadarajan. The plan ar k-means problem is NP- hard. Theoretical Computer Science , 442:13–21, 2012
2012
-
[32]
N. Megiddo. Linear-time algorithms for linear program ming in R3 and related problems. SIAM journal on computing , 12(4):759–776, 1983
1983
-
[33]
Megiddo and K
N. Megiddo and K. Supowit. On the complexity of some comm on geometric location problems. SIAM journal on computing , 13(1):182–196, 1984
1984
-
[34]
Megiddo and A
N. Megiddo and A. Tamir. New results on the complexity of p-centre problems. SIAM Journal on Computing , 12(4):751–758, 1983
1983
-
[35]
Mladenovi´ c, M
N. Mladenovi´ c, M. Labb´ e, and P. Hansen. Solving the p-center problem with tabu search and variable neighborhood search. Networks, 42(1):48–64, 2003. 17
2003
-
[36]
Peugeot, N
T. Peugeot, N. Dupin, M-J Sembely, and C. Dubecq. MBSE, P LM, MIP and Robust Optimization for System of Systems Management, Applicatio n to SCCOA French Air Defense Program. In Complex Systems Design&Management , pages 29–40. Springer, 2017
2017
-
[37]
Pulido and C
G. Pulido and C. Coello. Using clustering techniques to improve the performance of a multi-objective particle swarm optimizer. In Genetic and Evolutionary Computation Conference, pages 225–237. Springer, 2004
2004
-
[38]
Ramirez-Atencia, S
C. Ramirez-Atencia, S. Mostaghim, and D. Camacho. A kne e point based evolutionary multi-objective optimization for mission planning proble ms. In Proceedings of the Genetic and Evolutionary Computation Conference , pages 1216–1223. ACM, 2017
2017
-
[39]
Kubushishi
J-P Rasson and T. Kubushishi. The gap test: an optimal me thod for determining the number of natural classes in cluster analysis. In New approaches in classification and data analysis , pages 186–193. Springer, 1994
1994
-
[40]
Samorani, Y
M. Samorani, Y. W ang, Z. Lv, and F. Glover. Clustering-d riven evolutionary algorithms: an application of path relinking to the quadratic unconstra ined binary optimization prob- lem. Journal of Heuristics , pages 1–14, 2018
2018
-
[41]
S. Sayın. Measuring the quality of discrete representa tions of efficient sets in multiple objective mathematical programming. Mathematical Programming, 87(3):543–560, 2000
2000
-
[42]
M. Sharir. A near-linear algorithm for the planar 2-cen ter problem. Discrete & Compu- tational Geometry , 18(2):125–134, 1997
1997
-
[43]
Sintorn and U
E. Sintorn and U. Assarsson. Fast parallel GPU-sorting using a hybrid algorithm. Journal of Parallel and Distributed Computing , 68(10):1381–1388, 2008
2008
-
[44]
E. Talbi. Metaheuristics: from design to implementation , volume 74. Wiley, 2009
2009
-
[45]
W ang and M
H. W ang and M. Song. Ckmeans. 1d. dp: optimal k-means clu stering in one dimension by dynamic programming. The R journal , 3(2):29, 2011
2011
-
[46]
Zio and R
E. Zio and R. Bazzo. A clustering procedure for reducing the number of representative solutions in the pareto front of multiobjective optimizati on problems. European Journal of Operational Research, 210(3):624–634, 2011. 18 Appendix A: Proof of the intermediate lemmas This se...
2011
-
[47]
□ Lemma 10
Having for a given k, i′ k ⩽ ik, ik−1 ⩽ i′ k−1 is implied by lemma 2 and d(zik , z ik−1−1) > OP T . □ Lemma 10. Let P ⊂ E such that card (P ) /greaterorequalslant2. Let i (resp j) the minimal 20 (resp maximal) index of points of P . We have the following results: ∀x∈ R2− { xi ...
Reviewed August 14, 2026 · model on record in the stance chip above.
Discussion (0). Continue with ORCID to comment.