@conference{Yang2022Competitive,

title = {Competitive Algorithms for Online Multidimensional Knapsack Problems},

author = {Lin Yang and Ali Zeynali and Mohammad H. Hajiesmaili and Ramesh Sitaraman and Don Towsley},

url = {https://groups.cs.umass.edu/hajiesmaili/wp-content/uploads/sites/24/2021/11/Sigmetrics_2022_OnlineKnapsack.pdf},

year  = {2022},

date = {2022-06-09},

booktitle = {ACM Sigmetrics},

abstract = {In this paper, we study the online multidimensional knapsack problem OMdKP in which there is a knapsack whose capacity is represented in m dimensions, each dimension could have a different capacity. Then, n items with different scalar profit values and mm-dimensional weights arrive in an online manner and the goal is to admit or decline items upon their arrival such that the total profit obtained by admitted items is maximized and the capacity of knapsack across all dimensions is respected. This is a natural generalization of the classic single-dimension knapsack problem and finds several relevant applications such as in virtual machine allocation, job scheduling, and all-or-nothing flow maximization over a graph. We develop two algorithms for OMdKP that use linear and exponential reservation functions to make online admission decisions. Our competitive analysis shows that the linear and exponential algorithms achieve the competitive ratios of $O(sqrt{thetaalpha})$ and $O(logleft(thetaalpharight))$, respectively, where alphaα is the ratio between the aggregate knapsack capacity and the minimum capacity over a single dimension and $theta$ is the ratio between the maximum and minimum item unit values. We also characterize a lower bound for the competitive ratio of any online algorithm solving OMdKP and show that the competitive ratio of our algorithm with exponential reservation function matches the lower bound up to a constant factor.},

keywords = {},

pubstate = {forthcoming},

tppubtype = {conference}

}

@conference{Yang2022Distributed,

title = {Distributed Bandits with Heterogeneous Agents},

author = {Lin Yang and Yu-Zhen Chen and Mohammad H Hajiesmaili and John Lui and Don Towsley},

year  = {2022},

date = {2022-05-05},

booktitle = {IEEE International Conference on Computer Communications (INFOCOM)},

abstract = {This paper tackles a multi-agent bandit setting in which M agents cooperate together to solve the same instance of a K-armed stochastic bandit problem. The agents in the system are heterogeneous: each agent has limited access to a local subset of arms and is asynchronous with different gaps between decision-making rounds. The goal for each agent is to find its optimal local arm and agents are able to cooperate by sharing their observations. For this heterogeneous multi-agent setting, we propose two respective algorithms, CO-UCB and CO-AAE. Both algorithms are proven to attain the order-optimal regret, $Oleft(sum_{i:tilde{Delta}_i>0} log T/tilde{Delta}_iright)$, where $tilde{Delta}_i$ is the minimum suboptimality gap between the reward mean of arm i and any local optimal arm. In addition, with a careful selection of valuable information for cooperation, CO-AAE achieves a low communication complexity. Last, numerical experiments verify the efficiency of both algorithms.},

keywords = {},

pubstate = {forthcoming},

tppubtype = {conference}

}

@conference{Sun2021Pareto,

title = {Pareto-Optimal Learning-Augmented Algorithms for Online Conversion Problems},

author = {Bo Sun and Russell Lee and Mohammad H Hajiesmaili and Adam Wierman and Danny HK Tsang

},

url = {https://groups.cs.umass.edu/hajiesmaili/wp-content/uploads/sites/24/2021/10/pareto_optimal_learning_augmen.pdf



https://groups.cs.umass.edu/hajiesmaili/wp-content/uploads/sites/24/2021/12/poster_neurips21_bo.pdf



https://groups.cs.umass.edu/hajiesmaili/wp-content/uploads/sites/24/2021/12/slides_neurips2021_bo.pdf},

year  = {2021},

date = {2021-12-06},

booktitle = {Advances in Neural Information Processing Systems (NeurIPS)},

abstract = {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.},

keywords = {},

pubstate = {published},

tppubtype = {conference}

}

@conference{Yang2021Cooperatibe,

title = {Cooperative Stochastic Bandits with Asynchronous Agents and Constrained Feedback},

author = {Lin Yang and Yu-Zhen Chen and Stephen Pasteris and Mohammad H Hajiesmaili and John Lui and Don Towsley},

url = {https://groups.cs.umass.edu/hajiesmaili/wp-content/uploads/sites/24/2021/10/cooperative_stochastic_bandits-1.pdf



https://groups.cs.umass.edu/hajiesmaili/wp-content/uploads/sites/24/2021/12/poster_neurips2021_lin.pdf



https://groups.cs.umass.edu/hajiesmaili/wp-content/uploads/sites/24/2021/12/slides_neurips2021_lin.pdf},

year  = {2021},

date = {2021-12-06},

booktitle = {Advances in Neural Information Processing Systems (NeurIPS)},

abstract = {This paper studies a cooperative multi-armed bandit problem with M agents cooperating together to solve the same instance of a K-armed stochastic bandit problem with the goal of maximizing the cumulative reward of agents. The agents are heterogeneous in (i) their limited access to a local subset of arms; and (ii) their decision-making rounds, i.e., agents are asynchronous with different decision-making gaps. 

The goal is to find the global optimal arm and agents are able to pull any arm, however, they observe the reward only when the selected arm is local. The challenge is a tradeoff for agents between pulling a local arm with the possibility of observing the feedback, or relying on the observations of other agents that might occur at different rates. Naive extensions of traditional algorithms lead to an arbitrarily poor regret as a function of aggregate action frequency of any suboptimal arm located in slow agents. We resolve this issue by proposing a novel two-stage learning algorithm, called the CO-LCB algorithm, whose regret is a function of the aggregate action frequency of agents containing the optimal arm. We also show that the regret of CO-LCB matches the regret lower bound up to a  K factor.},

keywords = {},

pubstate = {published},

tppubtype = {conference}

}

@conference{FOCAS2021,

title = {FOCAS: Practical Video Super Resolution using Foveated Rendering},

author = {Lingdong Wang and Mohammad H Hajiesmaili and Ramesh Sitaraman},

url = {https://groups.cs.umass.edu/hajiesmaili/wp-content/uploads/sites/24/2021/12/FOCAS_Practical_Video_Super_Resolution_using_Foveated_Rendering__Final.pdf},

year  = {2021},

date = {2021-11-18},

booktitle = {ACM Multimedia 2021},

keywords = {},

pubstate = {published},

tppubtype = {conference}

}

@conference{SusCloud2021,

title = {Enabling Sustainable Clouds: The Case for Virtualizing the Energy System},

author = {Noman Bashir and Tian Guo and Mohammad Hajiesmaili and David Irwin and Prashant Shenoy and Ramesh Sitaraman and Abel Souza and Adam Wierman

},

url = {https://groups.cs.umass.edu/hajiesmaili/wp-content/uploads/sites/24/2021/09/2106.08872-1.pdf},

year  = {2021},

date = {2021-11-11},

booktitle = {ACM SoCC},

abstract = {Cloud platforms' growing energy demand and carbon emissions are raising concern about their environmental sustainability. The current approach to enabling sustainable clouds focuses on improving energy-efficiency and purchasing carbon offsets. These approaches have limits: many cloud data centers already operate near peak efficiency, and carbon offsets cannot scale to near zero carbon where there is little carbon left to offset. Instead, enabling sustainable clouds will require applications to adapt to when and where unreliable low-carbon energy is available. Applications cannot do this today because their energy use and carbon emissions are not visible to them, as the energy system provides the rigid abstraction of a continuous, reliable energy supply. This vision paper instead advocates for a ``carbon first'' approach to cloud design that elevates carbon-efficiency to a first-class metric. To do so, we argue that cloud platforms should virtualize the energy system by exposing visibility into, and software-defined control of, it to applications, enabling them to define their own abstractions for managing energy and carbon emissions based on their own requirements.},

keywords = {},

pubstate = {published},

tppubtype = {conference}

}

@conference{Competitive2021Lee,

title = {Competitive Bidding Strategies for Online Linear Optimization with Inventory Management Constraints},

author = {Russell Lee and Yutao Zhou and Lin Yang and Mohammad Hajiesmaili and Ramesh Sitaraman},

year  = {2021},

date = {2021-11-04},

booktitle = {IFIP Performance },

abstract = {This paper develops competitive bidding strategies for an online linear optimization problem with inventory management constraints in both cost minimization and profit maximization settings. In the minimization problem, a decision maker should satisfy its time-varying demand by either purchasing units of an asset from the market or producing them from a local inventory with limited capacity. In the maximization problem, a decision maker has a time-varying supply of an asset that may be sold to the market or stored in the inventory to be sold later. In both settings, the market price is unknown in each timeslot and the decision maker can submit a finite number of bids to buy/sell the asset. Once all bids have been submitted, the market price clears, and the amount bought/sold is determined based on the clearing price and submitted bids. From this setup, the decision maker must minimize/maximize their cost/profit in the market, while also devising a bidding strategy in the face of an unknown clearing price. We propose dembid and supbid, two competitive bidding strategies for these online linear optimization problems with inventory management constraints for the minimization and maximization setting respectively. We then analyze the competitive ratios of the proposed algorithms and show that the performance of our algorithms approaches the best possible competitive ratio as the maximum number of bids increases. As a case study, we use energy data traces from Akamai data centers, renewable outputs from NREL, and energy prices NYISO to show the effectiveness of our bidding strategies in the context of energy storage management for a large energy customer participating in a real-time electricity market.},

keywords = {},

pubstate = {published},

tppubtype = {conference}

}

@conference{lee2021Online,

title = {Online Peak-Aware Energy Scheduling with Untrusted Advice},

author = {Russell Lee and Jessica Maghakian and Mohammad H. Hajiesmaili and Jian Li and Ramesh Sitaraman and Zhenhua Liu},

url = {https://groups.cs.umass.edu/hajiesmaili/wp-content/uploads/sites/24/2021/06/eenergy21-final70-1.pdf},

year  = {2021},

date = {2021-06-24},

booktitle = {Proceedings of the Twelfth ACM International Conference on Future Energy Systems (eEnergy)},

abstract = {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 Pareto-optimal, 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 Pareto-optimal deterministic algorithm. Our large-scale empirical evaluations using real traces of energy demand, energy prices, and renewable energy generations highlight that the proposed algorithms outperform algorithms optimized for worst-case and fully data-driven algorithms.},

note = {Best paper runner-up},

keywords = {},

pubstate = {published},

tppubtype = {conference}

}

@conference{Lin2020Adversarial,

title = {Adversarial Bandits with Corruptions: Regret Lower Bound and No-regret Algorithm},

author = {Lin Yang and Mohammad H. Hajiesmaili and Mohammad Sadegh Talebi and John C. S. Lui and Wing Shing Wong},

url = {https://groups.cs.umass.edu/hajiesmaili/wp-content/uploads/sites/24/2021/01/paper_final-1.pdf},

year  = {2020},

date = {2020-12-31},

booktitle = {Advances in Neural Information Processing Systems (NeurIPS)},

abstract = {This paper studies adversarial bandits with corruptions. In the basic adversarial bandit setting, the reward of arms is predetermined by an adversary who is oblivious to the learner’s policy. In this paper, we consider an extended setting in which an attacker sits in-between the environment and the learner, and is endowed with a limited budget to corrupt the reward of the selected arm. We have two main results. First, we derive a lower bound on the regret of any bandit algorithm that is aware of the budget of the attacker. Also, for budget-agnostic algorithms, we characterize an impossibility result demonstrating that even when the attacker has a sublinear budget, i.e., a budget growing sublinearly with time horizon T, they fail to achieve a sublinear regret. Second, we propose ExpRb, a bandit algorithm that incorporates a biased estimator and a robustness parameter to deal with corruption. We characterize the regret of ExpRb as a function of the corruption budget and show that for the case of a known corruption budget, the regret of ExpRb is tight.},

keywords = {},

pubstate = {published},

tppubtype = {conference}

}

@conference{Jha2020Emission,

title = {Emission-aware Energy Storage Scheduling for a Greener Grid},

author = {Rishikesh Jha and Stephen Lee and Srinivasan Iyengar and Mohammad H Hajiesmaili and David Irwin and Prashant Shenoy},

url = {https://groups.cs.umass.edu/hajiesmaili/wp-content/uploads/sites/24/2020/08/2005.12234-1.pdf},

doi = {10.1145/3396851.3397755},

year  = {2020},

date = {2020-06-01},

booktitle = {Proceedings of the Eleventh ACM International Conference on Future Energy Systems (eEnergy)},

abstract = {Reducing our reliance on carbon-intensive energy sources is vital for reducing the carbon footprint of the electric grid. Although the grid is seeing increasing deployments of clean, renewable sources of energy, a significant portion of the grid demand is still met using traditional carbon-intensive energy sources. In this paper, we study the problem of using energy storage deployed in the grid to reduce the grid's carbon emissions. While energy storage has previously been used for grid optimizations such as peak shaving and smoothing intermittent sources, our insight is to use distributed storage to enable utilities to reduce their reliance on their less efficient and most carbon-intensive power plants and thereby reduce their overall emission footprint. We formulate the problem of emission-aware scheduling of distributed energy storage as an optimization problem, and use a robust optimization approach that is well-suited for handling the uncertainty in load predictions, especially in the presence of intermittent renewables such as solar and wind. We evaluate our approach using a state of the art neural network load forecasting technique and real load traces from a distribution grid with 1,341 homes. Our results show a reduction of> 0.5 million kg in annual carbon emissions--equivalent to a drop of 23.3% in our electric grid emissions.},

note = {Best paper runner-up},

keywords = {},

pubstate = {published},

tppubtype = {conference}

}

@conference{Ambati2020Hedge,

title = {Hedge Your Bets: Optimizing Long-term Cloud Costs by Mixing VM Purchasing Options},

author = {Pradeep Ambati and Noman Bashir and David Irwin and Mohammad H. Hajiesmaili and Prashant Shenoy},

url = {https://ieeexplore.ieee.org/abstract/document/9096448},

doi = { 10.1109/IC2E48712.2020.00018},

year  = {2020},

date = {2020-04-01},

booktitle = {IEEE International Conference on Cloud Engineering (IC2E)},

abstract = {Cloud platforms offer the same VMs under many purchasing options that specify different costs and time commitments, such as on-demand, reserved, sustained-use, scheduled reserve, transient, and spot block. In general, the stronger the commitment, i.e., longer and less flexible, the lower the price. However, longer and less flexible time commitments can increase cloud costs for users if future workloads cannot utilize the VMs they committed to buying. Large cloud customers often find it challenging to choose the right mix of purchasing options to reduce their long-term costs, while retaining the ability to adjust capacity up and down in response to workload variations.To address the problem, we design policies to optimize long-term cloud costs by selecting a mix of VM purchasing options based on short- and long-term expectations of workload utilization. We consider a batch trace spanning 4 years from a large shared cluster for a major state University system that includes 14k cores and 60 million job submissions, and evaluate how these jobs could be judiciously executed using cloud servers using our approach. Our results show that our policies incur a cost within 41% of an optimistic optimal offline approach, and 50% less than solely using on-demand VMs.},

keywords = {},

pubstate = {published},

tppubtype = {conference}

}

@conference{yekke2019cdc,

title = {Risk-Averse Explore-Then-Commit Algorithms for Finite-Time Bandits},

author = {Ali Yekkehkhany and Ebrahim Arian and Mohammad H Hajiesmaili and Rakesh Nagi},

url = {https://arxiv.org/abs/1904.13387},

year  = {2019},

date = {2019-12-06},

booktitle = {Proc. of IEEE Annual Conference on Decision and Control (CDC)},

abstract = {In this paper, we study multi-armed bandit problems in explore-then-commit setting. In our proposed explore-then-commit setting, the goal is to identify the best arm after a pure experimentation (exploration) phase and exploit it once or for a given finite number of times. We identify that although the arm with the highest expected reward is the most desirable objective for infinite exploitations, it is not necessarily the one that is most probable to have the highest reward in a single or finite-time exploitations. Alternatively, we advocate the idea of risk-aversion where the objective is to compete against the arm with the best risk-return trade-off. Then, we propose two algorithms whose objectives are to select the arm that is most probable to reward the most. Using a new notion of finite-time exploitation regret, we find an upper bound for the minimum number of experiments before commitment, to guarantee an upper bound for the regret. As compared to existing risk-averse bandit algorithms, our algorithms do not rely on hyper-parameters, resulting in a more robust behavior in practice, which is verified by the numerical evaluation.

},

keywords = {},

pubstate = {published},

tppubtype = {conference}

}

@conference{8815242,

title = {Coordinating Distribution System Resources for Co-optimized Participation in Energy and Ancillary Service Transmission System Markets},

author = {Chengda Ji and Mohammad H Hajiesmaili and Dennice F Gayme and Enrique Mallada},

url = {https://groups.cs.umass.edu/hajiesmaili/wp-content/uploads/sites/24/2020/01/acc2019.pdf},

doi = {10.23919/ACC.2019.8815242},

year  = {2019},

date = {2019-07-01},

booktitle = {Proc. of American Control Conference (ACC)},

pages = {1315-1322},

address = {Philadelphia, PA, USA},

abstract = {This paper investigates the potential of using aggregate controllable loads and energy storage systems from multiple heterogeneous feeders to jointly optimize a utility's energy procurement cost from the real-time market and their revenue from ancillary service markets. Toward this, we formulate an optimization problem that co-optimizes real-time and energy reserve markets based on real-time and ancillary service market prices, along with available solar power, storage and demand data from each of the feeders within a single distribution network. The optimization, which includes all network system constraints, provides real/reactive power and energy storage set-points for each feeder as well as a schedule for the aggregate system's participation in the two types of markets. We evaluate the performance of our algorithm using several trace-driven simulations based on a real-world circuit of a New Jersey utility. The results demonstrate that active participation through controllable loads and storage significantly reduces the utility's net costs, i.e., real-time energy procurement costs minus ancillary market revenues.},

keywords = {},

pubstate = {published},

tppubtype = {conference}

}

@conference{Yang2019CISS,

title = {Online Linear Programming with Uncertain Constraints},

author = {Lin Yang and Mohammad H. Hajiesmaili and Wing. S Wong},

url = {https://groups.cs.umass.edu/hajiesmaili/wp-content/uploads/sites/24/2019/12/ciss.2019.pdf},

doi = {10.1109/CISS.2019.8693056},

year  = {2019},

date = {2019-04-18},

booktitle = {Proc. of IEEE Conference on Information Sciences and Systems (CISS)},

journal = {Proc. ACM Meas. Anal. Comput. Syst.},

address = {Baltimore, MD, USA},

abstract = {There are many applications scenarios in different disciplines where the critical knowledge of decision making arrives in a sequential manner, so the optimization must be done in an online fashion. An important class of online optimization problems that have been extensively studied in the past is online linear programs. This paper tackles a general class of online linear programs that take into account the online arrival of the constraint entries related to the available budget and demand for different problem settings. This generalization is motivated by many recent applications on revenue management or resource allocation problems with the unknown and time-varying budget. As the main contribution of this paper, we propose a decoupling strategy that can be used to reduce the general problem into a series of subproblems with offline entries for the budget and demand. Using the proposed strategy, one can decouple the general problem, leverage the state-of-the-art algorithms for the online subproblems with fixed constraints, and achieve the same performance for the general problem. As for a case study, we apply the strategy to an extension of the one-way trading problem with the dynamic budget.},

note = {Invited paper},

keywords = {},

pubstate = {published},

tppubtype = {conference}

}

@conference{Ahmad:2019:LOE:3307772.3328308,

title = {Learning from Optimal: Energy Procurement Strategies for Data Centers},

author = {Sohaib Ahmad and Arielle Rosenthal and Mohammad H Hajiesmaili and Ramesh K Sitaraman},

url = {http://doi.acm.org/10.1145/3307772.3328308},

doi = {10.1145/3307772.3328308},

year  = {2019},

date = {2019-01-01},

booktitle = {Proceedings of the Tenth ACM International Conference on Future Energy Systems (eEnergy)},

pages = {326--330},

address = {Phoenix, AZ, USA},

abstract = {Environmental concerns and rising grid prices have motivated data center owners to invest in on-site renewable energy sources. However, these sources present challenges as they are unreliable and intermittent. In an effort to mitigate these issues, data centers are incorporating energy storage systems. This introduces the opportunity for electricity bill reduction, as energy storage can be used for power market arbitrage.



We present two supervised learning-based algorithms, LearnBuy, that learns the amount to purchase, and LearnStore, that learns the amount to store, to solve this energy procurement problem. These algorithms utilize the idea of "learning from optimal" by using the values generated by the offline optimization as a label for training. We test our algorithms on a general case, considering buying and selling back to the grid, and a special case, considering only buying from the grid. In the general case, LearnStore achieves a 10--16% reduction compared to baseline heuristics, whereas in the special case, LearnBuy achieves a 7% reduction compared to prior art.},

note = {Notes paper},

keywords = {},

pubstate = {published},

tppubtype = {conference}

}

@conference{Lin2018Optimal,

title = {An Optimal Randomized Online Algorithm for QoS Buffer Management},

author = {Lin Yang and Wing S. Wong and Mohammad H. Hajiesmaili },

url = {https://groups.cs.umass.edu/hajiesmaili/wp-content/uploads/sites/24/2020/01/sigmetrics181-1.pdf},

doi = {10.1145/3219617.3219629},

year  = {2018},

date = {2018-06-14},

booktitle = {Proc. of ACM Sigmetrics},

address = {Irvine, CA, USA},

abstract = {The QoS (Quality of Service) buffer management problem, with significant and diverse computer applications, e.g., in online cloud resource allocation problems, is a classic online admission control problem in the presence of resource constraints. In its basic setting, packets with different values according to their QoS requirements, arrive in online fashion to a switching node with limited buffer size. Then, the switch needs to make an immediate decision to either admit or reject the incoming packet based on the value of the packet and its buffer availability. The objective is to maximize the cumulative profit of the admitted packets, while respecting the buffer constraint. Even though the QoS buffer management problem was proposed more than a decade ago, no optimal online solution has been proposed in the literature. This paper contributes to this problem by proposing: 1) A fixed threshold-based online algorithm with smaller competitive ratio than the existing results; 2) an optimal deterministic online algorithm under fractional admission model in which a packet could be admitted partially; and 3) an optimal randomized online algorithm for the general problem. We consider the last result being the main contribution of this paper.},

keywords = {},

pubstate = {published},

tppubtype = {conference}

}

@conference{alinia2018competitive,

title = {Competitive Online Scheduling Algorithms with Applications in Deadline-Constrained EV Charging},

author = {Bahram Alinai and Sadegh M Talebi and Mohammad H Hajiesmaili and Ali Yekkehkhany and Noel Crespi},

url = {https://groups.cs.umass.edu/hajiesmaili/wp-content/uploads/sites/24/2020/01/iwqos2018.pdf},

doi = { 10.1109/IWQoS.2018.8624184},

year  = {2018},

date = {2018-01-01},

booktitle = {Proc. of IEEE/ACM International Symposium on Quality of Service (IWQoS)},

address = {Banff, Alberta, Canada},

abstract = {This paper studies the classical problem of online scheduling of deadline-sensitive jobs with partial values and investigates its extension to Electric Vehicle (EV) charging scheduling by taking into account the processing rate limit of jobs and charging station capacity constraint. The problem lies in the category of time-coupled online scheduling problems without availability of future information. This paper proposes two online algorithms, both of which are shown to be (2-[1/U])-competitive, where U is the maximum scarcity level, a parameter that indicates demand-to-supply ratio. The first proposed algorithm is deterministic, whereas the second is randomized and enjoys a lower computational complexity. When U grows large, the performance of both algorithms approaches that of the state-of-the-art for the case where there is processing rate limits on the jobs. Nonetheless, in realistic cases, where U is typically small, the proposed algorithms enjoy a much lower competitive ratio. To carry out the competitive analysis of our algorithms, we present a proof technique, which is novel to the best of our knowledge. This technique could also be used to simplify the competitive analysis of some existing algorithms, and thus could be of independent interest.

},

keywords = {},

pubstate = {published},

tppubtype = {conference}

}

@conference{hajiesmaili2017understanding,

title = {Understanding the inefficiency of security-constrained economic dispatch},

author = {Mohammad H Hajiesmaili and Desmond Cai and Enrique Mallada},

url = {https://groups.cs.umass.edu/hajiesmaili/wp-content/uploads/sites/24/2020/01/cdc.2017.pdf},

doi = { 10.1109/CDC.2017.8263947},

year  = {2017},

date = {2017-12-01},

booktitle = {Proc. IEEE Annual Conference on Decision and Control (CDC)},

pages = {2035-2040},

address = {Melbourne, Australia},

abstract = {The security-constrained economic dispatch (SCED) problem tries to maintain the reliability of a power network by ensuring that a single failure does not lead to a global outage. The previous research has mainly investigated SCED by formulating the problem in different modalities, e.g. preventive or corrective, and devising efficient solutions for SCED. In this paper, we tackle a novel and important direction, and analyze the economic cost of incorporating security constraints in economic dispatch. Inspired by existing inefficiency metrics in game theory and computer science, we introduce notion of price of security as a metric that formally characterizes the economic inefficiency of SCED as compared to the original problem without security constraints. Then, we focus on the preventive approach in a simple topology comprising two buses and two lines, and investigate the impact of generation availability and demand distribution on the price of security. Moreover, we explicitly derive the worst-case input instance that leads to the maximum price of security. By experimental study on two test-cases, we verify the analytical results and provide insights for characterizing the price of security in general networks.},

keywords = {},

pubstate = {published},

tppubtype = {conference}

}

@conference{yang2017offering,

title = {Hour-Ahead Offering Strategies in Electricity Market for Power Producers with Storage and Intermittent Supply},

author = {Lin Yang* and Mohammad H Hajiesmaili* and Hanling Yi and Minghua Chen},

url = {https://groups.cs.umass.edu/hajiesmaili/wp-content/uploads/sites/24/2020/01/sigmetrics.2017.pdf},

doi = {10.1145/3143314.3078543},

year  = {2017},

date = {2017-06-17},

booktitle = {Proc. of ACM Sigmetrics },

journal = {SIGMETRICS Perform. Eval. Rev.},

address = {Urbana, IL, USA},

abstract = {This paper proposes online offering strategies for a storage-assisted renewable power producer that participates in hour-ahead electricity market. The online strategy determines the offering price and volume, while no exact or stochastic future information is available in a time-coupled setting in the presence of the storage. The proposed online strategy achieves the best possible competitive ratio of O(log θ), where θ is the ratio between the maximum and minimum clearing prices. Trace-driven experiments demonstrate that the proposed strategy achieves close-to-optimal performance.

},

note = {*equal contribution, poster paper},

keywords = {},

pubstate = {published},

tppubtype = {conference}

}

@conference{hajiesmaili2017crowd,

title = {Crowd-Sourced Storage-Assisted Demand Response in Microgrids},

author = {Mohammad H Hajiesmaili and Minghua Chen and Enrique Mallada and Chi-Kin Chau},

url = {https://groups.cs.umass.edu/hajiesmaili/wp-content/uploads/sites/24/2020/01/eEnergy2017.pdf},

doi = {10.1145/3077839.3077841},

year  = {2017},

date = {2017-01-01},

booktitle = {Proc. of the Eighth International Conference on Future Energy Systems (ACM eEnergy)},

pages = {91--100},

address = {Shatin, Hong Kong},

abstract = {This paper studies the problem of utilizing heterogeneous energy storage systems, including electric vehicles and residential batteries, to perform demand-response in microgrids. The objective is to minimize the operational cost while fulfilling the demand-response requirement. The design space is to select and schedule a subset of available storage devices that are heterogeneous in operating cost, capacity, and availability in time. Designing a performance-optimized solution, however, is challenging due to the combinatorial nature of the problem with mixed packing and covering constraints, and the essential need for online solution design in practical scenarios where both demand-response requirement and the profile of user-owned storage systems arrive online. We tackle these challenges and design several online algorithms by leveraging a recent theoretical computer science technique which uses a problem-specific exponential potential function to solve online mixed packing and covering problems. We show that the fractional version of the algorithm achieves a logarithmic bi-criteria competitive ratio. Empirical trace-driven experiments demonstrate that our algorithms perform much better than the theoretical bounds and achieve close-to-optimal performance.},

note = {Short version appeared in ACM Greenmetrics 2017},

keywords = {},

pubstate = {published},

tppubtype = {conference}

}

@conference{hajiesmaili2016Online,

title = {Online Microgrid Energy Generation Scheduling Revisited: The Benefits of Randomization and Interval Prediction},

author = {Mohammad H Hajiesmaili and Chi-Kin Chau and Minghua Chen and Longbo Huang},

url = {https://groups.cs.umass.edu/hajiesmaili/wp-content/uploads/sites/24/2020/01/eEnergy2016.1.pdf},

doi = {10.1145/2934328.2934329},

isbn = {978-1-4503-4393-0},

year  = {2016},

date = {2016-01-01},

booktitle = {Proc. of the Seventh International Conference on Future Energy Systems (ACM eEnergy)},

pages = {1:1--1:11},

address = {Waterloo, Ontario, Canada},

abstract = {Energy generation scheduling is a fundamental problem in microgrid design that determines the on/off status and the output level of energy sources with the goal of minimizing the cost and satisfying both electricity and heat demand. The uncertainty in both renewable generation and microgrid demand makes the problem drastically different from its counterparts and in traditional power systems and brings out the essential need of online algorithm design. In the literature, an online deterministic algorithm called CHASE has achieved a competitive ratio of 3, which is the best possible among deterministic algorithms. In addition, it has been shown the accurate prediction can improve performance. This paper revisits the problem by investigating the benefits of randomization and interval prediction, i.e., relaxing accurate prediction assumption by considering an interval of valid ranges for future demand. We propose rCHASE, a randomized algorithm that achieves competitive ratio of around 2.128, improving beyond the best deterministic algorithm. Then, we propose iCHASE, an interval prediction-aware algorithm that is built upon rCHASE and a new extension we developed for the classic ski-rental problem. Our trace-driven experiments demonstrate that iCHASE outperforms CHASE; the average cost reduction of iCHASE is 15.85%, while CHASE reduces the cost by 9.1%.},

note = {Best paper candidate},

keywords = {},

pubstate = {published},

tppubtype = {conference}

}

@conference{deng2016energy,

title = {Energy-efficient Timely Transportation of Long-haul Heavy-duty Trucks},

author = {Lei Deng and Mohammad H Hajiesmaili and Minghua Chen and Haibo Zeng},

url = {https://groups.cs.umass.edu/hajiesmaili/wp-content/uploads/sites/24/2020/01/eEnergy.2016.2.pdf},

doi = {10.1145/2934328.2934338},

isbn = {978-1-4503-4393-0},

year  = {2016},

date = {2016-01-01},

booktitle = {Proc. of the Seventh International Conference on Future Energy Systems (ACM eEnergy)},

pages = {10:1--10:12},

address = {Waterloo, Ontario, Canada},

abstract = {We consider a timely transportation problem where a heavy-duty truck travels between two locations across the national highway system, subject to a hard deadline constraint. Our objective is to minimize the total fuel consumption of the truck, by optimizing both route planning and speed planning. The problem is important for cost-effective and environment-friendly truck operation, and it is uniquely challenging due to its combinatorial nature as well as the need of considering hard deadline constraint. We first show that the problem is NP-Complete; thus exact solution is computational prohibited unless P=NP. We then design a fully polynomial time approximation scheme (FPTAS) that attains an approximation ratio of 1 + ∈ with a network-size induced complexity of O(mn2/∈2), where m and n are the numbers of nodes and edges, respectively. While achieving highly-preferred theoretical performance guarantee, the proposed FPTAS still suffers from long running time when applying to national-wide highway systems with tens of thousands of nodes and edges. Leveraging elegant insights from studying the dual of the original problem, we design a fast heuristic solution with O(m + n log n) complexity. The proposed heuristic allows us to tackle the energy-efficient timely transportation problem on large-scale national highway systems. We further characterize a condition under which our heuristic generates an optimal solution. We observe that the condition holds in most of the practical instances in numerical experiments, justifying the superior empirical performance of our heuristic. We carry out extensive numerical experiments using real-world truck data over the actual U.S. highway network. The results show that our proposed solutions achieve 17% (resp. 14%) fuel consumption reduction, as compared to the fastest path (resp. shortest path) algorithm adapted from common practice.},

note = {Best paper candidate},

keywords = {},

pubstate = {published},

tppubtype = {conference}

}

@conference{hajiesmaili2015utility,

title = {Utility-optimal dynamic rate allocation under average end-to-end delay requirements},

author = {Mohammad H Hajiesmaili and Mohammad Sadegh Talebi and Ahmad Khonsari},

url = {https://groups.cs.umass.edu/hajiesmaili/wp-content/uploads/sites/24/2020/01/cdc2015.pdf},

doi = {10.1109/CDC.2015.7402975},

year  = {2015},

date = {2015-12-01},

booktitle = {Proc. IEEE Conference on Decision and Control (CDC)},

pages = {4842-4847},

address = {Osaka, Japan},

abstract = {QoS-aware networking applications such as real-time streaming and video surveillance systems require nearly fixed average end-to-end delay over long periods to communicate efficiently, although may tolerate some delay variations in short periods. This variability exhibits complex dynamics that makes rate control of such applications a formidable task. This paper addresses rate allocation for heterogeneous QoS-aware applications that preserves the long-term average end-to-end delay constraint while, similar to Dynamic Network Utility Maximization (DNUM), strives to achieve the maximum network utility aggregated over a fixed time interval. Since capturing temporal dynamics in QoS requirements of sources is allowed in our system model, we incorporate a novel time-coupling constraint in which delay-sensitivity of sources is considered such that a certain end-to-end average delay for each source over a pre-specified time interval is satisfied. We propose DA-DNUM algorithm, as a dual-based solution, which allocates source rates for the next time interval in a distributed fashion, given the knowledge of network parameters in advance. Through numerical experiments, we show that DA-DNUM gains higher average link utilization and a wider range of feasible scenarios in comparison with the best, to our knowledge, rate control schemes that may guarantee such constraints on delay.

},

keywords = {},

pubstate = {published},

tppubtype = {conference}

}

@conference{hajiesmaili2015cost,

title = {Cost-Effective Low-Delay Cloud Video Conferencing},

author = {Mohammad H Hajiesmaili and Lok To Mak and Zhi Wang and Chuan Wu and Minghua Chen and Ahmad Khonsari},

url = {https://groups.cs.umass.edu/hajiesmaili/wp-content/uploads/sites/24/2020/01/icdcs2015.pdf},

doi = {10.1109/ICDCS.2015.19},

year  = {2015},

date = {2015-06-01},

booktitle = {Prof. of IEEE International Conference on Distributed Computing Systems (IEEE ICDCS)},

pages = {103-112},

address = {Columbus, OH, USA},

abstract = {The cloud computing paradigm has been advocated in recent video conferencing system design, which exploits the rich on-demand resources spanning multiple geographic regions of a distributed cloud, for better conferencing experience. A typical architectural design in cloud environment is to create video conferencing agents, i.e., Virtual machines, in each cloud site, assign users to the agents, and enable inter-user communication through the agents. Given the diversity of devices and network connectivities of the users, the agents may also transcode the conferencing streams to the best formats and bitrates. In this architecture, two key issues exist on how to effectively assign users to agents and how to identify the best agent to perform a Transcoding task, which are nontrivial due to the following: (1) the existing proximity-based assignment may not be optimal in terms of inter-user delay, which fails to consider the whereabouts of the other users in a conferencing session, (2) the agents may have heterogeneous bandwidth and processing availability, such that the best Transco ding agents should be carefully identified, for cost minimization while best serving all the users requiring the transcoded streams. To address these challenges, we formulate the user-to-agent assignment and Transco ding-agent selection problems, which targets at minimizing the operational cost of the conferencing provider while keeping the conferencing delay low. The optimization problem is combinatorial in nature and difficult to solve. Using Markov approximation framework, we design a decentralized algorithm that provably converges to a bounded neighborhood of the optimal solution. An agent ranking scheme is also proposed to properly initialize our algorithm so as to improve its convergence. The results from a prototype system implementation show that our design in a set of Internet-scale scenarios reduces the operational cost by 77% as compared to a commonly-adopted alternative, while sim...

},

keywords = {},

pubstate = {published},

tppubtype = {conference}

}

@conference{alinia2015construction,

title = {On the Construction of Maximum-Quality Aggregation Trees in Deadline-Constrained WSNs},

author = {Bahram Alinia and Mohammad H Hajiesmaili and Ahmad Khonsari},

url = {https://groups.cs.umass.edu/hajiesmaili/wp-content/uploads/sites/24/2020/01/infocom.2015.pdf},

doi = { 10.1109/INFOCOM.2015.7218386},

year  = {2015},

date = {2015-04-01},

booktitle = {Proc. IEEE Conference on Computer Communications (INFOCOM)},

pages = {226-234},

address = {Hong Kong},

abstract = {In deadline-constrained data aggregation in wireless sensor networks (WSNs), the imposed sink deadline in an interference-limited network hinders participation of all sensor nodes in data aggregation. Thus, a subset of nodes can contribute in aggregation and quality of aggregation (QoA) increases with the growth of the number of participating nodes. Scheduling the nodes' transmissions is a central problem, which aims to maximize the QoA, while satisfying the sink deadline, i.e., on-time delivery of the sensed data to the sink node. Although the previous studies have proposed optimal scheduling algorithms to this problem given a particular aggregation tree, there is no work on constructing optimal tree in this context. The underlying aggregation tree can make a big difference on QoA since we demonstrate that the ratio between the maximum achievable QoAs of different trees could be as large as O(2 D ), where D is the sink deadline. In this paper, we cast an optimization problem to address optimal tree construction for deadline-constrained data aggregation in WSNs. The problem is combinatorial in nature and difficult to solve as we prove its NP-hardness. We employ Markov approximation framework and devise two distributed algorithms with different computation overheads to find bounded close-to-optimal solutions. Simulation experiments in a set of representative randomly-generated scenarios show that the proposed algorithms significantly improve QoA by 101% and 93% on average compared to the best, to our knowledge, existing alternative methods.

},

keywords = {},

pubstate = {published},

tppubtype = {conference}

}

@conference{zhang2015peak,

title = {Peak-Aware Online Economic Dispatching for Microgrids},

author = {Ying Zhang and Mohammad Hassan Hajiesmaili and Minghua Chen},

url = {https://groups.cs.umass.edu/hajiesmaili/wp-content/uploads/sites/24/2020/01/eEnergy.2015.pdf},

doi = {10.1145/2768510.2768538},

year  = {2015},

date = {2015-01-01},

booktitle = {Proc.of the Sixth International Conference on Future Energy Systems (ACM eEnergy)},

pages = {27--36},

address = {Bangalore, India},

abstract = {By employing local renewable energy sources and power generation units while connected to the central grid, microgrid can usher in great benefits in terms of cost efficiency, power reliability, and environmental awareness. Economic dispatching is a central problem in microgrid operation, which aims at effectively scheduling various energy sources to minimize the operating cost while satisfying the electricity demand. Designing intelligent economic dispatching strategies for microgrids, however, is drastically different from that for conventional central grids, due to two unique challenges. First, the erratic renewable energy emphasizes the need for online algorithms. Second, the widely-adopted peak-based pricing scheme brings out the need for new peak-aware strategy design. In this paper, we tackle these critical challenges and devise peak-aware online economic dispatching algorithms. For microgrids with fast-responding generators, we prove that our deterministic and randomized algorithms achieve the best possible competitive ratios 2 - β and e/(e - 1 + β), respectively, where β ∈ [0,1] is the ratio between the minimum grid spot price and the local-generation price. Our results characterize the fundamental price of uncertainty of the problem. For microgrids with slow-responding generators, we first show that a large competitive ratio is inevitable. Then we leverage limited prediction of electricity demand and renewable generation to improve the competitiveness of the algorithms. By extensive empirical evaluations using real-world traces, we show that our online algorithms achieve near offline-optimal performance. In a representative scenario, our algorithm achieves 23% and 11% cost reduction as compared to the case without local generation units and the case using peak-oblivious algorithms, respectively.



},

note = {Best paper candidate},

keywords = {},

pubstate = {published},

tppubtype = {conference}

}