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 novel mechanism for online allocation with multi-phase, non-separable regularizers, termed Cap-and-Penalize (CnP), inspired by real-world applications such as cap-and-tax policies in carbon pricing. The CnP regularizer models a multi-phase cost structure, imposing a monotone convex penalty when total allocation exceeds a predefined level (soft cap) and enforcing a strict limit (hard cap) beyond which allocation is prohibited. Our contributions are twofold: (1) we propose an online mechanism for CnP-regularized allocation without per-step resource constraints, which operates as a simple and intuitive posted-price mechanism, but achieves the best-possible guarantee among all possible online algorithms; (2) we tackle the more complex setting with per-step resource constraints by decomposing the regularizer into local components, yielding a similar mechanism with time-dependent marginal pricing functions. To establish the tightness of our results in both settings, we introduce a representative function-based approach that transforms the lower-bound proof into the problem of solving an ordinary differential equation with boundary conditions. We believe that this technique has the potential to be applied to other similar online optimization 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.

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.

We prove that single-parameter natural exponential families with subexponential tails are self-concordant with polynomial-sized parameters. For subgaussian natural exponential families we establish an exact characterization of the growth rate of the self-concordance parameter. Applying these findings to bandits allows us to fill gaps in the literature: We show that optimistic algorithms for generalized linear bandits enjoy regret bounds that are both second-order (scale with the variance of the optimal arm's reward distribution) and free of an exponential dependence on the bound of the problem parameter in the leading term. To the best of our knowledge, ours is the first regret bound for generalized linear bandits with subexponential tails, broadening the class of problems to include Poisson, exponential and gamma bandits.

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.

In this paper, we study a general transactive energy (TE) retailing problem in smart grids: a TE retailer (e.g., a utility company) publishes the energy price, which may vary over time. TE customers arrive in an arbitrary manner and may choose to either purchase a certain amount of energy based on the posted price, or leave without buying. Typical examples of such a setup include a transactive electric vehicle charging platform, or a general market-based demand-side management program, etc. We consider the setting where the customer arrival information is unknown (i.e., without prediction), and focus on maximizing the social welfare of the TE system through a posted-price mechanism (PPM) that runs in an online fashion with causal information only. We quantify the performance of the proposed PPM in the competitive analysis framework, and show that our proposed PPM is optimal in the sense that no other online mechanisms can achieve a better competitive ratio. We evaluate our theoretic results for the case of transactive electric vehicle charging. Our extensive experimental results show that the proposed PPM is competitive and robust against system uncertainties, and outperforms several existing benchmarks.

We study a general online combinatorial auction problem in algorithmic mechanism design. A provider allocates multiple types of capacity-limited resources to customers that arrive in a sequential and arbitrary manner. Each customer has a private valuation function on bundles of resources that she can purchase (e.g., a combination of different resources such as CPU and RAM in cloud computing). The provider charges payment from customers who purchase a bundle of resources and incurs an increasing supply cost with respect to the totality of resources allocated. The goal is to maximize the social welfare, namely, the total valuation of customers for their purchased bundles, minus the total supply cost of the provider for all the resources that have been allocated. We adopt the competitive analysis framework and provide posted-price mechanisms with optimal competitive ratios. Our pricing mechanism is optimal in the sense that no other online algorithms can achieve a better competitive ratio. We validate the theoretic results via empirical studies of online resource allocation in cloud computing. Our numerical results demonstrate that the proposed pricing mechanism is competitive and robust against system uncertainties and outperforms existing benchmarks.

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.

The optimal operation of a distributed battery energy storage system (BESS) for energy arbitrage under dynamic pricing is studied in this paper, and the Pareto optimal arbitrage policy that balances the economic value and lifetime tradeoff of the BESS is obtained. Specifically, the lifetime performance of the BESS is represented by its average lifetime, i.e., the average operational duration within which its capacity stays above a certain threshold, and the value performance of the BESS is defined as the total average arbitrage value within its entire lifetime. We propose a constrained stochastic shortest path (CSSP) model to characterize the optimal value-lifetime performance pair. By exploiting the hidden structure of this CSSP problem, an efficient parallel algorithm is proposed to compute the optimal policy. We further prove the condition under which the optimal policy is Pareto optimal. This implies that the achievable optimal value-lifetime performance pair is globally optimal as long as the system-wide utility is monotonically increasing in both the value performance and the lifetime performance. We validate our proposed model and algorithm via real battery specifications and electricity market data, and the results show promising insights for both infrastructure planning and operational management of BESSs in practice.

Future smart grid (SG) has been considered a complex and advanced power system, where energy consumers are connected not only to the traditional energy retailers (e.g., the utility companies), but also to some local energy networks for bidirectional energy trading opportunities. This paper aims to investigate a hybrid energy trading market that is comprised of an external utility company and a local trading market managed by a local trading center (LTC). The existence of local energy market provides new opportunities for the energy consumers and the distributed energy sellers to perform the local energy trading in a cooperative manner such that they all can benefit. This paper first quantifies the respective benefits of the energy consumers and the sellers from the local trading and then investigates how they can optimize their benefits by controlling their energy scheduling in response to the LTC's pricing. Two different types of the LTC are considered: 1) the nonprofit-oriented LTC, which solely aims at benefiting the energy consumers and the sellers; and 2) the profit-oriented LTC, which aims at maximizing its own profit while guaranteeing the required benefit for each consumer and seller. For each type of the LTC, the optimal trading problem is formulated and the associated algorithm is further proposed to efficiently find the LTC's optimal price, as well as the optimal energy scheduling for each consumer and seller. Numerical results are provided to validate the benefits of the hybrid energy trading market and the performance of the proposed algorithms.

The cyber-physical directory is proposed previously to enhance the effectiveness of current digital directories, which used the tag-cloud representation to make relevant information obviously bigger to users due to their interests. Such customized visualizations can speed up the information search for user social activities at a location. Unfortunately, such visualization poorly utilizes the total area of a directory display by leaving a lot of unused areas. This paper introduces a 3-step optimized visualization framework that solves this problem while preserving the advantages of tag-cloud representations. The proposed framework is successfully implemented for its feasibility, and is proved its high utilization and practicality to users in a real scenario.

The current mobile broadband market experiences major growth in data demand and average revenue loss. To remain profitable from the perspective of a service provider (SP), one needs to maximize revenue as much as possible by making subscribers satisfied within the limited budget. On the other hand, traffic demands are moving toward supporting the wide range of heterogeneous services with different quality of service (QoS) requirements. In this paper, we consider packet scheduling problem in the 4th generation partnership project (3GPP) long term evolution-advanced (LTE-A) system to optimize the long-term average revenue of SPs subject to differential QoS constraints for heterogeneous traffic demands. The QoS-constrained control problem is first formulated as a constrained Markov decision process (CMDP) problem, of which the optimal control policy is achieved by utilizing the channel and queue information simultaneously. Subsequently, based on the proposed CMDP problem, we further formulated an optimization problem which stochastically grantees the QoS through a chance constraint. To make the proposed chance-constraint programming problem computationally tractable, we use Bernstein approximation technique to analytically approximate the chance constraint as a convex conservative constraint. Finally, the proposed scheduling framework and solution methods are validated via numerical simulation.