Online Conversion with Switching Costs: Robust and Learning-Augmented Algorithms

This paper introduces and studies online conversion with switching costs (OCS), a novel class of online problems motivated by emerging control problems in the design of sustainable systems. We consider both minimization (OCS-min) and maximization (OCS-max) variants of the problem. In OCS-min, an online player aims to purchase one item over a sequence of time-varying cost functions and decides the fractional amount of item to purchase in each round. The player must purchase the entire item before a deadline, and they incur a movement cost whenever their decision changes, i.e., whenever they purchase different amounts of the item in consecutive time steps. From the player's perspective, the goal is to minimize their total cost, including the total purchasing cost and any movement cost incurred over the time horizon. In OCS-max, the setting is almost the same, except the player sells an item fractionally according to time-varying price functions, so the goal is to maximize their total profit, and any movement costs are subtracted from the revenue. In both settings, the cost/price functions are revealed one by one in an online manner, and the player makes an irrevocable decision at each time step without the knowledge of future cost/price functions. Our motivation behind introducing OCS is an emerging class of carbon-aware problems such as carbon-aware electric vehicle (EV) charging [12] and carbon-aware compute shifting [1, 3, 22, 23, 46, 57], which have attracted significant attention in recent years.