{"id":"37052dbe-0440-414d-ba57-968961a14483","arxiv_id":"2606.23365","paper_version":1,"verdict":"CONDITIONAL","confidence":"LOW","novelty_score":7.0,"correctness_risk":"low","formal_verification":"none","parameter_count":0,"one_line_summary":"Exact O(kn) algorithm for fixed-cardinality subset selection under the continuous integral bi-objective R2 indicator via adjacent-neighbor decomposition and Monge matrix search.","lead":"The paper derives an exact dynamic programming decomposition for selecting k points from a sorted bi-objective Pareto front to maximize the continuous integral R2 indicator, then proves the transition costs form a Monge matrix to obtain O(kn) time via matrix search. Researchers working on indicator-based multi-objective optimization may use these algorithms for exact subset selection without sampling weights.","discovery_kind":"new_method","skeptic_critique":{"model":"grok-4.3","headline":"No significant objection identified","rationale":"The reader's weakest assumption directly identifies the single-crossing step that underpins the Monge property and the O(kn) claim. Because the paper supplies an explicit proof sketch, consistency checks, and reproducible code, the argument is internally coherent; the low confidence stems only from the abstract-only review, not from any visible flaw.","tokens_in":1776,"tokens_out":262,"duration_ms":12109,"concrete_test":"Run the provided reproducible Python code on the exhaustive-enumeration test instances; confirm that the matrix-search output matches the O(kn^2) DP output to machine precision on all k-subsets for n ≤ 20.","verdict_should_be":"UNCHANGED","load_bearing_attack":"No load-bearing concern identified. The central claim requires the transition matrix to be Monge, which the paper establishes via a lower-envelope sweep argument on single-crossing transition functions together with the i < j triangular condition. The manuscript states that this holds for the exact continuous integral R2 decomposition, the input is assumed sorted (standard for bi-objective Pareto fronts), and the resulting O(kn) staircase search follows directly. No internal inconsistency is apparent in the DP setup or the claimed properties.","agreement_with_reader":"agree"},"referee_report":{"model":"grok-4.3","summary":"The paper derives an exact adjacent-neighbor decomposition of the continuous integral bi-objective R2 indicator (area under the lower envelope of Tchebycheff scalarizations) into boundary, unary, and transition terms for sorted Pareto fronts. This yields a Bellman DP solvable in O(kn^2) time; the authors then prove the transition matrix is Monge via a lower-envelope sweep argument on single-crossing functions together with the i < j triangular condition, enabling a staircase matrix-search implementation in O(kn) time under constant-time comparisons. Reproducible Python code is supplied that verifies consistency against exhaustive enumeration, the direct DP, and the divide-and-conquer variant.","tokens_in":1869,"tokens_out":381,"duration_ms":18451,"significance":"If the Monge property and single-crossing conditions hold, the work supplies the first exact O(kn) algorithm for continuous integral R2 subset selection, improving on prior quadratic DP approaches while remaining parameter-free and self-contained from the integral definition. The explicit matrix-search proof, the distinction from finite-weight approximations, and the provision of reproducible code with consistency checks are concrete strengths that advance exact methods in indicator-based multi-objective subset selection.","major_comments":[],"minor_comments":[{"comment":"The assumption that input points are already sorted by increasing first objective and decreasing second objective is stated in the abstract and introduction but should be restated explicitly as a precondition in the algorithm descriptions and pseudocode sections.","section":"Algorithms section"},{"comment":"The phrase 'under constant-time arithmetic comparisons' in the abstract and complexity claims could be clarified with a brief remark on the computational model (e.g., real-RAM) to avoid ambiguity for readers outside computational geometry.","section":"Abstract"}],"recommendation":"accept","confidential_remarks":null},"author_rebuttal":{"model":"grok-4.3","summary":"We thank the referee for the positive assessment and recommendation to accept. The summary accurately captures the core technical contributions of the adjacent-neighbor decomposition, the Monge property proof via single-crossing lower envelopes, and the resulting O(kn) matrix-search algorithm.","responses":[],"tokens_in":1339,"tokens_out":70,"duration_ms":5370,"standing_objections":[]},"desk_editor":{"model":"grok-4.3","letter":"The main advance is an exact dynamic program for picking k out of n sorted bi-objective points to maximize the integral R2 indicator (area under the lower envelope of Tchebycheff losses), reduced to O(kn) time once the transition costs are shown to form a Monge matrix. The decomposition into boundary terms, unary corrections, and adjacent-neighbor transitions is straightforward from the integral definition, and the Monge property follows from a lower-envelope argument on single-crossing functions together with the triangular i < j condition. This is distinct from the hypervolume cases in the cited prior work and from finite-weight approximations.\n\nThe paper does the basics right: it stays exact, assumes only the standard sorted Pareto ordering, supplies reproducible Python code with consistency checks across the naive DP, divide-and-conquer, and matrix-search versions, and avoids any fitted parameters. The central claim is internally consistent on the terms given.\n\nThe only soft spot worth noting is that the single-crossing verification is sketched rather than expanded in the abstract, so a referee would want to see the full sweep argument written out; nothing in the outline suggests it fails. No load-bearing gaps appear in the DP setup or the claimed complexity.\n\nThis is for researchers who need exact, fast subset selection under the continuous R2 indicator in two objectives. Anyone already using dynamic programming on two-dimensional indicators will find the Monge shortcut immediately usable. It is worth sending to peer review because the algorithmic improvement is precise, the evidence is self-contained, and the result is reproducible.","headline":"The paper gives a clean O(kn) exact algorithm for continuous integral R2 subset selection by proving the DP transition matrix is Monge.","tokens_in":2357,"tokens_out":385,"would_cite":false,"duration_ms":13656,"reading_group":"maybe","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":[],"pacs":[],"model":"grok-4.3","headline":"The transition matrix for the integral R2 indicator is Monge, enabling exact subset selection in O(kn) time.","keywords":["subset selection","R2 indicator","Monge matrix","dynamic programming","matrix search","bi-objective optimization","Pareto front","integral indicator"],"falsifier":"Running the matrix-search algorithm on a small instance where exhaustive search is feasible and observing a different selected subset or objective value would falsify the correctness claim.","tokens_in":2679,"feed_emoji":"","tokens_out":687,"duration_ms":37884,"temperature":0.7,"pith_summary":"The paper develops exact algorithms for choosing a fixed number of points from a bi-objective Pareto front to maximize the integral R2 indicator, which computes the area under the lower envelope of weighted Tchebycheff losses over all possible weights. It starts with a dynamic programming formulation that runs in quadratic time per selection step and then shows that the cost matrix satisfies the Monge property. This property allows a faster divide-and-conquer approach and ultimately a linear-time matrix search method. A sympathetic reader would care because the integral formulation avoids sampling artifacts from discrete weight vectors and the speed-up makes exact selection practical for larger sets of candidate points.","feed_headline":"Monge property gives O(kn) exact algorithm for integral R2 subset selection","feed_subtitle":"Proof that transition costs form a Monge matrix allows linear-time dynamic programming to select k points maximizing the continuous R2 area.","key_machinery":"The Monge property of the transition matrix, which permits staircase matrix search for the dynamic programming recurrence.","core_discovery":"For a sorted set of n points, an adjacent-neighbor decomposition yields a Bellman dynamic program with O(kn^2) time for selecting k points. The transition matrix is Monge, which the paper proves via a lower-envelope sweep over single-crossing functions together with the triangular feasibility condition i < j. This yields a divide-and-conquer implementation in O(kn log n) time and a staircase matrix-search implementation in O(kn) time under constant-time comparisons. The algorithms compute the exact continuous integral rather than a finite-sample approximation.","pith_inferences":["The same Monge structure might appear in other scalarization-based indicators, allowing similar speed-ups.","This could lead to practical implementations in multi-objective evolutionary algorithms for bi-objective problems.","Extensions to three or more objectives would require generalizing the Monge property or finding analogous structures.","Testing on real-world Pareto fronts could reveal whether the theoretical speed-up translates to observed performance gains."],"forward_implications":["The exact integral R2 can be optimized without discretizing the weight space.","Subset selection for this indicator becomes feasible at larger scales due to the linear time per point.","The approach extends prior dynamic programming work on hypervolume and other indicators to the continuous R2 case.","Consistency checks with exhaustive enumeration are possible for small instances."],"fun_headline_variants":["Monge matrix gives O(kn) exact integral R2 selection","O(kn) matrix-search for exact bi-objective R2 subset selection","Exact R2 subset selection via Monge transitions in linear time","Bellman DP with Monge property for O(kn) integral R2 selection"],"cache_read_input_tokens":2112,"weakest_assumption_plain":"The candidate points must be pre-sorted by increasing first objective and decreasing second objective, and the transition functions must satisfy the single-crossing property with the triangular condition i < j.","fun_headline_variants_meta":{"raw":{"variants":["Monge matrix gives O(kn) exact integral R2 selection","O(kn) matrix-search for exact bi-objective R2 subset selection","Exact R2 subset selection via Monge transitions in linear time","Bellman DP with Monge property for O(kn) integral R2 selection"]},"model":"grok-4.3","cost_usd":0.003982,"raw_usage":{"total_tokens":2005,"prompt_tokens":771,"num_sources_used":0,"completion_tokens":76,"cost_in_usd_ticks":39815500,"prompt_tokens_details":{"text_tokens":771,"audio_tokens":0,"image_tokens":0,"cached_tokens":64},"completion_tokens_details":{"audio_tokens":0,"reasoning_tokens":1158,"accepted_prediction_tokens":0,"rejected_prediction_tokens":0}},"tokens_in":771,"tokens_out":76,"duration_ms":13066,"temperature":1.0,"reasoning_tokens":1158,"cache_read_input_tokens":64,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-06-26T05:59:06.392978+00:00","model_set":{"reader":"grok-4.3"},"falsifier":"Running the matrix-search algorithm on a small instance where exhaustive search is feasible and observing a different selected subset or objective value would falsify the correctness claim.","supporting_citations":[],"review_version":1}