{"id":"d16e2255-ee86-4b43-b4d4-896a7a2fc5a9","arxiv_id":"1908.09648","paper_version":1,"verdict":"CONDITIONAL","confidence":"MODERATE","novelty_score":5.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":0,"one_line_summary":"For points forming a 2D Pareto front, discrete and continuous K-center clustering are solvable in near-linear O(KN polylog N) time and O(N) memory via dynamic programming over sorted intervals.","lead":"This paper proves that p-center clustering of a two-dimensional Pareto front can be solved exactly in polynomial time, with O(KN log N) time for continuous centers and O(KN log^2 N) for discrete centers. The algorithms use dynamic programming over sorted non-dominated points and matter for archiving and summarizing large Pareto fronts in multi-objective optimization.","discovery_kind":"new_method","skeptic_critique":{"model":"deepseek-v4-flash","headline":"Proposition 3's proof uses a false containment: C'_K is a superset of C_K, so the bound f(C'_K) <= OPT is unproven; the interval-DP optimality in Theorem 1 rests on this step.","rationale":"The reader's weakest-assumption analysis identifies exactly the load-bearing flaw: the induction step of Proposition 3 contains a false containment for the suffix cluster C'_K. I checked the manuscript text and the error is plain: C'_K is a superset of C_K, not a subset, so Lemma 5 gives the opposite inequality and the bound f(C'_K) <= OPT does not follow. Since the DP in Section 5 optimizes only over interval clusters, the entire polynomial-time optimality claim rests on this proposition. This is an internal gap in the argument, not a disagreement with external consensus. The theorem may still be true: Lemmas 2-4 and an exchange/interval-covering argument suggest a plausible repair, but the manuscript does not provide it, and no code or machine-checked proof independently confirms the DP. Therefore the reader's CONDITIONAL verdict remains appropriate; my stress-test does not move the verdict.","tokens_in":17742,"tokens_out":10046,"duration_ms":114412,"concrete_test":"Enumerate all Pareto fronts of size N <= 8 with integer coordinates (e.g., all strictly decreasing sequences in a small grid), and for each, K = 2..4, compute (a) the true optimum over all set partitions for f^C and f^D and (b) the interval-only DP optimum from Algorithm 2. If any instance has (a) < (b), Proposition 3 is false and Theorem 1 fails. If no instance differs over the full enumeration, the concern is a proof gap rather than a false theorem, and Proposition 3 should be re-proved with the interval-covering construction replacing the faulty containment step.","verdict_should_be":"UNCHANGED","load_bearing_attack":"In Proposition 3 (Section 4.3), the induction step takes an optimal partition C_1,...,C_K of K-γ-CP2dPF, with C_K the cluster containing x_N and i the smallest index in C_K. It defines C'_K = {x_j : i <= j <= N} and C'_k = C_k ∩ {x_j : j < i} for k < K, then asserts 'for all k, C'_k ⊂ C_k', concluding f_γ(C'_k) <= f_γ(C_k) <= OPT. The assertion is true only for k < K. For k = K, C'_K contains every Pareto point from i to N, so in general C_K ⊂ C'_K rather than the reverse; Lemma 5 then gives f_γ(C'_K) >= f_γ(C_K), and the needed inequality f_γ(C'_K) <= OPT is not established. Because the DP in Section 5 (Equation (18)) restricts attention to interval clusters C_{j,i}, the optimality of the DP is exactly Proposition 3. Thus the central claim is not supported by the proof as written. The interval property may be recoverable by an interval-covering exchange argument (the cluster cost formulas in Lemmas 3 and 4 depend mainly on the extreme indices), but no such argument is supplied.","agreement_with_reader":"agree"},"referee_report":{"model":"deepseek-v4-flash","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'}.","tokens_in":18012,"tokens_out":6426,"duration_ms":63739,"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":[{"comment":"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":"Section 4.3, Proposition 3"},{"comment":"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.","section":"Section 6.2"}],"minor_comments":[{"comment":"The text writes \"f_gamma(C'_k) ⊂ f_gamma(C_k)\"; the subset symbol should be the inequality \"<=\".","section":"Section 4.3, Proposition 3 proof"},{"comment":"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.","section":"Section 5.2, Proposition 5"},{"comment":"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.","section":"Algorithm 1 (Section 4.4)"},{"comment":"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.","section":"Algorithm 4 (Section 5.3)"},{"comment":"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.","section":"Appendix A, Lemma 10 proof"},{"comment":"The proof refers to \"Proposition 2\" when it means \"Lemma 2\" (the monotonic distance lemma).","section":"Appendix A, Lemma 6 proof"}],"recommendation":"major_revision","confidential_remarks":"The main result is appealing, but the proof of Proposition 3 is not merely incomplete: it relies on a false set inclusion. The authors need to either supply a correct proof of the interval property or present a counterexample. The novelty split with the authors' earlier work [16] is also not entirely clear; the manuscript cites its own prior papers for closely related results (p-median and p-center on 2D Pareto fronts), and the present contribution would be stronger if the differences were articulated more explicitly."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"Two things to know. First, the paper does something real: it gives a unified DP for continuous and discrete K-center on a 2D Pareto front and claims O(KN log N) / O(KN log^2 N) time and O(N) space, improving the authors' earlier polynomial-time result. The geometric observations — that distances obey a Monge-like monotonicity and the 1-center cost depends only on extreme indices — are genuinely useful and make the DP line-computation idea credible.\n\nSecond, the key structural lemma, Proposition 3, is not proved as written. The induction step defines C'_K as the suffix from the smallest index in the old last cluster to N. This is a superset of the old C_K, not a subset, so the monotonicity Lemma 5 cannot give f(C'_K) ≤ OPT. The text says \"C'_k ⊂ C_k\" for all k, which is false for k = K. The interval-optimality of the DP in Equation (18) rests entirely on this proposition. The result may be salvageable — the cost formulas in Lemmas 3 and 4 depend mainly on the extreme indices, so an exchange argument can probably push interior points into a neighboring cluster — but that argument is not in the paper. Without it, the central claim is unsupported.\n\nThere are also smaller issues: Algorithm 1 has a typo in the dichotomic midpoint (i+i' over 2, where i' is not defined in scope), and the proof of Lemma 8 is only a sketch. The citation pattern is heavy on the authors' own prior work, but the earlier results are clearly cited and the new complexity bounds are not claimed elsewhere. I don't see invented entities or fitted free parameters.\n\nBottom line: this is a serious paper with a real algorithmic idea, currently held together by an unproven interval property. I would send it to a good computational geometry referee, but the revision must supply a correct proof of Proposition 3 or an explicit counterexample. If the property turns out to be false, the whole DP collapses. If it is true, the paper is a solid contribution to multi-objective optimization practice.\n\nMy vote: bring it to reading group as a cautionary example, don't cite it until the proof is fixed, and accept only conditional on the repair. It deserves a full referee round, not a desk reject.","headline":"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.","tokens_in":18519,"tokens_out":1889,"would_cite":false,"duration_ms":20009,"reading_group":"maybe","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":["68U05","90C27","90C39"],"pacs":[],"model":"deepseek-v4-flash","headline":"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.","keywords":["Pareto front","K-center problem","p-center problem","dynamic programming","computational geometry","bi-objective optimization","clustering","polynomial-time algorithm"],"falsifier":"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.","tokens_in":17568,"feed_emoji":"🎯","tokens_out":12185,"duration_ms":130912,"temperature":0.7,"pith_summary":"This paper claims that the planar K-center clustering problem, which is NP-hard in general, becomes solvable in polynomial time when the input points form a two-dimensional Pareto front: a set of pairwise incomparable points in the plane, such as the nondominated solutions of a bi-objective optimization problem. The paper argues that after sorting the front by one objective, an optimal clustering can be assumed to cut the front into contiguous index blocks, and that each block's covering radius is then easy to evaluate. This yields a dynamic programming algorithm running in $O(KN\\log N)$ time and $O(N)$ memory for the continuous K-center problem, and in $O(KN\\log^2 N)$ time for the discrete K-center problem when $K\\ge 3$, with the discrete 2-center case in $O(N\\log N)$. A sympathetic reader will care because bi-objective solvers routinely output huge fronts, and a fast exact clustering method turns such a front into a small set of representative balls for decision making.","feed_headline":"K-center clustering on a Pareto front runs in polynomial time","feed_subtitle":"A dynamic program cuts the front into contiguous blocks, taming an NP-hard planar problem.","key_machinery":"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.","core_discovery":"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.","pith_inferences":["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."],"forward_implications":["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."],"supporting_citations":[{"why":"Shows that the planar Euclidean discrete p-center problem is NP-hard in general, the hardness result that the Pareto-front restriction is claimed to bypass.","marker":"[33]"},{"why":"Supplies the linear-time minimum enclosing ball algorithm for the continuous 1-center problem that the paper's O(N) result improves with a simpler scan.","marker":"[32]"},{"why":"Gives the O(NK log N)-time, O(N)-space algorithm for k-centers with centers on a line, the affine-front special case that the interval DP generalizes to curved fronts.","marker":"[29]"},{"why":"Presents line-constrained k-center algorithms and furthest-neighbor Voronoi diagrams used as prior art for discrete 1-center and comparison baselines.","marker":"[4]"},{"why":"Earlier polynomial dynamic program for p-median and p-center clustering on a 2D Pareto front, the direct predecessor whose interval-clustering idea this paper refines and accelerates.","marker":"[16]"}],"fun_headline_variants":["Pareto-front clustering: K-center is polynomial-time solvable","Planar K-center on Pareto fronts goes polynomial-time","Polynomial time for K-center on a Pareto front","K-center clustering of Pareto front is polynomial","Pareto-front K-center: polynomial-time DP algorithm"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"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.","fun_headline_variants_meta":{"raw":{"variants":["Pareto-front clustering: K-center is polynomial-time solvable","Planar K-center on Pareto fronts goes polynomial-time","Polynomial time for K-center on a Pareto front","K-center clustering of Pareto front is polynomial","Pareto-front K-center: polynomial-time DP algorithm"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.0007,"raw_usage":{"total_tokens":3163,"prompt_tokens":952,"completion_tokens":2211,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":568,"completion_tokens_details":{"reasoning_tokens":2133}},"tokens_in":568,"tokens_out":2211,"duration_ms":17304,"temperature":1.0,"reasoning_tokens":2133,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-14T12:29:07.138082+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"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.","supporting_citations":[{"cited_title":"Megiddo and K","cited_arxiv_id":null,"evidence_quote":"Shows that the planar Euclidean discrete p-center problem is NP-hard in general, the hardness result that the Pareto-front restriction is claimed to bypass."},{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"Supplies the linear-time minimum enclosing ball algorithm for the continuous 1-center problem that the paper's O(N) result improves with a simpler scan."},{"cited_title":"Karmakar, S","cited_arxiv_id":null,"evidence_quote":"Gives the O(NK log N)-time, O(N)-space algorithm for k-centers with centers on a line, the affine-front special case that the interval DP generalizes to curved fronts."},{"cited_title":"Computing k-Centers On a Line","cited_arxiv_id":"0902.3282","evidence_quote":"Presents line-constrained k-center algorithms and furthest-neighbor Voronoi diagrams used as prior art for discrete 1-center and comparison baselines."},{"cited_title":"k-medoids and p-median clustering are solvable in polynomial time for a 2d Pareto front","cited_arxiv_id":"1806.02098","evidence_quote":"Earlier polynomial dynamic program for p-median and p-center clustering on a 2D Pareto front, the direct predecessor whose interval-clustering idea this paper refines and accelerates."}],"review_version":1}