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

• URL: http://arxiv.org/abs/2606.26591v1
• Date: Thu, 25 Jun 2026 04:25:20 GMT
• Title: Three-Objective Integral R2 Subset Selection: NP-Hardness and Submodular Approximation
• Abstract summary: This paper studies the problem for the integral R2 indicator in three objectives.<n>We show that the integral R2 improvement with respect to any fixed baseline is a monotone submodular set function.<n>We also give a tested greedy implementation that evaluates exact integral R2 values by subdivision.
• Score: 0.0
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• 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.

Related papers

• Computing the Integral R2 Indicator by Perspective Mapping and Box Decomposition [0.0]
  This work introduces a bidirectional perspective mapping between continuous integral R2 computation and integration over unions of anchored axis-aligned boxes.<n>Hypervolume algorithms that emit box decompositions can be reused by replacing ordinary box volumes with closed-form weighted box integrals.
  arXiv  Detail & Related papers  (2026-06-29T16:34:01Z)
• Solve for the Hyperparameter, Skip the Search: Kolmogorov-Optimal Scaling Laws for Spline Regression [0.0]
  Optimal resolution can be solved for in closed form, to the accuracy an exhaustive search reaches, at a fraction of the compute.<n>KORE fits two pilot resolutions, solves a leverage-calibrated 2x2 system for the bias and noise scales, and evaluates the closed-form plug-in resolution with a tiny leave-one-out certificate.
  arXiv  Detail & Related papers  (2026-06-22T16:41:10Z)
• Distributionally Robust Multi-Objective Optimization [47.16280600850848]
  We introduce distributionally robust multi-objective optimization (DRMOO)<n>We propose a double-loop MGDA that uses an inner loop to estimate dual variables and achieves a total sample complexity $mathcalO(-12)$ for reaching an $$-Pareto-stationary point.<n>To further improve efficiency, we handle generalized-smooth biased estimates, removing the need for double sampling.
  arXiv  Detail & Related papers  (2026-05-07T04:24:17Z)
• DC-Reg: Globally Optimal Point Cloud Registration via Tight Bounding with Difference of Convex Programming [43.06401929828342]
  We develop a new framework to achieve globally optimal point registration interplay.<n>We show that it achieves significantly faster convergence to extreme noise and the outlier-of-the-art global to extreme noise.
  arXiv  Detail & Related papers  (2026-03-26T13:38:45Z)
• An Information-Minimal Geometry for Qubit-Efficient Optimization [0.0]
  We recast qubit-efficient optimization as a geometry problem.<n>Local-consistency problem coincides exactly with the Sherali-Adams level-2 polytope $mathrmSA(2)$.
  arXiv  Detail & Related papers  (2025-11-11T15:38:57Z)
• Obtaining Lower Query Complexities through Lightweight Zeroth-Order Proximal Gradient Algorithms [65.42376001308064]
  We propose two variance reduced ZO estimators for complex gradient problems. We improve the state-of-the-art function complexities from $mathcalOleft(minfracdn1/2epsilon2, fracdepsilon3right)$ to $tildecalOleft(fracdepsilon2right)$.
  arXiv  Detail & Related papers  (2024-10-03T15:04:01Z)
• Decomposed Global Optimization for Robust Point Matching with Low-Dimensional Branching [41.05165517541873]
  We introduce a novel global optimization method for align partially overlapping point sets.<n>Our method exhibits superior robustness to non-rigid deformations, positional noise and outliers.<n> Experiments on 2D and 3D synthetic and real-world data demonstrate that our method, compared to state-of-the-art approaches, exhibits superior robustness to outliers.
  arXiv  Detail & Related papers  (2024-05-14T13:28:57Z)
• Polynomial-Time Solutions for ReLU Network Training: A Complexity Classification via Max-Cut and Zonotopes [70.52097560486683]
  We prove that the hardness of approximation of ReLU networks not only mirrors the complexity of the Max-Cut problem but also, in certain special cases, exactly corresponds to it. In particular, when $epsilonleqsqrt84/83-1approx 0.006$, we show that it is NP-hard to find an approximate global dataset of the ReLU network objective with relative error $epsilon$ with respect to the objective value.
  arXiv  Detail & Related papers  (2023-11-18T04:41:07Z)
• Gradient-Free Methods for Deterministic and Stochastic Nonsmooth Nonconvex Optimization [94.19177623349947]
  Non-smooth non optimization problems emerge in machine learning and business making. Two core challenges impede the development of efficient methods with finitetime convergence guarantee. Two-phase versions of GFM and SGFM are also proposed and proven to achieve improved large-deviation results.
  arXiv  Detail & Related papers  (2022-09-12T06:53:24Z)
• Hybrid Trilinear and Bilinear Programming for Aligning Partially Overlapping Point Sets [85.71360365315128]
  In many applications, we need algorithms which can align partially overlapping point sets are invariant to the corresponding corresponding RPM algorithm. We first show that the objective is a cubic bound function. We then utilize the convex envelopes of trilinear and bilinear monomial transformations to derive its lower bound. We next develop a branch-and-bound (BnB) algorithm which only branches over the transformation variables and runs efficiently.
  arXiv  Detail & Related papers  (2021-01-19T04:24:23Z)
• Canny-VO: Visual Odometry with RGB-D Cameras based on Geometric 3D-2D Edge Alignment [85.32080531133799]
  This paper reviews the classical problem of free-form curve registration and applies it to an efficient RGBD visual odometry system called Canny-VO. Two replacements for the distance transformation commonly used in edge registration are proposed: Approximate Nearest Neighbour Fields and Oriented Nearest Neighbour Fields. 3D2D edge alignment benefits from these alternative formulations in terms of both efficiency and accuracy.
  arXiv  Detail & Related papers  (2020-12-15T11:42:17Z)
• Robust 6D Object Pose Estimation by Learning RGB-D Features [59.580366107770764]
  We propose a novel discrete-continuous formulation for rotation regression to resolve this local-optimum problem. We uniformly sample rotation anchors in SO(3), and predict a constrained deviation from each anchor to the target, as well as uncertainty scores for selecting the best prediction. Experiments on two benchmarks: LINEMOD and YCB-Video, show that the proposed method outperforms state-of-the-art approaches.
  arXiv  Detail & Related papers  (2020-02-29T06:24:55Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.