This paper studies the online energy scheduling problem in a hybrid model where the cost of energy is proportional to both the volume and peak usage, and where energy can be either locally generated or drawn from the grid. Inspired by recent advances in online algorithms with Machine Learned (ML) advice, we develop parameterized deterministic and randomized algorithms for this problem such that the level of reliance on the advice can be adjusted by a trust parameter. We then analyze the performance of the proposed algorithms using two performance metrics: robustness that measures the competitive ratio as a function of the trust parameter when the advice is inaccurate, and consistency for competitive ratio when the advice is accurate. Since the competitive ratio is analyzed in two different regimes, we further investigate the Pareto optimality of the proposed algorithms. Our results show that the proposed deterministic algorithm is Paretooptimal, in the sense that no other online deterministic algorithms can dominate the robustness and consistency of our algorithm. Furthermore, we show that the proposed randomized algorithm dominates the Paretooptimal deterministic algorithm. Our largescale empirical evaluations using real traces of energy demand, energy prices, and renewable energy generations highlight that the proposed algorithmsmore »
Online PeakAware Energy Scheduling with Untrusted Advice
This paper studies the online energy scheduling problem in a hybrid model where the cost of energy is proportional to both the volume and peak usage, and where energy can be either locally generated or drawn from the grid. Inspired by recent advances in online algorithms with Machine Learned (ML) advice, we develop parameterized deterministic and randomized algorithms for this problem such that the level of reliance on the advice can be adjusted by a trust parameter. We then analyze the performance of the proposed algorithms using two performance metrics: textit{robustness} that measures the competitive ratio as a function of the trust parameter when the advice is inaccurate, and textit{consistency} for competitive ratio when the advice is accurate. Since the competitive ratio is analyzed in two different regimes, we further investigate the Pareto optimality of the proposed algorithms. Our results show that the proposed deterministic algorithm is Paretooptimal, in the sense that no other online deterministic algorithms can dominate the robustness and consistency of our algorithm. Furthermore, we show that the proposed randomized algorithm dominates the Paretooptimal deterministic algorithm. Our largescale empirical evaluations using real traces of energy demand, energy prices, and renewable energy generations highlight that the proposed algorithms more »
 Award ID(s):
 1908298
 Publication Date:
 NSFPAR ID:
 10296414
 Journal Name:
 Proceedings of the Twelfth ACM International Conference on Future Energy Systems (eEnergy)
 Sponsoring Org:
 National Science Foundation
More Like this


null (Ed.)This paper studies the online energy scheduling problem in a hy brid model where the cost of energy is proportional to both the volume and peak usage, and where energy can be either locally generated or drawn from the grid. Inspired by recent advances in online algorithms with Machine Learned (ML) advice, we develop parameterized deterministic and randomized algorithms for this problem such that the level of reliance on the advice can be adjusted by a trust parameter. We then analyze the performance of the pro posed algorithms using two performance metrics: robustness that measures the competitive ratio as a function of the trust parameter when the advice is inaccurate, and consistency for competitive ratio when the advice is accurate. Since the competitive ratio is analyzed in two different regimes, we further investigate the Pareto optimal ity of the proposed algorithms. Our results show that the proposed deterministic algorithm is Paretooptimal, in the sense that no other online deterministic algorithms can dominate the robustness and consistency of our algorithm. Furthermore, we show that the proposed randomized algorithm dominates the Paretooptimal de terministic algorithm. Our largescale empirical evaluations using real traces of energy demand, energy prices, and renewable energy generations highlightmore »

This paper leverages machinelearned 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 worstcase 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 1maxsearch and oneway trading problems, into a class of online thresholdbased algorithms (OTA). By incorporating predictions into design of OTA, we achieve the Paretooptimal tradeoff 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.

We study an online hypergraph matching problem with delays, motivated by ridesharing applications. In this model, users enter a marketplace sequentially, and are willing to wait up to $d$ timesteps to be matched, after which they will leave the system in favor of an outside option. A platform can match groups of up to $k$ users together, indicating that they will share a ride. Each group of users yields a match value depending on how compatible they are with one another. As an example, in ridesharing, $k$ is the capacity of the service vehicles, and $d$ is the amount of time a user is willing to wait for a driver to be matched to them. We present results for both the utility maximization and cost minimization variants of the problem. In the utility maximization setting, the optimal competitive ratio is $\frac{1}{d}$ whenever $k \geq 3$, and is achievable in polynomialtime for any fixed $k$. In the cost minimization variation, when $k = 2$, the optimal competitive ratio for deterministic algorithms is $\frac{3}{2}$ and is achieved by a polynomialtime thresholding algorithm. When $k>2$, we show that a polynomialtime randomized batching algorithm is $(2  \frac{1}{d}) \log k$competitive, and it is NPhardmore »

The online matching problem was introduced by Karp, Vazirani and Vazirani nearly three decades ago. In that seminal work, they studied this problem in bipartite graphs with vertices arriving only on one side, and presented optimal deterministic and randomized algorithms for this setting. In comparison, more general arrival models, such as edge arrivals and general vertex arrivals, have proven more challenging, and positive results are known only for various relaxations of the problem. In particular, even the basic question of whether randomization allows one to beat the triviallyoptimal deterministic competitive ratio of 1/2 for either of these models was open. In this paper, we resolve this question for both these natural arrival models, and show the following. For edge arrivals, randomization does not help  no randomized algorithm is better than 1/2 competitive. For general vertex arrivals, randomization helps  there exists a randomized (1/2+ Ω(1))competitive online matching algorithm.