We study the ordinal secretary problem, where a sequence of candidates arrives in uniformly random order, and the goal is to select the best candidate using only pairwise comparisons. We consider a learning-augmented setting that incorporates potentially erroneous predictions about the best candidate’s position. Our goal is to design online algorithms that balance robustness against poor predictions while having high performance when predictions are accurate. Using an optimization-based framework, we develop deterministic and randomized algorithms that extend classical strategies and explicitly model the trade-off between consistency and robustness. Also, we show the flexibility of our approach by applying it to multiple secretary problem variants, including multiple-choice and rehiring.

We study two online resource allocation problems with reusability in an adversarial setting, namely \problemkRentalFD and \problemkRentalVD. In both problems, a decision-maker manages k identical reusable units and faces a sequence of rental requests over time. We develop theoretically grounded relax-and-round algorithms with provable competitive ratio guarantees for both settings. For \problemkRentalFD, we present an optimal randomized algorithm that achieves the best possible competitive ratio. The algorithm first computes an optimal fractional allocation using a price-based approach, and then applies a novel lossless online rounding scheme to obtain an integral solution. For \problemkRentalVD, we first establish the impossibility of achieving lossless online rounding. We then introduce a limited-correlation rounding technique that treats each unit independently while introducing controlled dependencies across allocation decisions involving the same unit. Combined with a carefully-crafted price-based method for computing the fractional allocation, this approach yields an order-optimal competitive ratio for the variable-duration setting.

This paper introduces a family of learning-augmented algorithms for online knapsack problems that achieve near Pareto-optimal consistency-robustness trade-offs through a simple combination of trusted learning-augmented and worst-case algorithms. Our approach relies on succinct, practical predictions—single values or intervals estimating the minimum value of any item in an offline solution. Additionally, we propose a novel fractional-to-integral conversion procedure, offering new insights for online algorithm design.

We introduce and study the Combinatorial Ski Rental (CSR) problem, which involves multiple items that can be rented or purchased, either individually or in combination. At each time step, a decision-maker must make an irrevocable buy-or-rent decision for items that have not yet been purchased, without knowing the end of the time horizon. We propose a randomized online algorithm, Sorted Optimal Amortized Cost (SOAC), that achieves the optimal competitive ratio. Moreover, SOAC can be extended to address various well-known ski rental variants, including the multi-slope, multi-shop, multi-commodity ski rental and CSR with upgrading problems. Building on the proposed SOAC algorithm, we further develop a learning-augmented algorithm that leverages machine-learned predictions to improve the performance of CSR. This algorithm is capable of recovering or improving upon existing results of learning-augmented algorithms in both the classic ski rental and multi-shop ski rental problems. Experimental results validate our theoretical analysis and demonstrate the advantages of our algorithms over baseline methods for ski rental problems.

We study the online multi-class selection problem with group fairness guarantees, where limited resources must be allocated to sequentially arriving agents. Our work addresses two key limitations in the existing literature. First, we introduce a novel lossless rounding scheme that ensures the integral algorithm achieves the same expected performance as any fractional solution. Second, we explicitly address the challenges introduced by agents who belong to multiple classes. To this end, we develop a randomized algorithm based on a relax-and-round framework. The algorithm first computes a fractional solution using a resource reservation approach---referred to as the *set-aside* mechanism---to enforce fairness across classes. The subsequent rounding step preserves these fairness guarantees without degrading performance. Additionally, we propose a learning-augmented variant that incorporates untrusted machine-learned predictions to better balance fairness and efficiency in practical settings.

The adoption of virtualization in 5G and beyond networks enables the creation of network slices tailored to specific application requirements. While this flexibility is transformative, it introduces new challenges in slice management and orchestration (MANO). AI-based techniques are becoming essential for automated slice MANO. However, their effectiveness relies on the accuracy of network models that map VNF configurations and resource allocations to slice performance. Previous approaches, including simulations, control theory, and machine learning, face limitations such as high computational complexity, limited visibility, large data requirements, or specific use cases, e.g., in data center networks. In this work, we present vNetRunner, a framework for slice modeling using individually trained virtual network function models. We validate our framework using datasets from an open-source 5G testbed, focusing on traffic metrics such as mean delay and throughput. Our results demonstrate that vNetRunner estimates mean packet delay and throughput with Wasserstein distances of 6 ms and 0.554 Mbps, respectively, achieving execution times that are an order of magnitude faster than the state-of-the-art modeling approaches.

This paper addresses the online k-selection problem with diseconomies of scale (ØSDoS), where a seller seeks to maximize social welfare by optimally pricing items for sequentially arriving buyers, accounting for increasing marginal production costs. Previous studies have investigated deterministic dynamic pricing mechanisms for such settings. However, significant challenges remain, particularly in achieving optimality with small or finite inventories and developing effective randomized posted price mechanisms. To bridge this gap, we propose a novel randomized dynamic pricing mechanism for ØSDoS, providing a tighter lower bound on the competitive ratio compared to prior work. Our approach ensures optimal performance in small inventory settings (i.e., when k is small) and surpasses existing online mechanisms in large inventory settings (i.e., when k is large), leading to the best-known posted price mechanism for optimizing online selection and allocation with diseconomies of scale across varying inventory sizes.

A pivotal attribute of 5G networks is their capability to cater to diverse application requirements. This is achieved by creating logically isolated virtual networks, or slices, with distinct service level agreements (SLAs) tailored to specific use cases. However, efficiently allocating resources to maintain slice SLA is challenging due to varying traffic and quality-of-service (QoS) requirements. Traditional peak traffic-based resource allocation leads to over-provisioning, as actual traffic rarely peaks. Additionally, the complex relationship between resource allocation and QoS in end-to-end slices spanning different network segments makes conventional optimization techniques impractical. Existing approaches in this domain use mathematical network models (e.g., queueing models) or simulations, and various optimization methods but struggle with optimality, tractability, and generalizability across different slice types. In this paper, we propose MicroOpt, a novel framework that leverages a differentiable neural network-based slice model with gradient descent for resource optimization and Lagrangian decomposition for QoS constraint satisfaction. We evaluate MicroOpt against two state-of-the-art approaches using an open-source 5G testbed with real-world traffic traces. Our results demonstrate up to 21.9% improvement in resource allocation compared to these approaches across various scenarios, including different QoS thresholds and dynamic slice traffic.

Low Earth orbit (LEO) satellites-based non-terrestrial networks (NTN) are envisioned to complement the fifth-generation (5G) terrestrial networks (TN), enabling global cellular services. However, the high mobility and large coverage of these satellites result in frequent and numerous inter-satellite handovers, leading to signalling storms that degrade the satellite gNodeB services. To address this, we mathematically formulate the handover problem and propose a novel signalling load-aware handover protocol based on conditional handover. We evaluate the effectiveness of the protocol using a customized discrete-event simulator and compare it against a set of baseline conditional handover schemes. Our findings show that the proposed protocol significantly reduces signalling peaks and balances the load more effectively, enhancing the robustness and efficiency of handover in 5G NTN. The simulator is made publicly available.

We study the design of risk-sensitive online algorithms, in which risk measures are used in the competitive analysis of randomized online algorithms. We introduce the CVaR$_\delta$-competitive ratio ($\delta$-CR) using the conditional value-at-risk of an algorithm’s cost, which measures the expectation of the $(1-\delta)$-fraction of worst outcomes against the offline optimal cost, and use this measure to study three online optimization problems: continuous-time ski rental, discrete-time ski rental, and one-max search. The structure of the optimal $\delta$-CR and algorithm varies significantly between problems: we prove that the optimal $\delta$-CR for continuous-time ski rental is $2-2^{-\Theta(\frac{1}{1-\delta})}$, obtained by an algorithm described by a delay differential equation. In contrast, in discrete-time ski rental with buying cost $B$, there is an abrupt phase transition at $\delta = 1 - \Theta(\frac{1}{\log B})$, after which the classic deterministic strategy is optimal. Similarly, one-max search exhibits a phase transition at $\delta = \frac{1}{2}$, after which the classic deterministic strategy is optimal; we also obtain an algorithm that is asymptotically optimal as $\delta \todown 0$ that arises as the solution to a delay differential equation.

The online knapsack problem is a classic problem in the field of online algorithms. Its canonical version asks how to pack items of different values and weights arriving online into a capacity-limited knapsack so as to maximize the total value of the admitted items. Although optimal competitive algorithms are known for this problem, they may be fundamentally unfair, i.e., individual items may be treated inequitably in different ways. We formalize a practically-relevant notion of time fairness which effectively models a trade off between static and dynamic pricing in a motivating application such as cloud resource allocation, and show that existing algorithms perform poorly under this metric. We propose a parameterized deterministic algorithm where the parameter precisely captures the Pareto-optimal trade-off between fairness (static pricing) and competitiveness (dynamic pricing). We show that randomization is theoretically powerful enough to be simultaneously competitive and fair; however, it does not work well in experiments. To further improve the trade-off between fairness and competitiveness, we develop a nearly-optimal learning-augmented algorithm which is fair, consistent, and robust (competitive), showing substantial performance improvements in numerical experiments.

The burgeoning field of algorithms with predictions studies the problem of using possibly imperfect machine learning predictions to improve online algorithm performance. While nearly all existing algorithms in this framework make no assumptions on prediction quality, a number of methods providing uncertainty quantification (UQ) on machine learning models have been developed in recent years, which could enable additional information about prediction quality at decision time. In this work, we investigate the problem of optimally utilizing uncertainty-quantified predictions in the design of online algorithms. In particular, we study two classic online problems, ski rental and online search, where the decision-maker is provided predictions augmented with UQ describing the likelihood of the ground truth falling within a particular range of values. We demonstrate that non-trivial modifications to algorithm design are needed to fully leverage the UQ predictions. Moreover, we consider how to utilize more general forms of UQ, proposing an online learning framework that learns to exploit UQ to make decisions in multi-instance settings.

We introduce and study a family of online metric problems with long-term constraints. In these problems, an online player makes decisions $\mathbf{x}_t$ in a metric space $(X,d)$ to simultaneously minimize their hitting cost $f_t(\mathbf{x}_t)$ and switching cost as determined by the metric. Over the time horizon $T$, the player must satisfy a long-term demand constraint $\sum_t c(\mathbf{x}_t) \geq 1$, where $c(\mathbf{x}_t)$ denotes the fraction of demand satisfied at time $t$. Such problems can find a wide array of applications to online resource allocation in sustainable energy/computing systems. We devise optimal competitive and learning-augmented algorithms for the case of bounded hitting cost gradients and weighted $\ell_1$ metrics, and further show that our proposed algorithms perform well in numerical experiments.

Non-orthogonal multiple access (NOMA)-aided mobile edge computing (MEC) system can enhance the spectral-efficiency with massive tasks offloading. However, with more dynamic devices and the uncontrollable stochastic channel environment, it is even desirable to deploy appealing technique, i.e., intelligent reflecting surfaces (IRS), in the MEC system to flexibly adjust the communication environment and improve the system energy-efficiency. In this paper, we investigate the joint offloading, communication and computation resource allocation for IRS-assisted NOMA-aided MEC system. We firstly formulate a mixed integer energy-efficiency maximization problem with the system queue stability constraint. We then propose a Het-erogeneous Multi-agent Lyapunov-function-based Mixed Integer Deep Deterministic Policy Gradient (HMA-LMIDDPG) algorithm which is based on the multi-agent reinforcement learning (MARL) framework with homogeneous edge devices (EDs) and heterogeneous base station (BS) as heterogeneous multi-agent. Numerical results show that our proposed algorithms can achieve superior energy-efficiency performance to the benchmark algorithms while maintaining the queue stability.

An electric vehicle based mobility-on-demand (EMoD) system provides shared transportation (e.g., car-sharing or ride-sharing) to satisfy customers’ individual mobility demands. It has been recognized as a vital alternative form of transportation between public and private transportations in future sustainable cities. Constrained by the long charging time and limited driving range of EVs, an operator of an EMoD system demands for decision-making models and algorithms to manage the mobility and energy of EVs to best serve customers with least costs. In this paper, we propose a stochastic dynamic program (DP) to model three operational decisions of the EMoD system: i) dispatching EVs to serve mobility demand from customers, ii) repositioning EVs to accommodate the unbalanced mobility demands between service regions, and iii) recharging EVs to maintain their sufficient state-of-charge levels. To handle this large-scale DP problem, we first observe and prove that it has a coordinate-wise concave value function. Based on this structural property, we propose to use a separable piecewise linear function to approximate the value function and design an approximation-based algorithm to efficiently derive the decision policy. Numerical tests show that our proposed algorithm significantly outperforms the existing model-free approaches (e.g., greedy heuristic and Q-learning) that fail to take into account the structural properties of the DP problem.

By employing powerful edge servers for data processing, mobile edge computing (MEC) has been recognized as a promising technology to support emerging computation-intensive applications. Besides, non-orthogonal multiple access (NOMA)-aided MEC system can further enhance the spectral efficiency with massive tasks offloading. However, with more dynamic devices brought online and the uncontrollable stochastic channel environment, it is even desirable to deploy appealing technique, i.e., intelligent reflecting surfaces (IRS), in the MEC system to flexibly tune the communication environment and improve the system energy efficiency. In this paper, we investigate the joint offloading, communication and computation resource allocation for the IRS-assisted NOMA MEC system. We first formulate a mixed integer energy efficiency maximization problem with system queue stability constraint. We then propose the Lyapunov-function-based Mixed Integer Deep Deterministic Policy Gradient (LMIDDPG) algorithm which is based on the centralized reinforcement learning (RL) framework. To be specific, we design the mixed integer action space mapping which contains both continuous mapping and integer mapping. Moreover, the award function is defined as the upper-bound of the Lyapunov drift-plus-penalty function. To enable end devices (EDs) to choose actions independently at the execution stage, we further propose the Heterogeneous Multi-agent LMIDDPG (HMA-LMIDDPG) algorithm based on distributed RL framework with homogeneous EDs and heterogeneous base station (BS) as heterogeneous multi-agent. Numerical results show that our proposed algorithms can achieve superior energy efficiency performance to the benchmark algorithms while maintaining the queue stability. Specially, the distributed structure HMA-LMIDDPG can acquire more energy efficiency gain than the centralized structure LMIDDPG.

In this article, we consider a parking lot that manages the charging processes of its parked electric vehicles (EVs). Upon arrival, each EV requests a certain amount of energy. This request should be fulfilled before the EV’s departure. It is of critical importance to coordinate the EVs’ charging rates to smooth out the load profile of the parking lot because inappropriate charging rates can lead to sharp spikes and fluctuations on the load profile, imposing negative effects on the power grid. Meanwhile, empirical studies show that many parking lots exhibit statistical patterns on EV dynamics. For example, the bulk of EVs arrives during rush hours. Therefore, in this article, we incorporate such patterns into charging rate coordination. Although the statistical patterns can be summarized from historical data, they are difficult to be analytically modeled. As a result, we adopt a model-free deep reinforcement learning approach. We also take the latest continuous charging rate control technology into consideration. The decision variables are thus continuous and a policy gradient algorithm is needed to perform reinforcement learning. Technically, we first formulate the problem as a Markov decision process (MDP) with unknown state transition probabilities. To further derive a deep policy gradient algorithm, the challenge lies in the inconsistent and state-dependent action space of the MDP model, due to the constraint to satisfy EVs’ energy demands before their scheduled departure. To tackle the challenge, we design a customized model for neural network training by extending the action space to be consistent and state independent, and revise the reward function to penalize the neural network output if it is beyond the action space of the original MDP model. With this customized model, we then develop a deep policy gradient algorithm based on the proximal policy gradient framework. Numerical results show that our algorithm outperforms the benchmarks.

With the popularization of ride-sharing transportation and increasing penetration of electric vehicles (EVs) in recent years, the electric mobility-on-demand (EMoD) system is emerging as a promising means to provide ride-sharing services in the context of sustainable cities. In this paper, we focus on sequential decision-making for the operator of an EMoD system by considering both the passengers’ utility and system revenue. Specifically, we design a pricing mechanism to incentivize passengers with spatially and temporally different demand to make different mobility choices. After the passengers’ demand is realized, the operator makes operational decisions, including dispatching and repositioning EVs between service regions, and recharging EVs to maintain their energy levels. Therefore, a bi-level and dynamic programming problem is formulated to model these decisions. To solve this problem, we first transform the bi-level problem into a single-level one based on the structural properties of the formulation. Furthermore, we rigorously prove the coordinate-wise concavity of the single-level formulation and efficiently obtain near-optimal solutions based on approximation. Numerical tests show that the proposed dynamic pricing mechanism achieves a significantly better performance than static pricing and other existing model-free approaches (e.g., Q-learning).

The design of online algorithms has tended to focus on algorithms with worst-case guarantees, e.g., bounds on the competitive ratio. However, it is well-known that such algorithms are often overly pessimistic, performing sub-optimally on non-worst-case inputs. In this paper, we develop an approach for data-driven design of online algorithms that maintain near-optimal worst-case guarantees while also performing learning in order to perform well for typical inputs. Our approach is to identify policy classes that admit global worst-case guarantees, and then perform learning using historical data within the policy classes. We demonstrate the approach in the context of two classical problems, online knapsack and online set cover, proving competitive bounds for rich policy classes in each case. Additionally, we illustrate the practical implications via a case study on electric vehicle charging.

This paper leverages machine-learned predictions to design competitive algorithms for online conversion problems with the goal of improving the competitive ratio when predictions are accurate (i.e., consistency), while also guaranteeing a worst-case competitive ratio regardless of the prediction quality (i.e., robustness). We unify the algorithmic design of both integral and fractional conversion problems, which are also known as the 1-max-search and one-way trading problems, into a class of online threshold-based algorithms (OTA). By incorporating predictions into design of OTA, we achieve the Pareto-optimal trade-off of consistency and robustness, i.e., no online algorithm can achieve a better consistency guarantee given for a robustness guarantee. We demonstrate the performance of OTA using numerical experiments on Bitcoin conversion.

The Internet-of-Things (IoT) platform is faced with critical challenges posed by the conflict between resource-hungry IoT applications and resource-constrained IoT devices. Mobile-edge computing provides a promising solution by allowing IoT devices to offload their computation to nearby edge servers to enable fast and energy-efficient data processing. In this article, we study a scenario, where two IoT users (IoT devices) offload their computation workloads to an edge server with hybrid nonorthogonal multiple access (NOMA)-orthogonal multiple access (OMA) transmission. The hybrid multiple access transmission incorporates three offloading methods, namely, hybrid NOMA, pure NOMA, and pure OMA. The offloading-method selection, together with user selection, which determines the roles played by different IoT users in data transmission, comprises our offloading strategy and is optimized to minimize the maximal offloading latency of the two IoT users. By exploiting the method of successive convex approximation, we design an efficient algorithm to solve the complicated nonconvex problem and rigorously prove the convergence of our algorithm. Extensive numerical tests show that our scheme can always help IoT users to flexibly choose the best offloading strategy. Inspired by experimental observations, we analytically establish the criteria for the three offloading methods. We show that pure OMA transmission is never the best offloading method, except in some extreme cases that rarely occur in practice, while pure NOMA transmission is the most desirable offloading method in terms of latency minimization. We then propose detection approaches for the best offloading strategy with both offloading-method selection and user selection under certain system settings. The user selection is applied to avoid the pure OMA transmission and encourage the pure NOMA transmission.

This paper proposes a tandem fluid queue model for a mobile computing system with computation offloading and analytically derives its key quality-of-service (QoS) metric. Based on the performance model, we further evaluate the economic benefits of burstable instances, a new type of cloud instances that are recently introduced to the market, and make suggestions on whether burstable instances should be used for mobile computing to save users' costs under different wireless channel conditions and QoS requirements.

The past decades have witnessed an explosive growth of the Internet of Things (IoT) services requiring intensive computation resources. The conventional IoT devices, however, are usually equipped with very limited computation resources, which results in degraded quality of experience when executing the resource-hungry applications. Mobile edge computing (MEC), which enables smart terminals (STs) to offload parts of their computation workloads to the edge servers located at cellular base stations (BSs), has provided a promising approach to address this issue. In this article, we investigate the nonorthogonal multiple access (NOMA)-enabled multiaccess MEC. Specifically, by exploiting the advanced NOMA, an ST can simultaneously offload its computation workloads to different edge servers (ESs), which thus reduces the overall delay in completing the ST's computation workloads. To study this problem, we formulate a joint optimization of the computation resource allocations at the ESs, the ST's offloaded workloads and its radio resource allocations for NOMA transmission, with the objective of minimizing a system wise cost that accounts for the overall delay in finishing the ST's total computation workload and the total computation resource usage cost at the ESs. Despite the nonconvexity of the joint optimization problem, we exploit its layered structure and propose an efficient layered algorithm to find the optimal solution. By exploiting the optimal offloading solution of a single ST, we further investigate the scenario of multiple STs and propose two algorithms to determine the optimal grouping among different ESs for serving the STs, with one algorithm aiming at minimizing the total cost of all STs and the other algorithm aiming at determining the Nash stable grouping for the ESs. Numerical results are presented to validate the effectiveness of our proposed algorithms and show the performance gain of our proposed NOMA-enabled multiaccess computation offloading.

In this paper, we study resource allocation (including power and computation resources) and channel assignment in an uplink Non-orthogonal Multiple Access (NOMA)-based Mobile Edge Computing (MEC) system. Our objective is to minimize the total energy consumption of all users. The problem, however, is a non-convex combinatorial optimization problem. We first investigate the hidden convexity by reformulating the resource allocation problem when the channel assignment is given, and propose an efficient algorithm to allocate the resources by dual decomposition methods. Furthermore, we design a heuristic algorithm to decide the channel assignment leveraging the structural property in the reformulation. Extensive simulations verify that NOMA has great advantages over Orthogonal Multiple Access (OMA) in multi-user latency-intensive MEC systems.

Historically, transportation electrification has been largely hindered by the limited battery capacity and the long charging time. Battery swapping has emerged as one promising technology to mitigate these problems. A centralised battery charging station (BCS) is responsible for charging depleted batteries (DBs) and providing fully‐charged batteries (FBs) for multiple geographically‐distributed battery swapping stations (BSSs) so that they can carry out battery swapping services. Facilitated by the recent advancement in sensor and communication technologies, one salient advantage of this centralised approach lies in its convenience to better utilise dual energy sources (i.e. the traditional power grid and local renewable energy generators). This is achieved via optimising the charging processes of a large number of DBs. In this study, the authors propose an optimisation framework for a centralised BCS to minimise the energy cost from the dual energy sources to satisfy the FB demands from multiple BSSs. Particularly, the power dispatch problem in the day‐ahead and real‐time electricity markets is formulated as a two‐stage stochastic optimisation through consideration of the intermittent renewable energy. Numerical simulations show that the proposed optimised power dispatch is capable of achieving cost saving of 76% compared with the benchmark, subject to the limited information available in day‐ahead.

With the integration of renewable energy sources to the power grid, the volatility of supply in the system will increase. Consequently, the mismatch between the power supply and demand may happen frequently and, thus, lead to frequency deviation from its nominal value. To avoid this scenario, demand-side flexibility has been widely considered to provide frequency regulation services. In this paper, we focus on the flexibility of thermal systems in buildings and propose a hierarchical demand-response market with a three-step algorithm to model the interactions among three entities: the independent system operators (ISOs), aggregators, and end users. The flexibility from the end users is aggregated in step 1, which is based on the incentive and electricity prices broadcasted by the aggregator. A robust optimization approach is adopted to improve the user's decision under the electricity price uncertainty. To model the interaction between the ISO and aggregators in step 2, a bilevel optimization problem is solved, in which the ISO seeks to minimize its cost, while the aggregators maximize their benefits in the day-ahead market. In step 3, each aggregator allocates its successful trading reserve among end users based on their performance scores.