network schedulers

Abstract: The growth of large language model (LLM) inference and search services increases the scale of online linear programming problems, motivating computationally efficient algorithms. We develop resource-adaptive stochastic gradient descent (RASGD) for stochastic online linear programming. The algorithm uses one request and current inventory to update resource prices, requiring O(m) operations for m resources and memory per arrival and no LP or sample-average optimization. The central idea is to express the current-resource pricing logic of re-solving through a first-order SGD update: each arrival refreshes the remaining-inventory allowance in the dual objective, while the stepsize decreases for early learning and increases later to match the speed of inventory adjustment. Under standard non-degeneracy conditions, our algorithm is feasible on every sample path and achieves O(\log T) expected regret against the realized fractional hindsight optimum, which matches the lower bound, even for policies that know the distribution and have unrestricted computation. The analysis converts curvature around the fixed reference price into inventory stability without tracking optimal prices at changing resource levels. Numerical experiments show that RASGD achieves regret competitive with per-arrival LP re-solving and improves upon the tested first-order baselines, while retaining the computational efficiency of first-order methods. These results establish RASGD as a computationally efficient approach to achieving high allocation quality in large-scale OLP.

Abstract: An edge weighting of a graph induces a coloring of its vertices in which the color of a vertex is the total weight of the edges incident with it. Such an edge weighting is proper if adjacent vertices always receive distinct colors. Deciding whether a graph admits a proper weighting is known to be NP-complete for the weight set $\{0,1\}$, and also for $\{1,2\}$. In recent work (arXiv:2604.12363) we showed that both problems are FPT parameterized by the vertex cover number $k$, but it was open -- to the best of our knowledge -- whether either parameterized problem had a polynomial kernel. In this work, we show that both problems have polynomial kernels when parameterized by $k$. We also show that both problems are W[1]-hard parameterized by treedepth, answering another question from our earlier work. We then study the pre-weighted versions of the two problems, in which the weights of some edges are fixed in advance, and the task is to extend the assignment to a proper weighting of the whole graph. We show that both pre-weighted problems are FPT parameterized by the vertex cover number $k$. For the $\{1,2\}$ version the running time is $2^{O(k \log k)} \cdot n$; for the $\{0,1\}$ version we obtain the same running time when every pre-weight is $1$, and a slower FPT algorithm in the general case. We also show that both pre-weighted problems are W[1]-hard parameterized by either of (i) the feedback vertex set number or (ii) the treedepth of the input graph. Since a graph with no pre-assigned weights is a special case, our algorithms for the pre-weighted versions solve the two original problems as well, in time $2^{O(k \log k)} \cdot n$, significantly improving on the bound of $2^{O(k^4)} \cdot n^{O(1)}$ from our earlier work.

Abstract: Vehicle-to-Everything (V2X) communications impose very demanding requirements in terms of latency and reliability, which must be met in scenarios where multiple services with diverse performance targets coexist. In such scenarios, traffic-intensive services compete for limited radio resources, complicating the fulfillment of V2X service demands. Within this context, Network Slicing (NS) emerges as a key factor that enables the creation of multiple slices and the allocation of resources among them to satisfy heterogeneous service requirements. In particular, this work addresses the Radio Access Network (RAN) slicing problem from the perspective of Physical Resource Block (PRB) partitioning under high traffic demand conditions. To this end, a reinforcement learning approach based on Proximal Policy Optimization (PPO) is proposed to determine PRB allocations that satisfy the strict latency and reliability requirements of V2X services, while improving resource utilization efficiency and minimizing performance degradation of enhanced Mobile BroadBand (eMBB) services. The proposed solution is evaluated through simulation-based experiments under various traffic loads and different V2X service requirements, demonstrating its ability to adapt resource partitioning to network conditions and service demands.

Abstract: Intent-based networking decouples desired outcomes from device-level configuration, but most systems still map intents to parameters of an algorithm selected in advance. Large language models (LLMs) create an opportunity to automate algorithm design, yet unrestricted generated code is unsuitable for transport-network control because feasibility, reproducibility, and robustness must be enforced independently of the model. We present VERA-TN, a verification-guided framework that compiles a network intent into a bounded algorithm-design specification. The target architecture uses an LLM as a semantic variation operator over typed request-ordering and path-ranking programs; generated logic remains separated from a trusted allocator that enforces path validity, latency, capacity, and single-path constraints. We prove feasibility preservation under explicit assumptions and establish a sufficient bound for the lexicographic latency tie-break in the exact reference model. The released proof-of-concept instantiates the same interface with a bounded ten-parameter numerical candidate and deterministic replay, rather than a completed live-LLM/AST study. Across 150 certified held-out cases on a 28-node TEFNET24-derived hierarchy, evolutionary search reaches a mean priority-utility ratio of 0.958, compared with 0.952 for equal-budget random search and 0.940 for priority-greedy routing. The gain over random search is small but statistically detectable (Holm- adjusted p = 0.0083). The candidate does not improve congestion relative to MILP-C, and the effect of failure-aware training is inconclusive at the 0.05 level (p = 0.051). Eight discovery runs on the official national topology and replay on 12 unseen metro-regional topologies show no stable intent-specific specialization. These results support the trust-boundary and numerical-evolution claims but do not establish a benefit from LLM generation.

Abstract: Open RAN (O-RAN) slicing xApps must adapt resource allocations to changing channel conditions and traffic demands while meeting service-level agreements (SLAs). Deep reinforcement learning can produce adaptive policies, but their allocation rules remain encoded in neural-network parameters. Our goal is to retain this adaptability while making the controller's decision logic directly inspectable and editable by operators. We use a large language model (LLM) to evolve slicing controllers as compact Python programs whose decision logic remains readable and editable after optimization. The LLM proposes and revises candidates offline, while a calibrated simulator scores them, and the selected decision module runs unchanged in the O-RAN control path. On the NSF POWDER 5G testbed, the evolved controller releases resources from a guaranteed slice whose throughput target becomes unattainable under a sustained channel fade, improving best-effort throughput from 158.2 to 228.6 Mbps, a 44.5% gain over the best static allocation. Since the controllers are readable source code, their behavior can be predicted from their equations, defects can be diagnosed by reading the code, and calibration errors can be corrected with one-line edits, reducing SLA misses from 79.9% to 2.2% in one case and more than doubling fitness in another. In a four-slice trace-driven simulation calibrated to the same testbed, evolutionary search achieves higher average evaluation scores than independent prompting at a matched proposal budget, with mean normalized gains on held-out traces of 16.3% for prompting alone, 32.1% for evolution from scratch, and 51.0% for evolution from a starting program.

Abstract: Resource allocation systems often restrict each request to a short list of options before coordinating assignments globally. We study this separation in stochastic bipartite matching under independent vertex arrivals. Each request draws a state from its own known distribution, determining its compatible resources, and independently retains a menu of at most $k$ edges. A maximum matching is then computed on the retained graph. We show that bounded local menus universally suffice for near-optimal matching. For every $\varepsilon>0$, there is a menu size $k_\varepsilon$ depending only on $\varepsilon$ that preserves at least a $(1-\varepsilon)$ fraction of the expected maximum-matching size of the full realized graph. Earlier guarantees required additional assumptions on how matching mass is distributed across edges; our result resolves the unrestricted case. Moreover, the menus are simple to generate from any benchmark matching rule, either by weighted sampling according to the benchmark's edge marginals, or by applying the benchmark to sampled realizations and retaining the resulting partners. Our proof constructs a near-optimal certificate inside the sparsifier by combining a \emph{locally computable} surrogate for the large-marginal edges with a fractional completion from sampled light edges. The surrogate nearly preserves the benchmark's value and endpoint loads while controlling dependencies, which makes the statistical light-edge completion possible.

Abstract: The Minimum Sum Vertex Cover (MSVC) problem asks for an ordering of the vertices of a graph that minimizes the sum, over all edges, of the time at which each edge is first covered. We study the problem through the structure of vertex covers and obtain new approximation and exact algorithms, together with conditional lower bounds. For graphs of maximum degree $Δ$, we show that a simple ordering algorithm based on a minimum vertex cover achieves approximation ratio $R_Δ\le {(\sqrtΔ+1)}/{2}$. For $d$-regular graphs, we give a polynomial-time $1.184$-approximation by combining Max-$k$-Vertex-Cover approximation with a structural bound on optimal prefixes. On the exact side, we give an algorithm parameterized by the vertex cover number $k$ running in $2^{O(k\log k)} + O(n+m)$ time, improving the previous dependence on $k$, where $n$ and $m$ are the number of vertices and edges in the graph, respectively. We also develop a separator-based exact algorithm running in $ 2^{O(\sqrt n \log n)}$ time on planar, bounded-genus, and fixed-minor-free graph classes. Finally, we prove that Minimum Sum Vertex Cover is NP-hard on planar graphs and, assuming ETH, admits no $2^{o(\sqrt n)}$-time exact algorithm on $n$-vertex planar graphs. Thus our planar upper bound is tight up to logarithmic factors in the exponent.

Abstract: As serving capacity demand surpasses that of training, serving efficiency becomes increasingly important. Prefill-decode (P/D) disaggregation improves serving efficiency through specialization and isolation of the two phases. These benefits rest on a static partitioning. Phase demand, however, is not static. We observe that in a large LLM fleet the ratio of uncached input to output tokens has peak-to-mean ratios up to 4.7x at minute timescales, and that in a public agentic trace the hourly ratio spans a median 24.5x within a single day, while reassigning a replica takes tens of minutes. Agentic traffic sharpens the mismatch. Sizing each pool at its ninety-fifth percentile leaves up to 17% of cluster capacity unused; sizing below it converts the same imbalance into queueing and unrealized throughput. We present Crossflow, which makes this boundary elastic without changing node roles. Each decode node publishes a short-lived, revocable lease that bounds local-prefill compute, KV capacity, transfer work, and projected output. Across public and internal traces, Crossflow improves token throughput by 16.2-17.4% on geometric mean over static P/D, and by up to 43.4% at high load, while reducing mean TTFT at every evaluated point.

Abstract: We study asynchronous collective tree exploration, where $k$ agents with unrestricted communication start at the root of an unknown tree and discover edges online. At each step, an adversary chooses which agent moves. We give a deterministic algorithm that explores any tree with $n$ nodes and depth $D$ in at most \[ 2n+O\left(k\log^2(k)D\right) \] moves, matching known lower bounds up to a constant factor. As a direct consequence, we obtain a near-optimal competitive ratio of $O(\log^2 k)$ for synchronous collective tree exploration, where all agents move at each round. The proof relies on a multiscale power regularizer that may be of independent interest.

Abstract: Increasingly, resource allocation games are being proposed to model team coordination in denied communication environments. Of particular interest is understanding the impact of communication denial on the quality of emergent team coordination. In this work, we consider the situation with an arbitrary communication network and use the Price of Anarchy to quantify the quality of emergent behavior. Our main result is a computationally efficient algorithm that calculates a minimal communication network that has the same performance guarantee as the full information case. Additionally, we provide efficient algorithms that compute a Nash and a strict Nash equilibrium in the full information setting. Finally to support these algorithms, we provide sufficient conditions for the existence of a strict Nash equilibrium, characterize strict Nash equilibria across all communication networks, and show that each strict Nash equilibrium in the full information case has a necessary and sufficient set of communication links that induce it. We conclude by giving an execution time experiment of the proposed algorithm and examine several example games.

Abstract: In wireless communication networks, many resource optimization problems are nondeterministic polynomial-time hard (NP-hard) due to their combinatorial nature and high computational complexity. Recently, neutral-atom-based quantum computing has emerged as a promising platform for efficiently solving such problems by leveraging quantum superposition and entanglement. However, its application to wireless communication optimization problems remains largely unexplored. In this paper, we investigate the use of neutral-atom quantum platforms to solve the maximum access problem (MAP), formulated as a mixed-integer programming task that jointly considers admission control, user clustering, channel assignment, and power allocation in a non-orthogonal multiple access (NOMA)-enabled uplink network. To reduce the computational burden, the MAP is equivalently reformulated as a maximum independent set (MIS) problem in graph theory. This reformulation enables the use of the neutral atom platform based on Rydberg atom arrays, where the MIS problem is naturally encoded into the physical geometry and blockade constraints of the quantum system. Numerical results demonstrate the feasibility and potential of this approach for addressing large-scale wireless resource optimization problems.

Abstract: In this paper, we study the minimum-cost bipartite matching with penalties problem in metric spaces with bounded doubling dimension: Given two disjoint sets $R, B$ in a metric space $\mathcal{M}$ with $|R|+|B|=n$ and a penalty function $p \colon R \cup B \to \mathbb{R}_{\ge 0}$, the goal is to select a set of pairs in $R\times B$ so that every point belongs to at most one pair and the sum of the distances of the selected pairs and the penalties of the points not belonging to any pair is minimized. While near-linear time approximation algorithms are known for the minimum-cost perfect matching problem in geometric settings, no such algorithm was previously known for the penalty setting. We present a randomized algorithm that computes a $(1+\varepsilon)$-approximate minimum-cost bipartite matching with penalties in $O(n \mathrm{poly}(\log n, 1/\varepsilon))$ time with high probability. To the best of our knowledge, this is the first near-linear time approximation algorithm for the problem in the penalty setting.

Abstract: Reconfigurable photonic interconnects are emerging as a promising communication architecture for next-generation distributed computing. Yet, most circuit schedulers are designed around an idealized view of the interconnect as either blocking or strictly non-blocking. Practical scalable designs are often rearrangeably non-blocking (RNB), with connections routed through networks of internal $2\times2$ switches. This changes the scheduling problem fundamentally: establishing a new connection can force existing connections to be rerouted, trigger state changes across multiple internal switches, and impose reconfiguration delay on otherwise unrelated traffic. We present Tetris, a circuit scheduling algorithm for RNB photonic interconnects. Tetris builds on two observations. First, All-to-All demands are often not doubly stochastic, leaving a small number of endpoints as communication bottlenecks. Second, reconfiguration delay can be large enough to change which connection should be scheduled next. Tetris prioritizes bottleneck endpoints using their remaining communication and reconfiguration work, while selecting and routing matchings to preserve ongoing connections whenever possible. Matchings ensure progress, but connections are scheduled independently, allowing completed connections to be replaced without matching-wide barriers and incurring delay only at switches whose states change. Our simulation and hardware-emulation results show that Tetris reduces All-to-All demand completion time by up to $6.6$x over Birkhoff--von Neumann-based scheduling and by $30$% over Sunflow. More broadly, RNB interconnects raise new questions in multi-tenant scheduling and routing for partial reconfiguration, which we discuss at the end of the paper.

Abstract: In the online metric matching problem, we have $n$ servers with known locations in some metric space. Requests arrive one-by-one at certain locations, and upon arrival a request must be matched to a server that was not matched to a previous request. The goal is to minimize the matching cost. For randomized algorithms with an oblivious adversary, the best known competitive ratio is obtained by embedding the metric space into an HST, and then solving the problem in the setting where the metric space is defined by the HST. Bansal et al. (Algorithmica, 2014) introduced a framework for online metric matching where one develops an algorithm in a restricted reassignment model, and then transforms this into a true online algorithm. Using this framework, they obtained an expected competitive ratio of $O(\log n)$ for HSTs; this also gives the best known competitive ratio of $O(\log^2 n)$ for general metrics. In this paper, we revisit this framework with the aim of developing new algorithms. For HSTs where each node has at most $Δ$ children, we develop an algorithm via this framework with an expected competitive ratio of $O((\log\log Δ) \cdot \log Δ)$. In particular, this ratio is independent of $n$, the number of servers/requests. It is near-optimal, as the expected competitive ratio of any algorithm is $Ω(\log Δ)$.

Abstract: The prize-collecting traveling salesperson problem is a variant of the metric traveling salesperson problem in which vertices may be left unvisited by paying their associated penalties. The objective is to minimize the length of the tour plus the total penalty of the unvisited vertices. Blauth, Klein, and Nägele gave the previously best-known LP-relative $1.599$-approximation. We show that a simpler version of their algorithm, obtained by omitting the splitting-off preprocessing before the tree decomposition, has an LP-relative approximation ratio of $1.555761$. The improvement comes from a stronger analysis of the parity-correction step.

Abstract: This study investigates an Aerial-Ground Integrated Heterogeneous network (AGIHN) architecture that combines terrestrial macro base stations and unmanned aerial vehicles (UAVs) serving as aerial base stations to enhance uplink access for macrocell users. To address the complex uplink resource allocation challenge for multiple device-to-device (D2D) communication pairs, we propose a low-complexity Multi-Channel Rate-Fair (MCRF) algorithm. Distinct from traditional exclusive allocation methods, MCRF supports shared reuse, enabling multiple D2D pairs to simultaneously multiplex on the same resource block, thereby significantly improving spectral efficiency. To manage the severe intra-tier interference arising from this non-orthogonal sharing, a heuristic Interference Avoidance (IA) strategy is integrated to ensure the transmission quality of D2D users. The proposed framework jointly optimizes system throughput, user fairness, and energy efficiency without requiring computationally intensive offline training. Simulation results demonstrate distinct performance advantages depending on the reuse mode: Compared to traditional single-channel exclusive reuse schemes, MCRF achieves massive gains, increasing D2D energy efficiency and throughput by approximately 397% and 542%, respectively. Furthermore, relative to multi-channel benchmarks (e.g., MCRR), the proposed algorithm optimizes the efficiency-fairness trade-off, enhancing the fairness index by 7.43% while maintaining a robust fairness score exceeding 0.6 in interference-prone environments.

Abstract: Sixth-generation (6G) wireless systems are envisioned as networks of networks, integrating diverse in-X subnetworks that provide localized, high-performance connectivity. Ensuring reliable communication in dense deployments, such as industrial robots and vehicles, is challenging due to dynamic interference and strict performance requirements. Traditional radio resource management (RRM) methods have limitations, prompting the need for AI-based solutions. In this paper, we address the challenges of dynamic resource allocation and scheduling in 6G in-X subnetworks supporting applications with heterogeneous characteristics by proposing a novel framework that combines Multi-Agent Reinforcement Learning (MARL), Federated Learning (FL), and Explainable AI (XAI). Our solution is designed to improve the reliability, robustness, and transparency of resource management and intra-subnetwork scheduling while ensuring data privacy and fairness across multiple co-existing subnetworks. Unlike existing works, our approach considers a realistic scenario with multiple devices per subnetwork, thereby offering a more comprehensive and scalable solution. The proposed explainable RL framework enables agents to collaboratively optimize channel allocation and scheduling without the need to share raw data, preserving the privacy of each participating subnetwork. Extensive simulations based on 3GPP scenarios demonstrate the effectiveness of our approach, showing significant improvements in performance, and transparency over existing solutions.

Abstract: We study Greedy for online metric matching with $n$ servers and $n$ requests sampled independently and uniformly from $[0,1]^d$. Servers are available initially, and Greedy irrevocably matches each arriving request to its closest available server, incurring a cost of their distance. We prove that Greedy has competitive ratio $O(1)$ for every fixed $d\ne2$, and $Θ(\sqrt{\log n})$ for $d=2$. Previously, constant competitiveness was shown for $d = 1$ [BFP23], and no non-trivial results for this setting were known for higher dimensions. Our proof first analyzes Greedy on the flat torus and then transfers the estimates back to the cube.

Abstract: Intent-driven services envisioned for sixth-generation (6G) edge networks must translate changing requirements into executable contracts while wireless requests continue to arrive. Interpretation consumes part of the same deadline budget as transmission, queueing, and execution. We evaluate Jev as a decision model for this stage, asking whether faster contract activation improves service timeliness while preserving interpretation quality. Contracts specify permitted execution locations, deadlines, and priorities; a numerical scheduler uses them to allocate edge work. The evaluation combines live Jev, DeepSeek, Gemini, and self-hosted Qwen responses with packet-level New Radio simulation, mobility events, shared edge queues, and a real image-reading service. Cached interpretation with numerical scheduling substantially improves completion over direct model-selected placement. With correct interpretation on all evaluated contracts, Jev reduces median decision latency by 22.4% against DeepSeek and 61.9% against Gemini; completion in the modeled update scenarios rises by 3.50 and 8.35 percentage points. A separate comparison with direct-attribute Qwen retains a 53.0% latency reduction and a 4.78-point completion gain. Exchanging recorded model and scheduling waits reproduces the comparator completion summaries for all 12 trajectories in each of two modeled comparisons. In the real image service, Jev retains faster decisions and completes 459 requests correctly and on time, compared with 463 for DeepSeek and 435 for Qwen out of 1,080 each. These findings connect fast intent decisions to timely edge service execution and support using Jev at contract activation, with numerical scheduling adapting placements to current network and computing state.

Abstract: Given a directed graph with positive edge weights and two vertices s,t, a next-to-shortest s-t path is a shortest simple s-t path among those whose length is strictly larger than the shortest-path distance. The problem was introduced by Lalgudi, Papaefthymiou and Potkonjak in 1996; it is NP-hard when zero-weight edges are allowed, and its complexity on positively weighted digraphs remained open for almost three decades until Chen, Wein and Zhang recently gave a polynomial-time algorithm running in O(n^4 m^3 log n) time. We give a substantially faster algorithm within their optimal-middle-segment framework. The core idea is to split the problem into "choosing a prefix" and "completing it". Given a prefix P: s -> A made of shortest-path edges, delete the vertices used by P, forbid leaving A along shortest-path edges, and the best completion is one shortest-path computation. The difficulty lies in choosing P: even for a fixed A, deciding whether some shortest prefix admits a completion is NP-complete. We do not solve these fixed-A subproblems one by one. Fix any globally optimal next-to-shortest path; its middle segment induces a boundary edge x -> c in the shortest-path DAG. For the correct triple (A,B,x), the optimal path certifies c as a feasible next hop, and we prove that every feasible next hop that is not earlier than c in a topological order can be combined with the same middle segment into another globally optimal path. Hence only the feasible next hop of maximum topological index is kept per triple, giving O(n^3) representatives, all generated by a two-dimensional DAG dynamic program with a local reward. The total running time is O(n^3 (m + n log n)), and O(n^3 m) on unweighted graphs. The proof rests on an uncrossing lemma: the last intersection between a reference prefix and the candidate's partner suffix can always be moved strictly earlier, which cannot go on forever.

Abstract: We introduce a low-recourse rounding paradigm for packing problems in fully dynamic settings, which we name Dynamic Contention Resolution Schemes (DCRSs). These are dynamic analogs of (Online) Contention Resolution Schemes (or (O)CRSs) for low-recourse dynamic optimization and offer a variety of benefits. Similarly to their offline and online counterparts, DCRSs for different constraints can be combined to obtain DCRSs for the constraints' intersection. Furthermore, together with the Positive Body Chasing framework of Bhattacharya, Buchbinder, Levin, and Saranurak [FOCS 2023], DCRSs imply competitive recourse algorithms for fully dynamic packing problems with submodular objectives: these are algorithms that, for any input sequence, incur recourse that is itself competitive with the best possible recourse for that sequence. We show the existence of $Ω(1)$-balanced and $O(\log \mathrm{rank})$-recourse DCRSs for matroid constraints, and $Ω(1)$-balanced/$O(1)$-recourse DCRSs for matching and knapsack constraints. In particular, these yield the first non-trivial recourse bound for fully dynamic knapsack, as well as the first competitive-recourse algorithm for non-bipartite matching, and both of these apply even to monotone submodular objectives. Beyond our particular results, we view the DCRS framework as a principled step towards mechanizing the relax-and-round paradigm of approximation algorithms in the context of dynamic optimization.

Abstract: Motivated by applications in fairness and foundational questions, we consider the problem of maximizing a monotone submodular function $f\colon 2^E \rightarrow \mathbb{R}_+$ over maximum cardinality sets in the intersection of two matroids on a common ground set $E$. An important special case is submodular perfect matching in bipartite graphs. Prior to this work, its approximability was poorly understood with only constant inapproximability known, despite not even a $\frac{1}{o(\sqrt{|E|})}$-approximation being known. Even when allowing to violate the cardinality constraint slightly, only a bicriteria approximation with a significant loss in the objective was known. Here, we obtain two results. First, we show that, within constant factors, the problem is approximation-equivalent to Submodular Orienteering in directed graphs. This yields an $Ω(1 / \log |E|)$-approximation in quasi-polynomial time together with an almost-matching hardness result. Second, we obtain an improved polynomial-time bicriteria approximation via a local search framework. More precisely, if $f(T^*)$ is the largest submodular value of a common independent set in both matroids of size at least $K$, we find a common independent set $T$ such that $|T| \geq (1 - ε) K$ and $f(T) \geq (1/2 - ε) f(T^*)$. In contrast, previous work only guarantees a value of $Ω(ε) f(T^*)$ while ensuring that $|T| \geq (1 - ε) K$.

Abstract: Artificial Intelligence (AI) is becoming a fundamental design principle of future AI-native communication networks, enabling autonomous resource management, adaptive control, and zero-touch network operation. While current AI-native architectures increasingly embed intelligence across network functions, they provide little guidance on how optimisation knowledge should be systematically generated, transferred, and exploited by AI models. This paper argues that the Learning-to-Optimize (L2O) represents the missing architectural layer between optimisation and AI-native intelligence. Rather than viewing optimisation merely as an online decision engine, the proposed paradigm redefines optimisation algorithms as offline knowledge generators that produce high-quality supervisory information for neural surrogate models. The resulting models inherit optimisation expertise while enabling low-latency runtime inference suitable for dynamic network environments. A generic four-stage L2O workflow is introduced, comprising optimisation, knowledge generation, surrogate learning, and runtime inference. Unlike existing Learning-to-Optimize approaches, which primarily focus on algorithm acceleration, the proposed framework establishes L2O as an architectural abstraction applicable across heterogeneous communication and computing systems. The proposed paradigm is illustrated by an NR-V2X relay-selection problem, in which optimisation-generated solutions from a Mixed-Integer Linear Programming (MILP) solver are used to train a Graph Neural Network that can reproduce near-optimal decisions in real time. The presented perspective positions Learning-to-Optimize as a key architectural enabler for future AI-native networks.

Abstract: The weighted $k$-matroid intersection problem asks for a maximum-weight set that is independent in each of $k$ matroids on a common ground set. The natural LP relaxation optimizes over the intersection of the $k$ matroid independent set polytopes. It is conjectured that this LP has integrality gap at most $k-1$. The conjecture is known for $k\le3$, but for $k\ge4$ the best general upper bound was $k$. We improve this bound to $k-1+1/k$. More generally, we prove that the natural LP of a $p$-matchoid has integrality gap at most $p-1+1/p$, with a deterministic LP-relative algorithm attaining the same factor. The matchoid extension resolves the $p$-matchoid part of a conjecture of Lee, Sviridenko, and Vondrák; projective planes give explicit tight instances whenever one of order $p-1$ exists.

Abstract: We consider the online carpooling problem, where edges arrive online and must be oriented immediately while keeping the discrepancy between the indegree and outdegree at each vertex small. We prove that the natural Greedy algorithm incurs discrepancy $O(\min\{T^{1/3},n\})$ after $T$ arrivals. This resolves a question of Ajtai et al., who showed that any deterministic algorithm must incur $Ω(\min\{T^{1/3},n\})$ discrepancy, and gave an algorithm with $O(\min\{T^{1/2},n\})$ discrepancy. We also show a similar square-root to cube-root improvement in the stochastic setting, where $O(n)$ edges are sampled independently from an underlying $n$-vertex graph $G$. Formally, we show an $O((\log n)^{1/3})$ bound for random arrivals from any $Δ$-regular graph $G$. When $Δ= Ω((\log n)^3)$, we show the more refined bound of $O((\log n/\log Δ)^{1/3}+\log\log n)$ on the discrepancy. We show that the cube-root term in the previous bound is essential, while the $\log\log n$ term is already known to be necessary for random arrivals from complete graphs. The previous upper bounds here were $O((\log n)^{1/2})$, which follow from the breakthrough works on online discrepancy due to Kulkarni, Reis, and Rothvoss, and Aden-Ali. Our techniques for proving such cube-root-type bounds may be of independent interest, as the standard quadratic-potential and subgaussian analyses underlying the previous general bounds appear inherently unable to go below square-root-type guarantees.

Abstract: The reliance on scarce and expensive accelerators such as GPUs and TPUs in modern datacenters places unprecedented demands on backend infrastructure. For workloads characterized by heterogeneous service times and complex multi-stage processing, such as Generative AI, conventional load balancing techniques are often inadequate, relying heavily on costly overprovisioning to maintain service level objectives. This paper introduces DLB, the Distributed Load Balancer, a novel system designed to minimize end-to-end user latency for large-scale, heterogeneous workloads. DLB employs a scalable, distributed design with peer-to-peer probing to maintain real-time visibility into server capacity across large-scale, geographically distributed infrastructure. The system continuously learns latency models to estimate the latency impact of routing decisions, allowing it to effectively manage heterogeneous hardware and diverse model architectures. We provide a novel theoretical analysis of our routing algorithms that establishes their stability and global performance guarantees over time. We also evaluate DLB through extensive simulations, which show substantial gains compared to state-of-the-art load balancing algorithms. Finally, following a 22-month deployment of DLB at Google, where it facilitates large-scale Generative AI inference for thousands of different machine learning models and millions of requests per second, we detail the design choices and practical experiences gained from the system in production. Analysis of production migrations demonstrates that DLB yields statistically significant latency reductions compared to the legacy baseline, including a 17\% decrease in median latency and a 13\% decrease at the p95 tail.

Abstract: The goal-oriented communication paradigm is poised to enable novel real-time applications by easing the burden on communication networks while still delivering task-relevant information. However, efforts so far have focused on the encoding problem, while the design of medium access schemes is still in the early stages of development, especially when connectivity is to be provided to a massive number of devices, e.g., for remote monitoring. In this respect, existing goal-oriented approaches are often centralized or based on simplified underlying mechanisms, requiring unrealistic assumptions. In this work, we present the Goal-oriented Irregular Repetition Slotted ALOHA (GO-IRSA) scheme, which combines modern random access techniques with belief-based policies. GO-IRSA does not impose significant computing loads on the sensors or require frequent feedback, and it can reduce the average and worst-case error of the estimate of a distributed Wiener process by over 30% with respect to the optimal centralized solution in a network with thousands of sensors, and is robust to imperfect interference cancellation and inaccurate process knowledge.

Abstract: Modern smart vehicles leverage multimodal sensors, ranging from high-bandwidth vision systems to low-rate physiological monitors, to provide personalized in-cabin services. However, integrating high-fidelity multimodal fusion with collaborative training is often hindered by the heterogeneous and time-varying Quality of Service (QoS) constraints of vehicular networks. Standard Federated Learning (FL) approaches enforce rigid synchronous rounds that fail to account for these resource asymmetries, leading to safety-critical timing violations and energy exhaustion. In this paper, we propose FedQoS, a novel asynchronous, event-triggered FL framework that decouples local computation from global communication via a two-phase gating mechanism. First, we introduce a resource-aware training gate that initializes local learning only when sensing buffers and energy reserves meet safety thresholds, preventing ML tasks from compromising core vehicle mobility. Second, a QoS-aware transmission policy gates uplink updates based on an efficiency score that balances model novelty against instantaneous latency and energy costs. Locally, clients optimize an objective featuring a staleness-aware proximal term that dynamically adjusts the global anchor strength based on update age. Extensive experiments on multimodal vehicular datasets demonstrate that FedQoS achieves competitive personalized accuracy with only marginal performance loss compared to FedAvg, while substantially reducing QoS violations, cutting communication overhead by 76.7\%, and lowering latency cost by 26.0\%, demonstrating a highly favorable accuracy and efficiency balance for real-world vehicular deployments.

Abstract: The Antibandwidth and Cyclic Antibandwidth problems are NP-hard graph labeling problems that aim to maximize the minimum (cyclic) distance between labels assigned to adjacent vertices. Extensive research on these problems has resulted in a variety of mathematical formulations and computational approaches. However, their minimum span perspective, in which a prescribed minimum (cyclic) distance is fixed and the objective is to minimize the label span, has received comparatively little attention. In this paper, we consider this complementary perspective by introducing the Minimum Span Antibandwidth/Cyclic Antibandwidth Labeling (MSABL/MSCABL) problems and developing a unified Boolean Satisfiability (SAT)-based framework for solving them. The SAT-based framework formulates MSABL/MSCABL as a sequence of decision problems and exploits their monotonicity to accelerate the search process. We also consider two SAT solving strategies, parallel and incremental SAT solving: the former examines multiple candidate spans concurrently, while the latter reuses a single SAT instance while progressively restricting the label domain. The proposed approaches are evaluated on benchmark instances from the Harwell-Boeing Sparse Matrix Collection and compared with CPLEXCP, CPLEXMIP, and Gurobi. The results show that SAT-based approaches are highly competitive in solution quality, with the parallel approach performing best overall for MSCABL and the incremental approach for MSABL. With the no-hole constraint, they remain competitive with CPLEXCP and significantly outperform CPLEXMIP and Gurobi, particularly for MSCABL. These results demonstrate the effectiveness of SAT solving as an exact approach for MSABL and MSCABL.

Abstract: Communication-driven multi-view sensing relies on routine communication transmissions for sensing acquisition, while the resulting sensing data at distributed devices must be uploaded to an edge server under limited communication resources. This creates a unique coupling between sensing acquisition and edge inference: the communication interval determines the source information, whereas the uplink condition determines how much information can be delivered to the server for sensing inference. To account for this coupling, we propose a source entropy-guided adaptive transmission framework. Specifically, we characterize the entropy of packet-triggered channel state information (CSI) as a function of the communication interval using a multi-output Gaussian process. The resulting analytical bound is compared with the available bit budget, determined by the transmission rate and latency requirement, to select between original-data and task-oriented transmission. For task-oriented transmission, we formulate the communication-constrained inference problem based on the information bottleneck and decompose it into adaptive distributed encoding and multi-view inference (ADE-MI), which avoids alternating optimization between the devices and the edge server. Experiments on the Widar3.0 multi-view CSI gesture recognition dataset show that the analytical bound closely follows the normalizing-flow numerical estimate, while ADE-MI outperforms task-oriented benchmarks under the same bit budget and the proposed framework further improves recognition accuracy under time-varying channels.

Abstract: The strong matroid secretary conjecture asserts that every matroid admits a $1/e$-competitive secretary algorithm, matching the classical single-choice guarantee. We formulate a finite linear program whose value is the optimal ordinal competitive ratio of any fixed matroid; for all matroids of positive rank on seven elements and nearly all on eight, this value exceeds $1/e$. The same computations suggested that the optimal ratio is monotone under truncation of the matroid; we prove this for uniform matroids, where the ratio is strictly increasing in the rank, and refute it for a graphic matroid. Guided by this evidence, we prove the conjecture for every linear matroid, a class that includes graphic matroids, regular matroids, laminar matroids, and gammoids, giving a $1/e$-competitive ordinal secretary algorithm. The algorithm maintains bounds on the expected intersection dimension of the accepted span with every ambient subspace. Uncrossing and separation show that these bounds can be preserved while admitting each current greedy-basis element with a prescribed probability and the construction uses finite linear programs. For every matroid, we also give a single-sample prophet algorithm with competitive ratio $1/2$ in any fixed arrival order independent of the samples and values. Its output, including the selected values, has exactly the law of an independent fair thinning of an optimum from a fresh product draw. The algorithm uses $O(n^2)$ independence queries on $n$ elements. Both constants are tight in their respective models. We also give a self-contained black-box reduction that converts a single-sample prophet ratio $α$ into a secretary ratio $α^2/16$, preserving polynomial running time. Our single-sample algorithm consequently yields a $1/64$-competitive ordinal secretary algorithm for arbitrary matroids.

Abstract: The demand matching problem generalizes both the knapsack problem and the $b$-matching problem. In this problem, each edge of a graph has a demand and a weight, and each vertex has a capacity. The goal is to find a maximum weight subset of edges such that, at each vertex, the total demand of the incident selected edges does not exceed the vertex capacity. Parekh [IPCO 2011] proved that, if each edge is individually feasible, the natural LP relaxation for demand matching has integrality gap at most $3$, yielding a $3$-approximation algorithm. This bound is tight for the natural LP relaxation, matching the lower bound of Shepherd and Vetta [Math. Oper. Res. 2007]. We present a randomized $(3/2 + \sqrt{2} + \varepsilon) \approx (2.914 + \varepsilon)$-approximation algorithm for the demand matching problem for every $\varepsilon > 0$, giving the first approximation ratio strictly better than $3$. For bipartite graphs, we obtain a randomized $(2 + \varepsilon)$-approximation algorithm for every $\varepsilon > 0$. Both algorithms run in time polynomial in $1/\varepsilon$ and the input length. Our algorithms use a strengthened LP relaxation based on intersecting the integral knapsack polytopes associated with the vertices, together with a multiple-choice generalization. As a key ingredient, we prove the existence of a $(q, 1/(1+q))$-balanced contention resolution scheme for the integral knapsack polytope for every $q \in [0, 1]$, which may be of independent interest. The balance guarantee $1/(1+q)$ is tight in the worst case over all knapsack instances.

Abstract: The matroid secretary problem asks an online algorithm to select a high-weight independent set from elements arriving in uniformly random order, with immediate and irrevocable decisions. Singla (2026) recently gave a $4$-competitive algorithm for arbitrary matroids using only the number of elements and independence queries on already-arrived elements. Following his approach, we obtain an improved competitive ratio of $2+\sqrt3\approx3.7321$ in the same information model. Our algorithm accepts every element of a fixed canonical optimum with probability at least $2-\sqrt3$ and uses $O(n^2)$ independence queries. The algorithm modifies Singla's reversible reference process by retaining a randomly chosen part of the sample as a reserve whose membership in the reference greedy solution is not frozen. Balancing the remaining sample and post-sample elements preserves reversibility and allows an exact calculation of the probability that an exchange partner blocks a target element. The resulting guarantee has a direct analytic proof.

Abstract: The generalized switch is a highly flexible queueing model, covering multiclass, multiserver, and multiresource queueing systems as well as a wide variety of stochastic networks. Although many scheduling policies have been developed for this model, they almost entirely address unknown job duration settings. How to optimally use known job durations in the generalized switch has remained open. Moreover, optimizing mean response time remains open in both settings. We introduce the first policy to guarantee heavy-traffic optimal mean response time in the generalized switch, our Smallest Equalizing Bucket (SEB) policy. The key challenge in designing an optimal scheduling policy is that we must simultaneously prioritize small jobs and also minimize resource waste, all while fitting within the generalized switch's service options. SEB overcomes this challenge by grouping jobs into duration-based buckets and enforcing an "equalizing" service structure that keeps each bucket balanced while still prioritizing the smallest jobs. We prove SEB's heavy-traffic optimality. Simulations further confirm the effectiveness of SEB-inspired heuristics.

Abstract: Efficient physical resource block (PRB) allocation in 5G networks requires accurate demand forecasting. Conventional methods minimize symmetric error metrics (MAE, RMSE), ignoring the operational cost asymmetry where under-provisioning (service degradation) is far costlier than over-provisioning (wasted capacity). We propose a goal-oriented probabilistic forecasting framework that aligns model training with the operator's decision-making objectives. Specifically, we train DeepAR and Temporal Fusion Transformer (TFT) models using the Pinball Loss function and derive the optimal allocation quantile from the operator's cost matrix. Evaluation on a real beam-level 5G traffic dataset shows that the proposed approach reduces operational cost compared to MSE-trained baselines while maintaining calibrated uncertainty estimates. The framework enables dynamic PRB allocation that explicitly balances service reliability against resource efficiency.

Abstract: A finite structural characterization of the $U$-user multiuser channel-capacity region appears here. This region relies upon three concepts: (i) subset-based message atomization, (ii) synchronized receiver chain-rule/Fano reduction, and (iii) successive-decoding achievability via a finite-super-symbol closure. The resulting region is a finite union of order-indexed polytopes parameterized by the synchronized minimum mutual-information vector $\mathcal{I}_{\min}$. The framework removes auxiliary-random-variable proliferation and makes explicit the finite geometric structure underlying general multiuser converses, with the interference channel providing the primary illustration. For the linear matrix Gaussian multiuser-channel special case under per-user trace covariance constraints, Gaussian signaling is capacity-region-achieving within this framework. Also shown is that maximum rate sum for any Gaussian multiple-user-channel derives from simple iterative procedures.

Abstract: We extend the analysis of strong aggregation to general compatibility graphs, focusing on item counts rather than positions, and exploring generalized greedy matching disciplines. We prove that under a condition of automorphism-based transition consistency, the associated Markov chain is strongly aggregable for an arbitrary graph with a non-trivial automorphism group. Furthermore, we extend our analysis to non-greedy matching disciplines, distinguishing scenarios where compatible items can or cannot coexist within the same state. This result is illustrated with a simple compatibility graph with a rich automorphism structure: the odd rings. For all scenarios, we investigate the strong aggregation properties of the resulting Markov chains. This work enhances the theoretical understanding of lumpability in stochastic matching models and provides a foundation for analyzing complex graph structures.

Abstract: The $k$-server conjecture states that a deterministic online algorithm can achieve competitive ratio $k$ on every metric space. We prove the conjecture. Specifically, we show that the work function algorithm satisfies it. Our proof uses a natural algebraic representation of the work function as a matrix, which encodes all feasible paths to reach a configuration. In this representation, the minimum and addition operations arising in the definition of optimal costs correspond to addition and multiplication of formal expressions, and each work function value corresponds to the determinant of $k$ columns of the matrix. A request arrival updates the representation via a change of basis and row replacement. The amortized analysis is based on a potential function defined in terms of a larger matrix whose coordinates are pairs of coordinates of the original matrix representation.

Abstract: We study the weighted feedback vertex set problem in tournaments. For every fixed integer $k\geq 2$, we give a deterministic $(2+1/k)$-approximation algorithm with running time $n^{2^{O(k)}}$, apart from polynomial dependence on the encoding length of the weights. Consequently, for every fixed $\varepsilon>0$, weighted feedback vertex set in tournaments has a deterministic $(2+\varepsilon)$-approximation running in time $n^{2^{O(1/\varepsilon)}}$. The algorithm combines two ingredients. When the triangle graph of the tournament has bounded clique number, a chain decomposition of its transitive complement yields an exact dynamic program for a maximum-weight transitive subtournament. When the clique number is large, a structural theorem for triangle graphs supplies a constant-size strongly good cost vector. A local-ratio reduction with this cost vector gives the claimed guarantee. As a by-product, the dynamic program solves weighted feedback vertex set exactly in $\mathcal B_7$-free tournaments in time $O(n^7)$, where $\mathcal B_7$ is the family of seven-vertex tournaments with feedback vertex set number at least three.

Abstract: Parallel batch-dynamic trees are a fundamental building block in recent theoretical and practical advances in dynamic graph algorithms. However, all existing parallel batch-dynamic tree data structures, including Euler tour trees, UFO trees, topology trees, and rake-compress trees, are all significantly outperformed in the sequential setting by link-cut trees, which have been the sequential state-of-the-art for over 40 years. Despite their excellent performance in the sequential setting, designing efficient batch-parallel link-cut trees has remained a major open problem. In this paper, we close this gap by introducing MOJOS, a unified framework for theoretically- and practically-efficient parallel batch-dynamic trees. We exploit the fact that both Euler tour trees and link-cut trees rely on a common dynamic sequence abstraction that supports splitting and joining. We introduce a new batch-dynamic sequence built using treaps that achieves optimal work and depth, and outperforms existing parallel skip list and treap implementations for batch updates, queries, and memory usage. With MOJOS, we develop a new batch-parallel Euler tour tree algorithm that outperforms prior batch-dynamic tree implementations supporting subtree queries. Unlike prior batch-parallel Euler tour trees which rely on skip list's ability to represent cyclic sequences, MOJOS allows any batch-dynamic sequence data structure to be used as a drop-in replacement. Finally, we develop the first theoretically-efficient batch-parallel link-cut tree, which is also the first batch-dynamic data structure supporting path queries to achieve $O(\log n)$ depth for batch updates in the binary-forking model. Our link-cut tree implementation outperforms all known parallel batch-dynamic tree data structures supporting path queries.

Abstract: A communication system may convey urgent information through a fast physical stream and more specific information through a slower material stream. In several biological and engineered settings, however, the fast process also changes the transport law of the slow one. We study this architecture under a shared resource constraint, with a strictly increasing concave fast-channel capacity--cost function and a deadline-constrained slow molecular channel. We first characterize the capacity region under separated message routing and message-independent operating-point schedules, and identify the marginal criterion for complementarity rather than competition between the streams. For one-dimensional drift diffusion, we prove that arrival probability before a deadline is strictly log-concave in Péclet number. For a distinguishable-token deadline-erasure channel, any increasing concave transport-actuation law then yields an exact single-crossing theorem: complementarity exists if and only if an initial transport-assistance elasticity exceeds one, the transition is unique when it exists, and the decreasing allocation branch remains the Pareto boundary after convexification. For positive baseline drift and sufficiently strong coupling, a unique critical normalized deadline determines when complementarity disappears. Short- and long-deadline limits clarify the associated temporal regimes. Numerical examples for a finite-frame LTI-Poisson slow channel exhibit analogous allocation behavior with counting noise and intersymbol interference.

Abstract: When performing parallel data transmission through a network using multiple paths, it is practically important to minimize the maximum transmission time among the selected paths. This study addresses an online problem in which $k$ paths from an origin vertex to a destination vertex must be selected at each time step within a network represented as a directed graph. Here, the number of paths going through each edge in each parallel data transmission is limited to its capacity, and the time required for transmission is determined stochastically. We formulate the semi-bandit problem of selecting a set of paths to minimize the maximum traversal time among the selected paths and propose an algorithm to solve it.

Abstract: We resolve the matroid secretary conjecture, giving an online algorithm that accepts each element of the offline optimum with probability at least $1/4$. The algorithm only needs the number of elements in advance and independence-oracle access to subsets of already-arrived elements; it does not need to know the matroid upfront.

Abstract: Temporal Path Cover (TPC) and Temporally Disjoint Path Cover (TDPC) ask for minimum-cardinality covers of a temporal digraph by temporal paths, with TDPC additionally requiring pairwise temporal disjointness. Cioni et al. proved both problems NP-hard on temporal DAGs whose underlying undirected graph has vertex-cover number three and left the vertex-cover-two case open. We resolve this question affirmatively for both problems. Using polynomial-time reductions from Distinct Numerical Matching with Target Sums, we show that TPC and TDPC are NP-complete already when the underlying undirected graph has vertex-cover number exactly two. For TPC, this yields an exact vertex-cover threshold: polynomial-time solvability at vertex-cover number at most one and NP-completeness at two. For TDPC, we further study the boundary case of temporal oriented stars. A reuse-normalization argument reduces optimum solutions to leaf-unique two-edge merges. If either the incoming or outgoing side is single-label, the optimum remains polynomial-time computable even when the opposite side is multi-label. We also introduce a span parameter for feasible merge realizations and prove that any feasible family of k merges forces a realization of span at least 2k-2. Hence TDPC on temporal oriented stars is in XP parameterized by maximum span, and is polynomial-time solvable for every fixed span bound. The unrestricted multi-label star case remains open.

Abstract: This paper studies joint sampling, route activation, and preemption control over $N$ heterogeneous transmission routes under a long-run objective combining Age of Information (AoI) with sampling and transmission costs. We formulate the problem as an average-cost impulse-control model, derive a vector-form integral average-cost optimality equation over a hybrid state space, and establish structural reductions on the state. We consider a two-route case and compute optimized policies using discretized policy iteration. Surprisingly, the results show that preemption can reverse routing preferences: the optimized policy may exclusively use a route with both a larger mean delay and a larger delay variance while avoiding the seemingly superior route. Relative to baselines that do not allow preemption, the proposed policy reduces average AoI by up to $96\%$.

Abstract: We study switching regret in adversarial multi-armed bandits, where the learner competes with an arm sequence that changes at most $S$ times. When $S$ is known, an optimal expected regret of $\widetilde{\mathcal{O}}(\sqrt{(S+1)KT})$ is obtainable [Auer et al., 2002]. However, when $S$ is unknown, Marinov and Zimmert [2021] show that this guarantee is impossible under an adaptive adversary. In this paper, we show that a single algorithm achieves $\widetilde{\mathcal{O}}(\sqrt{(S+1)KT})$ expected regret for every $S$ against an oblivious adversary, resolving an open problem of Auer et al. [2019b]. Our algorithm combines a fixed-share learner initialized with a small learning rate and dyadic-interval subroutines that search for local improvements using randomized learning rates and implicit exploration. Importantly, a non-uniform prior favors following the main learner, keeping the cost of maintaining many subroutines small. When the subroutines accumulate sufficient improvement over the main learner, its learning rate doubles, allowing adaptation to the unknown number of comparator switches $S$.

Abstract: 6G is expected to push ultra-reliable low-latency communication (URLLC) toward stringent residual-error targets for mission-critical services, where undetected errors and erasures carry fundamentally different costs. Block error rate (BLER) conflates block confusions (undetected errors) and block erasures, which have fundamentally different impacts on system reliability. This paper extends the confusion and erasure analysis of error-bounded decoders to square quadrature amplitude modulation (QAM) constellations in the finite blocklength (FBL) regime. To handle QAM's heterogeneous symbol energies - which make the per-pair Euclidean distance a distribution rather than a single value - we derive analytical lower and upper bounds on the block confusion rate by, respectively, collapsing this distribution to its root-mean-square (RMS) distance and averaging the pairwise confusion over it. These bounds are proven to be monotonically decreasing in both the average symbol energy and the blocklength, with the decrease rate governed by the constellation order. Numerical results confirm that as the signal-to-noise ratio (SNR) or redundancy increases, the confusion rate falls many orders of magnitude below the reliability target, leaving detectable erasures as the dominant residual error.

Abstract: Marginal-contribution pricing makes the social objective an exact potential, but does not ensure that every stable assignment is efficient. We study indivisible clients with heterogeneous workloads, arbitrary nonnegative assignment costs, and private eligibility menus over a fixed number of shared servers and optional local execution. Each server's social cost is its occupancy multiplied by its aggregate workload and a server-specific coefficient. For every fixed server cap $M$, we prove that the price of anarchy over this class is $Θ_M(κ^{1-2^{-M}})$ as the workload-ratio cap $κ$ grows. The upper bound applies to every equilibrium and every feasible comparison, without an acyclic-comparison or strongly-connected-component restriction. Its proof combines a common-multiplier certificate, a source-weighted residual inequality and an ordered moment recurrence. A matching chain family has a realization by mobile unmanned aerial vehicle (UAV) clients and fixed ground servers, with positive altitude, positive-width coverage and an explicitly paid wireless baseline. We prove exact waypoint elimination and give an input-computable component refinement. Scheduling and congestion identities delimit which established bounds transfer. Exact enumeration of 2,800 synthetic games identifies inefficient equilibria, while 270 primary-parameterized synthetic instance-budget records evaluate incremental latency relative to a feasible multistart reference. Tightness concerns the heterogeneity exponent for fixed $M$, not matching leading constants or measured frequency of the worst-case configurations.

Abstract: This work considers multi-agent coordination with arbitrary information networks among the agents using a game-theoretic approach. A system designer aims to assign local utility functions to the agents to guide their actions toward a desired system objective. The performance of the assigned local utilities is measured by the well known pure price of anarchy (pPoA) metric that equals the ratio of the system objective at the worst pure Nash equilibrium of the corresponding game to the optimal system objective. Our aim is to derive the utility functions which optimize the pPoA-based performance guarantees for any given information network and system objective. We develop a linear program that derives the optimal pPoA for any arbitrary information network and arbitrary system objective. Our work is the first to solve optimal utility design for arbitrary networks; our techniques generalize previous approaches which considered only the full-information setting. For supermodular objective functions, we prove that counterintuitively, a fully communication-denied utility design is optimal irrespective of the original information network. For submodular system objectives, an exhaustive numerical analysis suggests that the optimal utility design is robust to communication failures even for this case. When the system objective is weighted maximum coverage, the marginal contribution utility design provably optimizes the pPoA for a wide variety of information networks of interest.

Abstract: Convex Optimization with Nested Evolving Feasible Sets (CONES)} was introduced in \cite{CONESVaze} where the objective function \(f\) remains fixed but the feasible region evolves over time as a nested sequence \(S_1 \supseteq S_2 \supseteq \cdots \supseteq S_T\). The goal of an online algorithm is to simultaneously minimize the regret with respect to hindsight static optimal benchmark and the total movement cost $M_\cA(T)$ while ensuring feasibility at all times. CONES is an optimization-oriented generalization of the well-known \emph{nested convex body chasing} (NCBC). In this paper, we extend CONES to allow for loss functions $f_t'$s to also change over time. When all loss functions are convex, we show that the projected proximal algorithm achieves $O(T^{1-β}), O(T^β)$ simultaneous regret and movement cost, respectively, for any $β\in [0,1)$, over a time horizon of $T$. We also show that any {\it weakly adaptive} online algorithm with $O(T^β)$ regret has a movement cost of $Ω\left(T^{\frac{1-β}{2}}\right)$ for any $β\in [0,1)$. When all loss functions are strongly convex, we show that the projected proximal algorithm simultaneously achieves $O(1)$ regret and a movement cost of $O(\log T)$. To complement this, we show that any online algorithm with sublinear {\it anytime} regret has a movement cost of $Ω\left(\log T\right)$.

Abstract: This paper studies weighted decoding-delay minimization for multiple RLNC-coded message streams that compete for finite processing capacity at a destination. Packet arrivals are exogenous, while the scheduler only determines the processing order of packets already available at the destination. A trace-conditioned offline scheduling formulation shows that a batch-release subclass is strongly NP-hard even with a single processing unit. Message-Aware Innovation-Deficit Scheduling (MAIDS) is then developed to prioritize each serviceable message according to its weight and remaining decoding deficit. For a single processing unit, MAIDS is shown to be exactly optimal under nonblocking progressive arrivals with equal weights and under common activation with arbitrary positive weights, while the unrestricted weighted online problem admits no universal deterministic $O(1)$ competitive ratio. Simulation results on streaming and batch benchmarks show that MAIDS consistently reduces weighted decoding delay relative to the tested baselines, remains close to the offline optimum on average, and recovers the predicted exact performance boundaries.

Abstract: Rate adaptation is a crucial mechanism in IEEE 802.11 networks and next-generation cellular systems. Since the time scale for rate adaptation is typically much shorter than that for user association and scheduling, we investigate a joint design of wireless user association and scheduling and rate adaptation across different time scales to maximize cumulative network throughput while ensuring desired fairness among users. We develop a MaxWeight-type user association and scheduling algorithm that integrates virtual queues -- tracking each user's scheduling debt to maintain fairness -- and Upper Confidence Bound (UCB) estimates in its weight measure. Each selected user then employs the UCB algorithm for rate adaptation on a short time scale. Our theoretical findings reveal that the proposed algorithm achieves cumulative regret that grows with the square root of the time horizon up to a logarithmic factor and results in zero cumulative fairness violation after a certain number of time frames. Furthermore, since the MaxWeight-type algorithm involves evaluating all the feasible schedules that can be exponential to the number of users due to the interference constraints, leading to high computational complexity, we introduce a low-complexity alternative utilizing the so-called pick-and-compare (PC) approach. We demonstrate the effectiveness of both algorithms through simulations based on real-world data traces.

Abstract: The fixed-charge network flow problem (FCNFP) couples continuous flow allocation with discrete arc-activation decisions, making it a canonical but computationally challenging model for a variety of network design and resource allocation problems. Exact mixed-integer linear programming formulations capture the fixed-charge structure faithfully, but often become difficult to solve on large networks. We propose a scalable continuous-optimization algorithm for large-scale single-commodity FCNFP based on an iteratively reweighted least-squares (IRLS) framework. The method replaces the discontinuous fixed-charge and linear arc cost objective with a smooth nonconvex Lasry--Lions surrogate and solves a sequence of weighted quadratic flow subproblems. Each subproblem is solved by a warm-started dual semismooth Newton method whose Newton systems have weighted graph-Laplacian structure, enabling the use of modern Laplacian solvers. To further improve the discovered arc supports of the challenging underlying combinatorial problem, we also develop an algorithmic variant that incorporates objective-driven perturbation restarts and an anchor-union restricted search that jointly leverages supports discovered by IRLS and by complementary FCNFP heuristics. Computational experiments on 410 benchmark, synthetic, and large-scale instances show that our method obtains the best objective quality among the evaluated scalable FCNFP algorithms, with a mean gap of $1.316\%$ to a time-limited MILP reference and a win-or-tie rate of $90.0\%$ among the non-MILP methods. The results indicate that combining smooth continuous optimization with support-level search is an effective strategy for producing high-quality feasible solutions to large-scale FCNFP.

Abstract: We improve the best known lower bound on the integrality gap for weighted unit-demand multicommodity flow on trees from $1/4$ to $2/5$, improving on the long-standing bound of Chekuri, Mydlarz, and Shepherd~\cite{CMS}. We give the proof in two stages. First, a surprisingly simple packing lemma and an inductive coloring argument give an intermediate bound of $4/11$. We then refine the argument to obtain $2/5$.

Abstract: We study semantic-aware remote estimation of multiple finite-state Markov sources observed by K sensors with overlapping coverage. The sensors share a time-division multiple-access uplink and differ in transmission reliability, delivery delay, and transmission budget. In each slot, the scheduler jointly selects a source and one of its monitoring sensors, or remains idle, to minimize the long-run average cost of actuation error subject to global and per-sensor transmission-frequency constraints. We formulate this problem as a finite average-cost constrained Markov decision process. We show that the transmission resource functions have rank at most K, although the global constraint may still restrict the feasible region. Consequently, the Lagrangian depends only on K effective transmission costs, and an optimal constrained solution can be represented using at most K+1 deterministic policy-recurrent-class components. We further characterize the piecewise-affine concave Lagrangian value function and derive projected dual subgradient ascent over an explicitly bounded multiplier set. Numerical results illustrate the value-function structure, the need for policy randomization in a representative instance, and the interaction between global and per-sensor transmission budgets.

Abstract: The openness and disaggregation of Open radio access network (O-RAN) facilitate resource sharing and coordination across networks, creating new demands for efficient and trustworthy cross-operator scheduling. However, such scheduling is beyond the scope and capability of conventional proportional fair scheduling (PFS), which lacks mechanisms for establishing trust among independent operators. To fulfill this gap, we propose the blockchain-based proportional fair scheduling (BC-PFS) that enables trustworthy inter-network coordination and resource pooling across operators in O-RAN. Specifically, we design four core smart contracts including registration, status reporting, scheduling, and settlement contracts with corresponding Solidity implementations to ensure trustworthy on-chain execution. Theoretically, to evaluate the BC-PFS performance, we develop an analytical framework to derive the user average throughput via both probabilistic and ordinary differential equation (ODE) approaches, and provide a simplified closed-form solution. Based on the above performance assessment, we quantify the pooling effect in O-RAN achieved through trustworthy cross-operator collaboration via BC-PFS, and point out that this effect grows monotonically in both the numbers of operator networks and users. Simulations validate the theoretical analysis and show the performance of the BC-PFS in O-RAN.

Abstract: In this article, we propose an online electronic counter-countermeasure (ECCM) framework designed to conceal the strategic decision-making processes of a cognitive radar (CR) operating under adversarial surveillance. We model the CR under two distinct decision paradigms: a static constrained utility-maximizing behavior and a dynamic expected utility-maximizing behavior. The radar's utility function is modeled via a von Mises--Fisher (vMF) distribution, with the distributional parameter constituting the private information to be protected from adversarial inference. We adopt a distribution privacy framework to conceal this private information and provide formal distribution privacy guarantees for cognition masking. In this work, we develop cognition-hiding algorithms for both static constrained utility maximization (WDPCH-SU), and dynamic expected utility maximization (WDPCH-DU). Through rigorous mathematical analysis, we show that both WDPCH-SU and WDPCH-DU satisfy $ε$-distribution privacy ($ε$-DistP) against inference-based adversarial attacks and present the privacy--performance trade-off bounds, quantifying utility loss (in static setting) and expected utility deviation (in dynamic setting) as functions of $ε$. Numerical results show that WDPCH-SU gives about 15\% improvement in utility loss at maximum privacy compared to the existing methodology while WDPCH-DU achieves a greater reduction in adversarial Fisher information without requiring explicit Fisher information constraints, at a moderate, analytically bounded utility deviation. These results are highly promising in many 6G communication scenarios such as network slicing for automated driving and swarm UAV coordination, where it is essential to keep the resource allocation policy robust against privacy attacks.

Abstract: The ultra-reliable low-latency communication (uRLLC) capability of 5G has created significant opportunities for industrial wireless connectivity, yet widespread use of cellular networks for closed-loop control remains challenging. Closed-loop control requires more than low packet latency and high reliability: cyclic command/feedback exchanges must complete within predictable time bounds despite changing channel conditions, recovery transmissions, mobility, and multi-device contention. This paper introduces Deterministic-5G (Det-5G), a unified radio resource allocation framework for industrial closed-loop control. Det-5G treats the complete bidirectional control cycle as the scheduling object and combines coordinated downlink/uplink allocation, adaptive bundled transmissions, group-oriented downlink communication, and optimized multi-user uplink scheduling over 5G air-interface. Its performance is evaluated through a combination of closed-form analysis and Monte Carlo scheduling experiments, with comparisons against conventional dynamic grant-based scheduling, semi-persistent scheduling/configured grant operation, and fixed proactive repetition. The evaluation shows that Det-5G improves predictability of cycle completion, maintains the target reliability under changing link conditions, and scales more effectively to multi-device control than conventional reactive scheduling, while adapting radio resource use instead of continuously provisioning for the worst case as in fixed repetition. These characteristics make cycle-oriented scheduling a pragmatic solution for reducing the determinism gap that limits the use of 5G for closed-loop control in different verticals, especially as it evolves through 5G-Advanced toward 6G.

Abstract: Generalized Nash Equilibrium Problems (GNEPs) often arise in multi-agent engineering applications that require distributed algorithms. Unlike traditional approaches that enforce consensus on multipliers, our method removes the need to share multipliers, reducing communication and improving privacy. As a result, different initializations can lead to different GNEs, including non-variational ones. We establish convergence under sufficient conditions using an input-to-state stability (ISS) framework.

Abstract: We study constrained online convex optimization with adversarial constraints when constraint values and gradients are observed through unbiased noise. Gaussian value noise of standard deviation $σ$ yields a worst-case lower bound of $Ω(\min\{σ,1\}T/\log^7T)$ on the maximum of expected regret and expected hard violation, even with known gradients. This rules out any jointly $O(T^{1-δ})$ guarantee for fixed $δ>0$ and fixed positive noise level. We therefore study budget violation: the largest cumulative overspend over any window within a fixed horizon. We introduce \LEDGER, which tracks observed net consumption in a nonnegative balance and sets constraint weights before the current feedback noise. Under common feasibility and conditional finite-variance feedback, for fixed problem parameters, \LEDGER\ achieves $O(\sqrt T/V)$ expected regret and $O(\sqrt V\,T^{3/4}+σ\sqrt T)$ expected budget violation for $V\in[T^{-1/2},1]$. This gives the pair $(O(\sqrt T),O(T^{3/4}))$ at $V=1$ and $(O(T^{2/3}),O(T^{2/3}))$ at $V=T^{-1/6}$, without a Slater condition. The budget-focused endpoint $V=T^{-1/2}$ gives $(O(T),O(\sqrt T))$. The same update yields $O((1+E[P_T])\sqrt T/V)$ expected dynamic regret for predictable feasible comparator paths, without common feasibility or path-length input. Its budget bound instead depends on the shortest feasible path, up to a dimension factor.