Minimax-Regret Rectangle Selection under Shared Boundaries and Coupled Flux Modes: Time–Space Algorithms, APSP Reductions, and Conservation Boundaries

On the same axis-aligned rectangle family A of an n × n rectilinear grid, changing either (a) the output contract (a full Θ(n⁴) regret map vs. a scalar minimax decision) or (b) the retained physical field dependence (shared-boundary cancellation in signed outward fluxes vs. coupled interior conservation laws) fundamentally transforms both algorithmic tractability and worst-case regret min_{R∈A} max_{z∈Z} max_{S∈A} (q_S(z) − q_R(z)). Whereas explicit pair evaluation costs Θ(n⁸) time across Θ(n⁴) rectangles, we establish a unified algorithmic, reduction, and conservation framework for two uncertainty models and their output/time–space trade-offs. First, under independent signed-face intervals, marginal score boxes ignore same-oriented boundary cancellation and overestimate regret by max{0, 2M − δ} on two overlapping rectangles. Partitioning each coordinate into Allen's 13 interval relations splits all pairs into 169 endpoint-ownership classes, yielding an output-optimal O(n⁴)-time complete regret map (plus an O(n³)-workspace row-streamed variant), a combinatorial O(n³)-time, O(n³)-space masked single-decision selector, and a tight 2-competitive two-stream certification policy with randomized boundary control L_N = 2 − 2N/((N + 1)H_N) → 2. A moat gadget reduces n × n maximum-weight subarray to the unmasked (n + 2) × (n + 2) scalar minimax value with a single uncertain face, transferring any O(N^(3−δ)) value speedup to O(n^(3−δ/10)) weighted directed All-Pairs Shortest Paths (APSP). This exponent implication is not a cubic lower bound: truly subcubic APSP algorithms are now known, and the construction supplies no reverse reduction from general rectangle regret to APSP. Second, inside O(n³) time under forbidden cells, we compress live workspace via √n checkpointing to O(n^(5/2)) words, via a shared suffix normal form, separable mask penalties, and tiled Chan–Williams distance products to O(n²√log(n + 1)) cells, and to O(n²) space through one internal transverse horizontal uncertain line (26 recipes). Third, a mathematical conservation dichotomy proves that steady fixed-source and nonnegative-balance ensembles collapse to zero regret whereas an insulated 2 × 2 transient diffusion system escapes collapse (Reg = 4 < 5) with strict residual-envelope looseness on 7/9 rectangles; we give exact O(n³ log(n + 1)) (k = 1), CDQ-free O(n³ log²(n + 1)) (k = 2), and sub-quartic O(2^k n³ log^(2^k−1)(n + 1)) (fixed k ≥ 3) coupled-mode solvers, O(n⁶) residual brackets, and three interface observability audits with boundary controls.

Authors

Publication Details

Journal
Zenodo (CERN European Organization for Nuclear Research)
Published
2026-11-16
DOI
https://doi.org/10.5281/zenodo.24264759
Primary Topic
Complexity and Algorithms in Graphs
Type
preprint
Controls
|||
ALL TIME
JAN
FEB
MAR
APR
MAY
JUN
JUL
AUG
SEP
OCT
NOV
preprint

Minimax-Regret Rectangle Selection under Shared Boundaries and Coupled Flux Modes: Time–Space Algorithms, APSP Reductions, and Conservation Boundaries

Xu Cao, Wenxuan Xiao
Zenodo (CERN European Organization for Nuclear Research)
Complexity and Algorithms in Graphs
preprint

Minimax-Regret Rectangle Selection under Shared Boundaries and Coupled Flux Modes: Time–Space Algorithms, APSP Reductions, and Conservation Boundaries

Xu Cao, Wenxuan Xiao
preprint en

Abstract

On the same axis-aligned rectangle family A of an n × n rectilinear grid, changing either (a) the output contract (a full Θ(n⁴) regret map vs. a scalar minimax decision) or (b) the retained physical field dependence (shared-boundary cancellation in signed outward fluxes vs. coupled interior conservation laws) fundamentally transforms both algorithmic tractability and worst-case regret min_{R∈A} max_{z∈Z} max_{S∈A} (q_S(z) − q_R(z)). Whereas explicit pair evaluation costs Θ(n⁸) time across Θ(n⁴) rectangles, we establish a unified algorithmic, reduction, and conservation framework for two uncertainty models and their output/time–space trade-offs. First, under independent signed-face intervals, marginal score boxes ignore same-oriented boundary cancellation and overestimate regret by max{0, 2M − δ} on two overlapping rectangles. Partitioning each coordinate into Allen's 13 interval relations splits all pairs into 169 endpoint-ownership classes, yielding an output-optimal O(n⁴)-time complete regret map (plus an O(n³)-workspace row-streamed variant), a combinatorial O(n³)-time, O(n³)-space masked single-decision selector, and a tight 2-competitive two-stream certification policy with randomized boundary control L_N = 2 − 2N/((N + 1)H_N) → 2. A moat gadget reduces n × n maximum-weight subarray to the unmasked (n + 2) × (n + 2) scalar minimax value with a single uncertain face, transferring any O(N^(3−δ)) value speedup to O(n^(3−δ/10)) weighted directed All-Pairs Shortest Paths (APSP). This exponent implication is not a cubic lower bound: truly subcubic APSP algorithms are now known, and the construction supplies no reverse reduction from general rectangle regret to APSP. Second, inside O(n³) time under forbidden cells, we compress live workspace via √n checkpointing to O(n^(5/2)) words, via a shared suffix normal form, separable mask penalties, and tiled Chan–Williams distance products to O(n²√log(n + 1)) cells, and to O(n²) space through one internal transverse horizontal uncertain line (26 recipes). Third, a mathematical conservation dichotomy proves that steady fixed-source and nonnegative-balance ensembles collapse to zero regret whereas an insulated 2 × 2 transient diffusion system escapes collapse (Reg = 4 < 5) with strict residual-envelope looseness on 7/9 rectangles; we give exact O(n³ log(n + 1)) (k = 1), CDQ-free O(n³ log²(n + 1)) (k = 2), and sub-quartic O(2^k n³ log^(2^k−1)(n + 1)) (fixed k ≥ 3) coupled-mode solvers, O(n⁶) residual brackets, and three interface observability audits with boundary controls.

Zenodo (CERN European Organization for Nuclear Research)
Complexity and Algorithms in Graphs
AI Navigator

Ask Laika to Summarize, Analyze, and Connect papers live on the map.

Summarize Papers & Methodologies

Extract key findings, datasets, and comparative methods across publications.

Benchmark Rankings & Visual Analytics

Rank top research institutions, authors, funders, topics, and journals by Field-Weighted Citation Impact (FWCI) and paper volume with instant charts.

Connect Distant Disciplines

Bridge topological clusters on the map to find hidden collaborative intersections.

Laika access coming soon