Pith. sign in

REVIEW 1 major objections 3 cited by

Integral R2 improvement is monotone submodular, yielding a (1-1/e) greedy guarantee, while exact fixed-cardinality selection is NP-hard in three objectives.

Reviewed by Pith at T0; open to challenge. T0 means a machine referee read the full paper against a public rubric. the ladder, T0–T4 →

Challenge this review Re-run · record.json Download PDF Read on arXiv ↗

T0 review · grok-4.3

2026-06-26 03:53 UTC pith:OLEJSUAJ

load-bearing objection The paper proves NP-hardness for exact 3-objective integral R2 subset selection via an anchored-box reduction and shows the improvement function is monotone submodular for a (1-1/e) greedy guarantee. the 1 major comments →

arxiv 2606.26591 v1 pith:OLEJSUAJ submitted 2026-06-25 math.OC cs.CGcs.NE

Three-Objective Integral R2 Subset Selection: NP-Hardness and Submodular Approximation

Michael T. M. Emmerich This is my paper
classification math.OC cs.CGcs.NE
keywords multiobjective optimizationR2 indicatorsubset selectionsubmodular functionNP-hardnessgreedy algorithmPareto frontTchebycheff scalarization
verification ladder T0 review T1 audit T2 compute T3 formal T4 reserved

The pith

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The paper establishes that the gain in integral R2 when adding a point to an existing set is a monotone submodular function for any fixed baseline. This property directly implies that greedy selection recovers at least a (1-1/e) fraction of the largest possible R2 improvement achievable with k points. The authors simultaneously prove that computing the exact optimal k-point subset is NP-hard when the number of objectives reaches three. These two results together separate the tractable two-objective case from the three-objective case and identify submodular optimization as a principled route to approximation.

Core claim

The integral R2 improvement with respect to any fixed baseline is a monotone submodular set function. For the usual ideal-point based R2 indicator this yields a direct gap-reduction guarantee: greedy selection closes at least a (1-1/e)-fraction of the maximum possible R2 gap between a fixed dominated anchor value and the best cardinality-k value. Exact fixed-cardinality subset selection is NP-hard already in three objectives. The hardness proof uses a perspective transformation that maps Tchebycheff-shadow improvements to a weighted anchored-box union problem with density (x1+x2+x3)^{-4}.

What carries the argument

The integral R2 indicator, defined as the integral over the two-dimensional weight simplex of the lower envelope of weighted Tchebycheff scalarizations.

Load-bearing premise

The R2 improvement function remains monotone submodular under the specific integral definition over the weight simplex, and the hardness reduction preserves optimality when mapping Tchebycheff-shadow improvements to the anchored-box union problem.

What would settle it

A concrete collection of points where the marginal integral R2 gain of adding one more point increases with set size, or a polynomial-time algorithm that solves exact fixed-cardinality three-objective R2 selection.

Watch this falsifier — get emailed when new claim-graph text bears on it.

If this is right

  • Greedy selection recovers at least (1-1/e) of the maximum R2 gap reduction for any fixed baseline.
  • Exact optimal k-point selection requires super-polynomial time in the worst case once three objectives are present.
  • The submodularity property applies to any fixed baseline, not only the ideal point.
  • Exact R2 values can be computed by subdivision with O(n^6) worst-case time per evaluation.

Where Pith is reading between the lines

These are editorial extensions of the paper, not claims the author makes directly.

  • The hardness separation suggests that specialized algorithms may remain feasible only for two objectives while higher dimensions require approximation.
  • Other scalarization-based indicators might inherit submodularity if they admit an analogous integral representation.
  • The greedy method could be hybridized with local search to improve practical performance on real Pareto-front data.
  • The perspective transformation used in the reduction may apply to proving hardness for related volume-based or hypervolume indicators.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit.

Referee Report

1 major / 0 minor

Summary. The paper claims that the integral R2 improvement (w.r.t. any fixed baseline) is a monotone submodular set function on three-objective Pareto-front approximations, yielding a (1-1/e) greedy gap-reduction guarantee for the ideal-point R2 indicator; it also claims that exact fixed-cardinality subset selection is NP-hard in three objectives via a perspective transformation reducing from the Bringmann-Cabello-Emmerich anchored-box problem with density (x1+x2+x3)^{-4}. A practical greedy implementation with O(n^6) exact integral evaluation is provided.

Significance. If the claims hold, the work cleanly separates the polynomial-time two-objective case from the three-objective case while supplying a principled submodular-optimization route to approximation; the submodularity result is parameter-free and rests on standard set-function theory, and the explicit O(n^6) implementation strengthens the positive side.

major comments (1)
  1. [Abstract / hardness reduction] Abstract and hardness-proof outline: the claim that the perspective transformation maps Tchebycheff-shadow improvements onto weighted anchored-box union volumes with density (x1+x2+x3)^{-4} while preserving optimality (i.e., argmax subsets) is load-bearing for the NP-hardness result. The provided sketch does not explicitly derive that this density is exactly the measure induced by integrating the R2 improvement over the two-dimensional weight simplex, nor does it rule out ordering discrepancies under the transformation; without this verification the reduction from the three-dimensional anchored-box problem does not yet establish hardness for integral R2.

Simulated Author's Rebuttal

1 responses · 0 unresolved

We thank the referee for the careful reading and for highlighting the need for greater explicitness in the hardness reduction. We address the comment below and will revise the manuscript to strengthen the presentation of the proof.

read point-by-point responses

  1. Referee: [Abstract / hardness reduction] Abstract and hardness-proof outline: the claim that the perspective transformation maps Tchebycheff-shadow improvements onto weighted anchored-box union volumes with density (x1+x2+x3)^{-4} while preserving optimality (i.e., argmax subsets) is load-bearing for the NP-hardness result. The provided sketch does not explicitly derive that this density is exactly the measure induced by integrating the R2 improvement over the two-dimensional weight simplex, nor does it rule out ordering discrepancies under the transformation; without this verification the reduction from the three-dimensional anchored-box problem does not yet establish hardness for integral R2.

    Authors: We agree that the current sketch is concise and would benefit from an explicit derivation. The perspective transformation is constructed so that the integral of the R2 improvement (over the weight simplex) equals the integral of the indicator function of the union of anchored boxes with respect to the measure whose density is exactly (x1+x2+x3)^{-4}; this follows by a direct change-of-variables computation in which the Jacobian of the perspective map produces the stated density factor. Because the map is continuous and strictly monotone in each coordinate, the argmax subsets are preserved. In the revision we will insert the full change-of-variables calculation and the monotonicity argument immediately after the statement of the transformation, making the reduction self-contained. revision: yes

Circularity Check

0 steps flagged

No circularity: submodularity proven from integral definition; hardness via explicit reduction adapting external base construction

full rationale

The derivation is self-contained. Submodularity of the integral R2 improvement is asserted as a property of the set function defined by integration of the Tchebycheff lower envelope over the weight simplex; this is a claim to be proven from the definition rather than assumed by renaming or self-reference. The (1-1/e) guarantee follows directly from the standard greedy theorem for monotone submodular functions, an external result. NP-hardness is obtained by exhibiting a perspective transformation that maps the problem to a weighted anchored-box union instance with the stated density and then invoking the prior anchored-box construction; the paper supplies the mapping step rather than reducing the claim solely to the citation. No fitted parameters are relabeled as predictions, no ansatz is smuggled, and no uniqueness theorem is imported from overlapping-author prior work to forbid alternatives. The self-citation supplies only the base hardness instance, which remains independently verifiable.

Axiom & Free-Parameter Ledger

0 free parameters · 2 axioms · 0 invented entities

The paper relies on standard definitions of monotonicity and submodularity from combinatorial optimization and on the correctness of a geometric reduction from a known NP-hard problem; no free parameters, new entities, or ad-hoc axioms are introduced.

axioms (2)
  • standard math A set function is monotone submodular if marginal gains diminish and adding an element never decreases the value.
    Invoked to apply the standard (1-1/e) greedy guarantee.
  • domain assumption The integral R2 indicator is defined as the integral of the lower envelope of weighted Tchebycheff scalarizations over the weight simplex.
    Core definition required for both the submodularity claim and the hardness reduction.

pith-pipeline@v0.9.1-grok · 5811 in / 1413 out tokens · 53821 ms · 2026-06-26T03:53:09.532546+00:00 · methodology

0 comments
read the original abstract

Selecting a fixed number of representative points from a finite Pareto-front approximation is a fundamental post-processing task in multiobjective optimization. This paper studies this problem for the integral R2 indicator in three objectives, where the indicator is defined as the integral of the lower envelope of weighted Tchebycheff scalarizations over the two-dimensional weight simplex. We provide two complementary algorithmic results. On the positive side, we show that the integral R2 improvement with respect to any fixed baseline is a monotone submodular set function. For the usual ideal-point based R2 indicator, with the ideal point fixed, this yields a direct gap-reduction guarantee: greedy selection closes at least a $(1-1/e)$-fraction of the maximum possible R2 gap between a fixed dominated anchor value and the best cardinality-$k$ value. We also give a tested greedy implementation that evaluates exact integral R2 values by subdivision, with worst-case running time $O(n^6)$. On the negative side, we prove that exact fixed-cardinality subset selection is NP-hard already in three objectives. The hardness proof uses a perspective transformation that maps Tchebycheff-shadow improvements to a weighted anchored-box union problem with density $(x_1+x_2+x_3)^{-4}$, and then adapts the three-dimensional anchored-box construction of Bringmann, Cabello, and Emmerich. Together, these results separate the tractable two-objective case from the three-objective case while identifying a principled approximation route based on submodular optimization.

Figures

Figures reproduced from arXiv: 2606.26591 by Michael T. M. Emmerich.

Figure 1
Figure 1. Figure 1: Tchebycheff-shadow interpretation of the integral [PITH_FULL_IMAGE:figures/full_fig_p003_1.png] view at source ↗
Figure 2
Figure 2. Figure 2: Greedy selection is meaningful in any dimension once integral [PITH_FULL_IMAGE:figures/full_fig_p009_2.png] view at source ↗
Figure 3
Figure 3. Figure 3: The perspective transformation converts Tchebycheff-shadow improvement [PITH_FULL_IMAGE:figures/full_fig_p011_3.png] view at source ↗
Figure 4
Figure 4. Figure 4: The common triangular-grid gadget in the two coordinate systems used by [PITH_FULL_IMAGE:figures/full_fig_p012_4.png] view at source ↗
Figure 5
Figure 5. Figure 5: A small induced-subgraph example for the hardness reduction, in the spirit [PITH_FULL_IMAGE:figures/full_fig_p013_5.png] view at source ↗

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.

Forward citations

Cited by 3 Pith papers

Reviewed papers in the Pith corpus that reference this work. Sorted by Pith novelty score.

  1. Computing the Integral R2 Indicator by Perspective Mapping and Box Decomposition

    cs.CG 2026-06 unverdicted novelty 7.0

    A bidirectional perspective mapping reduces integral R2 computation to weighted hypervolume differences, enabling box-decomposition algorithms to compute it in O(n log n) time for N=2,3 objectives.

  2. Computing the Integral R2 Indicator by Perspective Mapping and Box Decomposition

    cs.CG 2026-06 unverdicted novelty 7.0

    A bidirectional perspective mapping equates integral R2 computation to weighted hypervolume differences over anchored box decompositions, yielding output-sensitive algorithms with stated time complexities for fixed nu...

  3. Computing the Integral R2 Indicator by Perspective Mapping and Box Decomposition

    cs.CG 2026-06 unverdicted novelty 7.0

    A bidirectional perspective mapping reduces integral R2 computation to weighted hypervolume differences over box decompositions, enabling reuse of existing algorithms with output-sensitive overhead O(2^N M) and specif...

Reference graph

Works this paper leans on

11 extracted references · 4 canonical work pages · cited by 1 Pith paper · 3 internal anchors

  1. [1]

    M. T. M. Emmerich. Fast and exact biobjective subset selection for the integralR2 indicator. arXiv preprint arXiv:2606.23365, 2026

    work page internal anchor Pith review Pith/arXiv arXiv 2026

  2. [2]

    M. T. M. Emmerich. Preference-shaped expected hypervolume andR2 improvement: Exact computation and monotonicity. arXiv preprint arXiv:2605.28746, 2026

    work page internal anchor Pith review Pith/arXiv arXiv 2026

  3. [3]

    R2 v2: The Pareto-compliant R2 indicator for better benchmarking in bi-objective optimization,

    L. Schäpermeier and P. Kerschke, “R2 v2: The Pareto-compliant R2 indicator for better benchmarking in bi-objective optimization,”Evolutionary Computation, pp. 1–17, 2025

    2025

  4. [4]

    Reinvestigating the R2 Indicator: Achieving Pareto Compliance by Integration,

    L. Schäpermeier and P. Kerschke, “Reinvestigating the R2 Indicator: Achieving Pareto Compliance by Integration,” inParallel Problem Solving from Nature – PPSN XVIII, M. Affenzeller, S. M. Winkler, A. V. Kononova, H. Trautmann, T. Tušar, P. Machado, and T. Bäck, Eds., Lecture Notes in Computer Science, vol. 15151, pp. 202–216, 2024

    2024

  5. [5]

    Jaszkiewicz and P

    A. Jaszkiewicz and P. Zielniewicz. Exact calculation and properties of theR2 multiobjective quality indicator.IEEE Transactions on Evolutionary Computation, 29(4):1227–1238, 2025. doi:10.1109/TEVC.2024.3440571

    work page doi:10.1109/tevc.2024.3440571 2025

  6. [6]

    Maximum Volume Subset Selection for Anchored Boxes

    K. Bringmann, S. Cabello, and M. T. M. Emmerich. Maximum volume subset selection for anchored boxes. arXiv preprint arXiv:1803.00849, 2018. Conference version inSoCG 2017

    work page internal anchor Pith review Pith/arXiv arXiv 2018

  7. [7]

    M. R. Garey and D. S. Johnson. The rectilinear Steiner tree problem is NP-complete. SIAM Journal on Applied Mathematics, 32(4):826–834, 1977

    1977

  8. [8]

    J. A. Storer. On minimal-node-cost planar embeddings.Networks, 14(2):181–212, 1984

    1984

  9. [9]

    Tamassia and I

    R. Tamassia and I. G. Tollis. Planar grid embedding in linear time.IEEE Transactions on Circuits and Systems, 36(9):1230–1234, 1989

    1989

  10. [10]

    G. L. Nemhauser, L. A. Wolsey, and M. L. Fisher. An analysis of approximations for maximizing submodular set functions–I.Mathematical Programming, 14:265–294, 1978

    1978

  11. [11]

    U. Feige. A threshold oflnn for approximating set cover.Journal of the ACM, 45(4):634–652, 1998. 24

    1998