Papers

Polyhedral outer approximation (OA) is widely used to solve mixed-integer second-order cone programs (MISOCPs) by iteratively strengthening polyhedral relaxations of conic constraints. However, the accumulation of cutting planes can increase the difficulty of solving the resulting mixed-integer linear programs (MILPs), while repeatedly solving these MILPs can be computationally expensive. To address these challenges, we investigate the geometry of supporting cuts and the computational role of integrality in OA. First, we establish theoretical bounds showing that the marginal contribution of a new supporting cut decreases at least linearly as its supporting direction approaches an existing one. Motivated by this analysis, we develop a closed-form cut-generation strategy that balances separation depth and directional diversity. Second, we propose a progressive-integrality OA framework that strengthens the polyhedral approximation through linear programs and partially integral relaxations before solving full MILPs. We theoretically characterize the transfer of cut-induced bound improvements across integrality levels and provide a branch-and-bound interpretation of the framework. Computational experiments on CBLIB instances and large-scale AC unit-commitment models demonstrate substantial improvements over classical OA and direct MISOCP solution, with runtime reductions of up to 62% relative to classical OA on the reported power-system instances.

We establish a global, worst-case non-identifiability theorem for periodically driven finite-dimensional quantum systems. On the unrestricted smooth periodic Hamiltonian class, we show that the period-averaged Fubini-Study metric component of a fixed initial state cannot, in general, be reconstructed from exact one-period propagators indexed by every starting time and external parameter. Thus, even complete starting-time-resolved endpoint data are insufficient to determine this intra-period geometric quantity. The obstruction is characterized exactly. The starting-time-indexed endpoint data determine the conjugation path of the monodromy, but not its particular unitary lift. On each fixed-monodromy slice, the observational fibres are precisely the right orbits generated by smooth parameter-dependent based loops taking values in the pointwise centralizer of the monodromy. The Fubini-Study functional is not invariant under this fibre action and therefore does not factor through the endpoint observation map. An explicit real-analytic two-level witness demonstrates the obstruction within a commuting, one-generator Hamiltonian family, so neither non-Abelian time ordering nor Floquet-logarithm ambiguity is required. A continuous family of Hamiltonians produces identical starting-time-indexed one-period endpoint data while yielding different, and on the unrestricted class arbitrarily separated, period-averaged Fubini-Study geometry. Non-identifiability persists under any prescribed uniform bound on the parameter derivative of the Hamiltonian. The result is a deterministic global statement, not a claim of generic non-identifiability or experimental impossibility. It identifies a precise information gap between complete one-period endpoint data and full intra-period dynamics: the missing information is the unitary lift of the observed monodromy path rather than ordinary scalar phase freedom.

We prove that all (possibly infinitely generated) semi-Gorenstein-projective modules over a virtually Gorenstein Artin algebra are Gorenstein projective. We also establish a new criterion for determining the projective (injective) dimensions of modules over virtually Gorenstein Artin algebras. This enables us to show the validities of the Auslander-Gorenstein Conjecture, the (Strong) Nakayama Conjecture and Tachikawa's First Conjecture for virtually Gorenstein Artin algebras. Finally, we prove that the Auslander-Reiten Conjecture holds for virtually Gorenstein Artin algebras of finite CM-type.

We study online discrepancy minimization for independent random vectors in $\mathbb{R}^n$ with independent coordinates. Our deterministic algorithms require no knowledge of the horizon, and their guarantees hold at every prescribed deterministic terminal time $T$. For unit-variance sub-exponential coordinates with $\psi_1$-norms at most $\sigma$, we obtain terminal discrepancy $O(\sigma^4\sqrt n)$ with failure probability $\exp(-\Omega(\sigma^3\sqrt n))$. Independently masking centered unit-variance marks from the same class with retention probability $k/n$ gives $O(\sigma^4\sqrt k)$ discrepancy with failure probability $\exp(-\Omega(\sigma^3\sqrt k))$ when $k\gtrsim\log^2(2n)$. The fourth-power dependence on $\sigma$ is necessary for these sub-exponential classes at the stated confidence levels. For standard Gaussian marks, we obtain $O(\sqrt k+\sqrt{\log(2n)})$ discrepancy with failure probability $\exp(-\Omega(\sqrt k+\sqrt{\log(2n)}))$. Both terms are necessary up to absolute constants for $T\ge n$. In particular, $k\gtrsim\log n$ is the optimal sparsity threshold for $O(\sqrt k)$ discrepancy. For centered unit-variance sub-Gaussian marks with any fixed $\psi_2$-norm bound $\sigma$, logarithmic sparsity suffices for $O(\sigma\sqrt{k\log(e+\sigma)})$ discrepancy with probability tending to one as $n\to\infty$. For a dimension-dependent family of unit-variance laws with rare activations, matching bounds determine the fixed-confidence online discrepancy order $\Theta(\sqrt n\log\log n)$ at sufficiently long prescribed horizons. Our dense result generalizes the Rademacher-input theorem of Bansal and Spencer (2020) and establishes the horizon-independent $O(\sqrt n)$ Gaussian terminal discrepancy scale anticipated by Gamarnik et al. (2022). The proofs combine regularization, global Fenchel estimates, coupled Lyapunov functions, and terminal moment recursions.

A. A. Suslin and V. I. Kopeiko proved that the elementary linear, symplectic, and orthogonal groups are normal in the general linear group, symplectic group, and orthogonal group respectively. They also proved relative versions of these normality results with respect to an ideal of a ring. A. Bak, R. Basu, and R. A. Rao proved that the linear, symplectic, and orthogonal transvection groups are normal in the respective automorphism groups. These results are generalizations of the normality results by Suslin and Kopeiko in the setup of modules. In this paper, we prove stronger versions of the normality results proved by Bak, Basu, and Rao, which say that the relative transvection groups are normal in the respective automorphism groups.

Given a finite group $G$, we denote by $\psi(G)$ the sum of element orders of $G$. In this note, we determine finite groups $G$ such that $|H|-|K|$ divides $\psi(H)-\psi(K)$ for all subgroups $K\leq H\leq G$. Two weaker conditions are also proposed.

Let $G$ be a finite group and $H$ be a proper normal subgroup of $G$. In this note, we introduce two new functions $o(G,H)$ and $\psi''(G,H)$ involving the sums of element orders of $G$ and $H$. We prove that they satisfy certain inequalities, with equality if and only if $(G,H)$ is an equal order pair of a particular type.

Let $\{q_{k}: k\in\mathbb{N}\}$ be a non-increasing and convex sequence of non-negative numbers such that $q_{0}>0$. Our main result is to prove almost everywhere convergence \[ t_{a_{n}}(f)\to f \] of $f\in L_{1}(G)$ as $n\to\infty$, using several $\{a_{n}: n\in\mathbb{P}\}$ subsequences of positive integers for Nörlund means (defined by sequence $q$) on the Walsh-Paley system with weaker conditions than it was known before.

Many modern testing problems are sequential along two axes: new hypotheses may arrive over time, while evidence for hypotheses already under consideration continues to evolve and may be inspected at arbitrary stopping times. We develop dynamic $e$-closure for this setting. At a global stopping time the active true-null intersection is random. Future-extension coherence allows its certificate to be compared with that of a fixed terminal intersection, yielding simultaneous stopped-FDR control. If the certificates are also time-monotone, the resulting closure controls simultaneous SupFDR and is setwise persistent. Conversely, every procedure satisfying either criterion is contained in a dynamic closure generated by canonical normalized-loss processes. For pointwise mergers, fixed-dimensional admissibility is equivalent to ordinary arbitrary-dependence $e$-merging. Coherence across horizons then forces a single globally summable weight sequence and exact neutrality under padding by the $e$-value one; on a countably infinite hypothesis universe, this rules out nontrivial symmetric mergers in the admissible pointwise class. The theory extends from FDP to bounded losses that are monotone in the possible true-null configuration and local in the reported action. We also give a coherence counterexample, persistent constructions, and a globally valid shared-control model.

We investigate a class of Ricci-flat Kähler metrics on generalized conifolds constructed via gauged linear sigma models (GLSMs) with indefinite signature. By introducing shadow coordinates (superfields) entering the sigma model with negative signature kinetic term, we show that these GLSMs yield explicit Ricci-flat metrics on complex cones over products of projective spaces. We provide a general formula for the resulting Kähler potentials, along with detailed examples. Our results suggest new directions for the study of Calabi-Yau metrics and toric geometry, and raise interesting questions about the geometric meaning of indefinite signature models. We also give an interpretation in terms of a novel generalized Kähler gauging.

Two-dimensional translation-invariant topological CSS codes on qubits are known to be locally equivalent, after coarse-graining, to stacks of toric codes. However, existing constructions generally break more translation symmetry than is required to remove anyon-permuting translations, leaving open whether any further obstruction exists. We prove that no such obstruction occurs: after passing to the maximal anyon-preserving superlattice, every such code admits a local unitary decoupling into toric codes and product states. We further provide an efficient algorithm for explicitly constructing the decoupling map, together with bounds on the required supercell size and operator spreading. The decoupling requires no additional ancillas in generic cases and extends to finite systems with suitable boundary conditions.

Can excitation structure classify topological quantum codes up to finite-depth local circuits? For translation-invariant topological Calderbank–Shor–Steane (CSS) codes in arbitrary dimensions, we introduce excitation superselection profiles $\mathscr E_\sigma$ ($\sigma=X,Z$). Their cohomology layers $E_\sigma^\ell:=H^\ell(\mathscr E_\sigma)$ encode excitation types, fusion rules, and translation action, while $\mathscr E_\sigma$ retains cross-degree gluing. Pointlike, looplike, and higher-dimensional excitations correspond to degrees $\ell=1,2,\ldots$, respectively. Our matrix-level Schanuel-lemma method proves single-degree superselection rigidity: if $\mathscr E_\sigma$ is supported in a single degree $\ell$, then $E_\sigma^\ell$ and $\ell$ fix the stable translation-invariant Clifford class under a finite-resolution hypothesis automatic for prime qudits. If $E_\sigma^\ell$ is also finite, prime-qudit codes decouple into toric-code stacks by Clifford circuits after coarse graining, with the exact minimal threshold set by the translation kernel. We develop a unified topological theory of Koszul-complex models (encompassing toric codes, bivariate-bicycle codes, and Haah's cubic code): for regular models, we compute $E_\sigma^\ell$, prove $\mathscr E_\sigma$ is single-degree, express finite-torus logical modules as $\mathrm{Tor}$ groups, and obtain coarse-grained toric-stack normal forms at full length. Two constructions extend this framework to realize any admissible single-degree profile and build multi-degree extensions. The latter yields eight 3D qubit toric-code extensions with identical layers in both Pauli sectors and trivial translation action, yet distinct size-dependent ground-state degeneracies. The seven nonsplit models require blocking to decouple. Thus, cross-degree gluing carries translation-symmetry-enriched topological information invisible to individual layers.

We study the $\beta=2$ partition function $\int_{|h| \leq \log ^{\theta} q/2}|L(1/2+ih,\chi)|^2dh$ for typical Dirichlet characters modulo a large prime $q$ and $\theta \in (-1/3,0]$ motivated by a $q$-analogue of the Saksman–Webb conjectures. When $\theta <0$, we use an extension of Harper's randomisation argument with different localisations to recover moment upper bounds consistent with the critical normalisation predicted there. As an application, we prove that for $q(1-o(1))$ Dirichlet characters modulo $q$ with $U(q) \to \infty$, $$\max_{|h| \leq 1/2}|L(1/2+ih,\chi)|\ll \frac{e^{U(q)}\log q\log_3 q(\log_4 q)^{1/2}}{(\log_2 q)^{3/4}},$$ establishing an upper bound matching the predictions of the $q$-analogue of the Fyodorov–Hiary–Keating conjectures up to second order. Our proofs adapt Harper's argument in \cite{harper2019partition}.

Let $X$ be a smooth projective surface with $p_g=0$, and let $H$ be an ample divisor with $h^0(\mathcal{O}_X(H))\neq0$, $\chi(\mathcal{O}_X(H))\ge q$, and $h^1(\mathcal{O}_X(H))\neq0$. We prove that no rank two bundle $\mathcal{E}$ with $c_1(\mathcal{E})=3H+K_X$, with the Ulrich value of $c_2(\mathcal{E})$, and satisfying $h^0(\mathcal{E}(-H))=0$, can arise from an extension $0 \to \mathcal{O}_X(H+K_X) \to \mathcal{E} \to \mathcal{O}_X(2H)\otimes\mathcal{I}_Z \to 0$. Thus, for this natural Cayley-Bacharach construction, non-speciality of the polarization is necessary rather than merely convenient. We then study primary Burniat surfaces. We show that every ample and base point free divisor is non-special; consequently, every polarization carries a stable special Ulrich bundle of rank two, and the surface is strictly Ulrich wild with respect to every polarization. We also locate the special ample classes on three numerical rays through $K_X$, compute explicit families on these rays, and analyze a twisted-kernel variant of the construction. The degree bound underlying the non-speciality result overlaps with recent work of Y. Cho, while the global consequences and the no-go theorem are independent.

In 1989, Gyárfás conjectured that the vertex set of every $r$-edge-coloured complete graph can be partitioned into at most $r$ vertex-disjoint monochromatic paths. Erdős, Gyárfás, and Pyber subsequently proposed the analogous conjecture for monochromatic cycles. Pokrovskiy proved Gyárfás's conjecture for $r=3$, while disproving the conjecture of Erdős, Gyárfás, and Pyber for every $r\ge3$ by constructing colourings that require at least $r+1$ monochromatic cycles. In this paper, we disprove Gyárfás's conjecture in a quantitatively strong superlinear form: for every sufficiently large $r$, there exists an $r$-edge-coloured complete graph that requires at least $(1-o(1))r\log\log r$ vertex-disjoint monochromatic paths. Consequently, the monochromatic cycle-partition number is also superlinear in $r$. Our construction also disproves two conjectures of Pokrovskiy: one on monochromatic cycle coverings and the other on path coverings in the balanced bipartite setting.

Inspired by possible future markets of autonomous routing and driving (ARAD), we introduce competitive mediator games and their equilibria which generalize the (coarse) correlated equilibria, which have become a popular research area recently as they not only can be more socially efficient than Nash equilibria but also are limits of algorithmic no-regret multi-agent learning dynamics. We discuss the basic properties of competitive mediator games and prove that in the generic setting of anonymous congestion(routing) games with market-share maximizing mediators all competitive mediator equilibria are monopolies whenever one of the mediators is weakly preferred to other mediators by all users. We apply and interpret these results in the context of new markets of competing ARAD service providers. We also provide a comprehensive overview of these markets and discuss the future mechanism design thereof.

In this work, we define entanglement-assisted quantum locally recoverable codes with availability, in which any set of up to $\delta-1$ erased qudits can be recovered from any one of $t$ local recovery sets, each of size at most $r+\delta-1$, with the recovery sets intersecting exactly in the erased coordinates, where $r$ is a (small) positive integer. We show that shared entanglement permits $t>1$, meaning that multiple local recovery sets can be available for the same set of up to $\delta-1$ erasures. We establish a Singleton-like bound for this family of codes and present random constructions based on classical linear codes with Vandermonde parity-check matrices. We also provide explicit constructions of entanglement-assisted quantum locally recoverable codes with availability from several classical code families and their folded versions, including Tamo-Barg codes, fiber-product codes, and algebraic-geometry codes such as one-point Hermitian and Suzuki codes.

We study $L^\infty$ Widom factors for Chebyshev and residual polynomials on compact non-polar subsets of the real line that need not be regular in the sense of potential theory and, in particular, on sets with isolated points. We first show that boundedness of the Widom factors is independent of the normalization point $x_*\in\overline{\mathbb{R}}\backslash\mathsf{E}$. For semi-regular sets, meaning that the set of regular points $\mathsf{E}^\mathrm{reg}$ is closed, we introduce the irregularity coefficient $\mathcal{IR}(\mathsf{E},x_*)=\sum_{x\in\mathsf{E}\backslash\mathsf{E}^\mathrm{reg}}G_\mathsf{E}(x,x_*)$, which measures the contribution of irregular boundary points to the extremal polynomial problem. Our upper bound is \[ \sup_{n\ge1}\mathcal{W}_n(\mathsf{E},x_*) \le 2\exp\bigl[\mathcal{PW}(\mathsf{E}^\mathrm{reg},x_*)+\mathcal{IR}(\mathsf{E},x_*)\bigr], \] while the complementary lower bound is \[ \liminf_{n\to\infty}\mathcal{W}_n(\mathsf{E},x_*) \ge 2\exp\bigl[\mathcal{IR}(\mathsf{E},x_*)\bigr]. \] Consequently, for semi-regular Parreau–Widom sets the Widom factors are bounded if and only if $\mathcal{IR}(\mathsf{E},x_*)<\infty$. When the regular part is a finite union of intervals, this condition is equivalent to a geometric square-root summability condition on the irregular points. In the special case $\mathsf{E}=[a,b]\cup\{x_k\}_{k\ge1}$, the Widom factors have the exact, possibly infinite, limit $2\exp[\mathcal{IR}(\mathsf{E},x_*)]$. When this limit is finite, we obtain the corresponding Szegő–Widom asymptotics for the normalized extremal polynomials.

We study rooted Gibbs-DLR measures in the directed polymer model on $\mathbb{Z}^2$ with an ergodic disorder distribution which satisfies an additional mild hypothesis. We prove that the set of extremal rooted Gibbs-DLR measures is closed and totally ordered, characterize extremality in terms of path coalescence, and show that each fully supported extremal rooted Gibbs measure canonically generates a globally consistent and coalescing family of extremal rooted Gibbs measures indexed by all lattice sites. These families are, moreover, totally ordered. Building on this structure, we prove strong existence and strong uniqueness of the associated Busemann process, together with an $L^1$ continuity theorem for the shift-covariant Busemann cocycles which is joint in the inverse temperature, the tilt parameter, and the random environment. This yields, as a corollary, in-probability continuity of the generated extremal Gibbs measures corresponding to directions of differentiability under bounded i.i.d. perturbations of the weights. In positive temperature, it shows in-probability convergence of the generated extremal Gibbs measures. At zero temperature, it also yields quenched subsequential large deviation principles for the corresponding positive-temperature rooted Gibbs-DLR measures on path space. The rate functions are determined by a zero-temperature Busemann cocycle and vanish precisely on the infinite geodesics generated by that cocycle.

The algebraic connectivity of a graph $G$ is a well-studied graph invariant that is related to other properties of the graph such as connectivity and expansion. Given $n$ and $m$, $\alpha(n,m)$ is the maximum algebraic connectivity of a graph with $n$ vertices and $m$ edges. In 2015, Kolokolnikov conjectured that $\alpha(n,2n-4)=2$ for $n\geq 4$, and verified this claim computationally for $n \le 12$. In this paper, we prove Kolokolnikov's conjecture. We also show that $\alpha(n,3(n-3)) = 3$ is false in general. %Combined with the computational verification for $n \le 12$, this yields $\alpha(n,2n-4)=2$ for all admissible values of $n$.

We prove existence and non-existence results for $L^2$ eigenforms for the Hodge Laplacian on complete non-compact Ricci flat manifolds with special holonomy, with a particular focus on gravitational instantons. We briefly describe the physical interpretation of these results in superstring and M-theory.

We study holomorphic foliations on projective spaces that leave smooth projective complete intersection surfaces $M$ invariant. We determine precisely for which degrees such foliations on $M$ exist. As a consequence, we obtain new bounds for the classical Poincaré problem for smooth projective complete intersection surfaces and prove that previously known bounds for smooth hypersurfaces in $\mathbb{P}^3$ are optimal. Furthermore, for a foliation $[s]$ on $M$ with isolated singularities and for degrees beyond an explicit bound that we provide, we show that a section $s'$ has singular scheme containing that of $s$ if and only if $s'=\phi(s)$ for some global endomorphism $\phi$ of the tangent bundle of $M$.

We consider stochastic optimization where the goal is not only to optimize an average-case objective, but also to mitigate the occurrence of rare catastrophic events. This problem is motivated by safety-aware decision-making and AI training. We first argue that, in the presence of a simulation model, natural attempts to integrate variance reduction into optimization, even executed in a reasonable adaptive fashion, encounter fundamental challenges in guaranteeing realistic runtime when using common stochastic gradient descent algorithms. This challenge arises from the extreme sensitivity of tail-based objectives with respect to the decision variables, which renders a dichotomic failure of convergence regardless of what step size we select. We offer remedies based on a new notion of safe start that allows for efficient finite-time error control, and show how the sampling complexity scales favorably under the combination of safe start and variance reduction. We illustrate our methodologies on examples in portfolio optimization and robust classification with neural networks.

In this article, we study the Lebesgue space inequalities for extension operators associated with hyperbolic surfaces over rectangular regions. We characterize the corresponding operator norms in terms of the side-lengths. As an application, we present new restriction estimates for a class of hypersurfaces with additive structure.

Uniform stability is a classical tool for controlling the generalization error of a learning algorithm. Bousquet, Klochkov, and Zhivotovskiy (2020) showed that the problem can be reduced to a moment inequality for a sum of weakly interacting functions of independent random variables. Their bound contains an additional factor $\log n$, and they asked whether this factor can be removed. We answer this upper-bound question affirmatively. More specifically, let $Z=(Z_1,\ldots,Z_n)$ have independent coordinates and let $g_i(Z)$ satisfy $\mathbb E[g_i(Z)\mid Z_{-i}]=0, \ \left| \mathbb E[g_i(Z)\mid Z_i]\right|\le M, \ \text{for every } i = 1, \dots, n, $ where $Z_{-i}$ denotes all coordinates except $Z_i$. Assume additionally that changing any coordinate $Z_j$, $j\neq i$, changes $g_i$ by at most $\beta$, we prove that, for every $p\ge2$, for every $p\ge2$, $$ \left\| \sum_{i=1}^n g_i(Z)\right\|_p \le 16pn\beta+M\sqrt{2pn}. $$ This removes the $\log n$ factor from the previous bound and matches the lower bound of Bousquet, Klochkov, and Zhivotovskiy up to universal constants in the range covered by their construction. Our proof first establishes the required estimate on the Rademacher cube, then transfers it to arbitrary product distributions by a two-copy randomization argument.

A graph on \(n\) vertices is called a Parter graph if there exists a nonsingular symmetric matrix, whose nonzero off-diagonal entries correspond exactly to the edges of the graph, such that all of its principal submatrices of order \(n-1\) are singular. Previously, a graph satisfying this condition was said to have property~(P). It was proved that, for bipartite graphs of cycle rank at most \(3\), being a Parter graph is equivalent to the existence of a perfect matching. We extend this result to cycle rank \(4\), proving that every bipartite graph of cycle rank at most \(4\) is a Parter graph if and only if it has a perfect matching. Furthermore, we show that this bound is sharp by constructing, for every integer \(r\ge5\), a connected balanced bipartite Parter graph of cycle rank \(r\) that has no perfect matching.

Recently, A. Tyulenev and the author studied the class of metric spaces $\mathcal{X}$ such that for every mapping $\gamma \colon [0,1]\to\mathcal{X}$, there exists a $1$-Lipschitz function $F\colon \mathcal{X}\to \mathbb{R}$ that catches the total variation of $\gamma$, i.e. such that $\operatorname{V}_{F\circ\gamma} \gtrsim \operatorname{V}_\gamma$. In this short note, we show that a metric space $\mathcal{X}$ enjoys this property if and only if there exists a random $1$-Lipschitz function $f$ on $\mathcal{X}$ such that $\mathbb{E} |f(x) - f(y)| \gtrsim \rho(x,y)$ for every $x$ and $y$ in $\mathcal{X}$.

For $ n \geq 2$, $A\in M_n(\mathbb C)$ and $0<|q|\leq 1$, let $\Omega_q(A)=q^{-1}W_q(A)$ be the scaled $q$-numerical range. We prove that for every $\gamma \geq 1$, \[ \Omega_{\eta(\gamma)}(A) =\bigcup_{\kappa(S)\leq\gamma}W(S^{-1}AS), \qquad \eta(\gamma)=\frac{2}{\gamma+\gamma^{-1}}, \] where $\kappa(S)=\|S\|\,\|S^{-1}\|$. As a consequence, we prove the sharp inequality \[ \|p(A)\|\leq \max\!\left\{1,\frac{2|q|}{1+\sqrt{1-|q|^2}}\right\} \max_{z\in\Omega_q(A)}|p(z)|, \] for all polynomials $p$.

Vehicle platooning offers significant benefits, including reduced energy consumption, lower emissions, improved road utilization, enhanced safety, and reduced driver fatigue. As intelligent driving technologies continue to advance, platoon sizes are expected to increase substantially, making the efficient sequencing and resequencing of vehicles increasingly important. We study the vehicle platoon sequencing and resequencing problem on road networks with varying segment lengths under two fundamental objectives: minimizing total energy consumption and minimizing the maximum energy consumption of any vehicle. For the typically encountered combinations of vehicle and road characteristics, we provide a complete computational complexity classification, either developing polynomial-time algorithms or proving computational intractability. For several intractable cases, we design fully polynomial-time approximation schemes and polynomial-time heuristics with provable performance guarantees. A computational study demonstrates that the proposed heuristics achieve average solutions within 1% of optimal. We also consider settings in which only limited information about position-dependent energy savings is available and develop a heuristic with bounded worst-case performance. In addition, we present an efficient algorithm for on-road vehicle resequencing when only limited position changes are permitted. Together, these results provide a comprehensive algorithmic framework for energy-efficient vehicle platoon sequencing and resequencing.

Let $h>0$. For a complete and separable $\mathbb{R}$-tree $(T,d)$ equipped with a root $\rho$ and a finite Borel measure $\mu$, we define the $h$-mass-erased tree by removing from $T$ all fringe subtrees of mass less than $h$ and we equip it with a suitable measure such that the erasure operators $(\mathcal{E}_h)_{h\ge 0}$ form a semigroup that is continuous for the Gromov-weak topology. Then, we say that a sequence $\boldsymbol{\mu}_n=(T_n,d_n,\rho_n,\mu_n)$, $n\in\mathbb{N}$, converges in the sense of mass erasure if $(\mathcal{E}_h\boldsymbol{\mu}_n)_{n\in\mathbb{N}}$ converges Gromov-weakly for all $h\ge 0$. This notion of convergence is strictly weaker than Gromov-weak convergence and we establish criteria to relate the two notions. We define a distance function that metrizes convergence in the sense of mass erasure. By extending the notion of measured $\mathbb{R}$-trees to allow mass on the boundary (the far ends of infinite geodesics), we obtain a complete metric space. Next, we identify random trees of finite type (that is, discrete trees with edge lengths) satisfying the regenerative branching property as a specific class of measured (sub)critical GW forests. We then show that this class of trees is preserved by mass erasure and we compute the law of these mass-erased GW forests explicitly. Finally, we establish a limit theorem for these measured (sub)critical GW forests to converge to standard measured Lévy forests, i.e. those whose total mass has the same distribution as the total population of a continuous-state branching process. This includes cases with bounded variation by crucially using the convergence in the sense of mass erasure and it extends the cases studied previously.