skip to main content
Explore Scholarly Publications and Datasets in the NSF-PAR

  • Home
  • Search Results
  • Page 1 of 2

Search for: All records

Creators/Authors contains: "Hajiesmaili, Mohammad H."

Note: When clicking on a Digital Object Identifier (DOI) number, you will be taken to an external site maintained by the publisher. Some full text articles may not yet be available without a charge during the embargo (administrative interval).
What is a DOI Number?

Some links on this page may take you to non-federal websites. Their policies may differ from this site.

  1. ; ; ; ; ( , ACM SIGMETRICS Performance Evaluation Review)
    In this work, we study the online multidimensional knapsack problem (called 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 m-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 with several relevant applications such as in virtualmore »machine allocation, job scheduling, and all-or-nothing flow maximization over a graph. We develop an online algorithm for OMdKP that uses an exponential reservation function to make online admission decisions. Our competitive analysis shows that the proposed online algorithm achieves the competitive ratio of O(log (Θ α)), where α is the ratio between the aggregate knapsack capacity and the minimum capacity over a single dimension and θ is the ratio between the maximum and minimum item unit values. We also show that the competitive ratio of our algorithm with exponential reservation function matches the lower bound up to a constant factor.« less
    Free, publicly-accessible full text available June 20, 2023
  2. ; ; ; ; ( , Proceedings of the ACM on Measurement and Analysis of Computing Systems)
    In this paper, we study the online multidimensional knapsack problem (called 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 m-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 inmore »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(θα ) and O(łogł(θα)), respectively, where α is the ratio between the aggregate knapsack capacity and the minimum capacity over a single dimension and θ 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.« less
    Free, publicly-accessible full text available December 14, 2022
  3. ; ; ; ; ( , Proceedings of the Twelfth ACM International Conference on Future Energy Systems (eEnergy))
    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 ofmore »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.« less
    Accepted Manuscript Full Text Available
  4. ; ; ; ; ( , Proceedings of the ACM on Interactive, Mobile, Wearable and Ubiquitous Technologies)
    While ride-sharing has emerged as a popular form of transportation in urban areas due to its on-demand convenience, it has become a major contributor to carbon emissions, with recent studies suggesting it is 47% more carbon-intensive than personal car trips. In this paper, we examine the feasibility, costs, and carbon benefits of using electric bike-sharing---a low carbon form of ride-sharing---as a potential substitute for shorter ride-sharing trips, with the overall goal of greening the ride-sharing ecosystem. Using public datasets from New York City, our analysis shows that nearly half of the taxi and rideshare trips in New York are shortsmore »trips of less than 3.5km, and that biking is actually faster than using a car for ultra-short trips of 2km or less. We analyze the cost and carbon benefits of different levels of ride substitution under various scenarios. We find that the additional bikes required to satisfy increased demand from ride substitution increases sub-linearly and results in 6.6% carbon emission reduction for 10% taxi ride substitution. Moreover, this reduction can be achieved through a hybrid mix that requires only a quarter of the bikes to be electric bikes, which reduces system costs. We also find that expanding bike-share systems to new areas that lack bike-share coverage requires additional investments due to the need for new bike stations and bike capacity to satisfy demand but also provides substantial carbon emission reductions. Finally, frequent station repositioning can reduce the number of bikes needed in the system by up to a third for a minimal increase in carbon emissions of 2% from the trucks required to perform repositioning, providing an interesting tradeoff between capital costs and carbon emissions.« less
    Full Text Available 
  5. ; ; ; ; ( , Advances in Neural Information Processing Systems 33 (NeurIPS 2020))
    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 demonstratingmore »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.« less
    Accepted Manuscript Full Text Available
  6. ; ; ; ; ; ( , ACM SIGMETRICS Performance Evaluation Review)
    Full Text Available 
  7. ; ; ; ; ; ( , Eleventh ACM International Conference on Future Energy Systems)
    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 onmore »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.« less
    Full Text Available 
  8. ; ; ; ; ; ( , Sigmetrics)
    Full Text Available 
  9. ; ; ; ; ; ( , Proceedings of the ACM on Measurement and Analysis of Computing Systems)
    Full Text Available 
  10. ; ; ; ; ( , IEEE Transactions on Sustainable Computing)
    Electricity bill constitutes a significant portion of operational costs for large scale data centers. Empowering data centers with on-site storages can reduce the electricity bill by shaping the energy procurement from deregulated electricity markets with real-time price fluctuations. This work focuses on designing energy procurement and storage management strategies to minimize the electricity bill of storage-assisted data centers. Designing such strategies is challenging since the net energy demand of the data center and electricity market prices are not known in advance, and the underlying problem is coupled over time due to evolution of the storage level. Using competitive ratio asmore »the performance measure, we propose an online algorithm that determines the energy procurement and storage management strategies using a threshold based policy. Our algorithm achieves the optimal competitive ratio of as a function of the price fluctuation ratio. We validate the algorithm using data traces from electricity markets and data-center energy demands. The results show that our algorithm achieves close to the offline optimal performance and outperforms existing alternatives.%« less
    Full Text Available