network schedulers

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: 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.