Skyline-First Traversal as a Control Mechanism for Multi-Criteria Graph Search

• URL: http://arxiv.org/abs/2604.19807v1
• Date: Tue, 14 Apr 2026 08:44:24 GMT
• Title: Skyline-First Traversal as a Control Mechanism for Multi-Criteria Graph Search
• Abstract summary: This paper shows that under constrained cost models, finite cost grids, Markovian transitions, and a nonzero progress measure, Pareto geometry alone is sufficient to drive both scheduling and termination.<n>Our analysis establishes deterministic potential descent, certified termination via dominance coverage, a uniform bound on layer width induced by cost-grid geometry, and greedy cost-space dispersion within the skyline.
• Score: 0.0
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: In multi-criteria graph traversal, paths are compared via Pareto dominance, an ordering that identifies which paths are non-dominated, but says nothing about which path to expand next or when the search may stop. As a result, existing approaches rely on external mechanisms-heuristics, scalarization, or population-based exploration while Pareto dominance remains confined to passive roles such as pruning or ranking. This paper shows that, under constrained cost models, finite cost grids, Markovian transitions, and a nonzero progress measure, Pareto geometry alone is sufficient to drive both scheduling and termination. We show that extracting exclusively from the first Pareto layer, the skyline, induces a deterministic descent in a discrete completion potential, ensuring monotone progress toward solution completion. In parallel, a vector lower-bound certificate provides a stopping condition that guarantees dominance coverage of all remaining traversals without requiring a predefined number of solutions. Our analysis establishes deterministic potential descent, certified termination via dominance coverage, a uniform bound on layer width induced by cost-grid geometry, and greedy cost-space dispersion within the skyline. The resulting framework operates without scalarization, heuristic guidance, or probabilistic models, and repositions Pareto dominance from a passive filter to a deterministic driver of search.

Related papers

• One Step, One Lead: Mitigating Higher-Order Interference in Multi-Domain Reinforcement Learning via Cross-Step Control [62.82372407840088]
  We show that same-point domain gradients may remain nearly even when consecutive realized updates partially reverse one another in output space.<n>We propose OSOL, which designates a focus domain at each iteration, to rank token-level rebound risk.<n>OSOL reaches a domain-macro average of 0.4822, improving by 5.7% over the strongest compared baseline, without explicit higher-order differentiation.
  arXiv  Detail & Related papers  (2026-09-06T08:32:59Z)
• Certifying Plans under Model Mismatch: A Trilemma for Reachability from Scarce Data [5.455772242709494]
  Sim-to-real policies are designed under nominal dynamics, but target-system trials may yield only a few isolated one-step transitions.<n>We study pre-execution certification of a fixed control sequence, such as an action chunk produced by a learned policy.
  arXiv  Detail & Related papers  (2026-08-03T16:28:26Z)
• Fitting Unknown Number of Hyperplanes with Manifold Optimization [57.48093263119306]
  Fitting unknown number of linearplanes to data is a fundamental yet challenging problem in machine learning.<n>Existing approaches often struggle with optimum optima or lack geometric consistency.
  arXiv  Detail & Related papers  (2026-05-27T14:02:20Z)
• Order-Sensitive Sequential Interventions on Ideal Lattices [0.0]
  We study sequential interventions under prerequisite constraints.<n>In this setting, admissible intervention sequences are paths in the ideal lattice of a finite prerequisite poset.<n>We give an exact local-to-global theory of order sensitivity on this state space.
  arXiv  Detail & Related papers  (2026-04-29T09:29:10Z)
• Sector-dominant graph-local drivers for path-window barrier Hamiltonians on the Boolean hypercube [0.0]
  We study finite-size adiabatic state preparation on Boolean hypercubes.<n>We use graph-local drivers built from sector/path coordinates related to monotone Gray-code representatives.<n>We provide code, finite certificates, CSV files, validation logs, and reproduction scripts to make the finite-size claims traceable.
  arXiv  Detail & Related papers  (2026-04-28T10:54:42Z)
• Benchmarking Classical Coverage Path Planning Heuristics on Irregular Hexagonal Grids for Maritime Coverage Scenarios [1.2891210250935148]
  This paper presents a reproducible benchmark of deterministic single-vehicle coverage planning on irregular hexagonal grids.<n>The benchmark contains 10,000 Hamiltonian-feasible instances spanning compact, elongated, and irregular morphologies.<n>The strongest classical Hamiltonian baseline is a Warnsdorff variant that uses an index-based tie-break together with a terminal-inclusive residual-degree policy, reaching 79.0% Hamiltonian success.
  arXiv  Detail & Related papers  (2026-04-16T16:28:03Z)
• Cross-Spectral Witness for Hidden Nonequilibrium Beyond the Scalar Ceiling [18.923595971721344]
  coarse graining may absorb hidden forcing into an apparently equilibrium-like reduced description.<n>For scalar observables of linear systems, no time-irreversibility statistic can detect the underlying drive.<n>Within general CSM this certifies shared hidden-sector drive.
  arXiv  Detail & Related papers  (2026-04-04T15:54:29Z)
• Directional Mollification for Controlled Smooth Path Generation [2.6381163133447836]
  Mollification has been recently proposed as a computationally efficient and analytically tractable tool for path generation.<n>We introduce directional mollification, a novel operator that resolves this limitation while retaining the analytical tractability of classical mollification.
  arXiv  Detail & Related papers  (2026-03-23T11:18:43Z)
• The Offline-Frontier Shift: Diagnosing Distributional Limits in Generative Multi-Objective Optimization [56.39938641873341]
  We show that generative methods systematically underperform evolutionary alternatives with respect to other metrics, such as generational distance.<n>We argue that overcoming this limitation requires out-of-distribution sampling in objective space.<n>Our results position offline MOO as a distribution-shift--limited problem and provide a diagnostic lens for understanding when and why generative optimization methods fail.
  arXiv  Detail & Related papers  (2026-02-11T18:38:40Z)
• TABES: Trajectory-Aware Backward-on-Entropy Steering for Masked Diffusion Models [35.327100592206115]
  Backward-on-Entropy (BoE) Steering is a gradient-guided inference framework that approximates infinite-horizon context via a single backward pass.<n>To ensure scalability, we introduce ttexttActiveQueryAttention, a sparse adjoint primitive that exploits the structure of the masking objective to reduce backward pass complexity.
  arXiv  Detail & Related papers  (2026-01-30T19:10:32Z)
• Reasoning by Superposition: A Theoretical Perspective on Chain of Continuous Thought [64.43689151961054]
  We prove that a two-layer transformer with $D$ steps of continuous CoTs can solve the directed graph reachability problem.<n>In our construction, each continuous thought vector is a superposition state that encodes multiple search frontiers simultaneously.
  arXiv  Detail & Related papers  (2025-05-18T18:36:53Z)
• Exploiting hidden structures in non-convex games for convergence to Nash equilibrium [62.88214569402201]
  A wide array of modern machine learning applications can be formulated as non-cooperative Nashlibria. We provide explicit convergence guarantees for both deterministic and deterministic environments.
  arXiv  Detail & Related papers  (2023-12-27T15:21:25Z)
• Lifting the Convex Conjugate in Lagrangian Relaxations: A Tractable Approach for Continuous Markov Random Fields [53.31927549039624]
  We show that a piecewise discretization preserves better contrast from existing discretization problems. We apply this theory to the problem of matching two images.
  arXiv  Detail & Related papers  (2021-07-13T12:31:06Z)

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.