Search for: All records

Recent advances in omnidirectional cameras and AR/VR headsets have spurred the adoption of 360\(^{\circ}\)videos, which are widely believed to be the future of online video streaming. 360\(^{\circ}\)videos allow users to wear a head-mounted display (HMD) and experience the video as if they are physically present in the scene. Streaming high-quality 360\(^{\circ}\)videos at scale is an unsolved problem that is more challenging than traditional (2D) video delivery. The data rate required to stream 360\(^{\circ}\)videos is an order of magnitude more than traditional videos. Further, the penalty for rebuffering events where the video freezes or displays a blank screen is more severe as it may cause cybersickness. We propose an online adaptive bitrate (ABR) algorithm for 360\(^{\circ}\)videos calledBOLA360that runs inside the client’s video player and orchestrates the download of video tiles from the server to maximize the quality-of-experience (QoE) of the user.BOLA360conserves bandwidth by downloading only those video tiles that are likely to fall within the field-of-view (FOV) of the user. In addition,BOLA360continually adapts the bitrate of the downloaded video tiles so as to enable a smooth playback without rebuffering. We prove thatBOLA360is near-optimal with respect to an optimal offline algorithm that maximizes QoE. Further, we evaluateBOLA360on a wide range of network and user head movement profiles and show that it provides\(6\%\)to\(110\%\)improvements to the QoE of state-of-the-art algorithms. While ABR algorithms for traditional (2D) videos have been well-studied over the last decade, our work is the first ABR algorithm for 360\(^{\circ}\)videos withboththeoretical and empirical guarantees on its performance. 

Greenhouse gas emissions from the residential sector represent a large fraction of global emissions and must be significantly curtailed to achieve ambitious climate goals. To stimulate the adoption of relevant technologies such as rooftop PV and heat pumps, governments and utilities have designedincentivesthat encourage adoption of decarbonization technologies. However, studies have shown that many of these incentives are inefficient since a substantial fraction of spending does not actually promote adoption. Further, these incentives are not equitably distributed across socioeconomic groups. In this article, we present a novel data-driven approach that adopts a holistic, emissions-based, and city-scale perspective on decarbonization. We propose an optimization model that dynamically allocates a total incentive budget to households to directly maximize the resultantcarbon emissions reduction– this is in contrast to prior work, which focuses on metrics such as the number of new installations. We leverage techniques from the multi-armed bandits problem to estimatehuman factors, such as a household’s willingness to adopt new technologies given a certain incentive. We apply our proposed dynamic incentive framework to a city in the Northeast U.S., using real household energy data, grid carbon intensity data, and future price scenarios. We compare our learning-based technique to two baselines, one “status-quo” baseline using incentives offered by a state and utility, and one simple heuristic baseline. With these baselines, we show that our learning-based technique significantly outperforms both the status-quo baseline and the heuristic baseline, achieving up to 37.88% higher carbon reductions than the status-quo baseline and up to 28.76% higher carbon reductions compared to the heuristic baseline. Additionally, our incentive allocation approach is able to achieve significant carbon reduction even in a broad set of environments, with varying values for electricity and gas prices, and for carbon intensity of the grid. Finally, we show that our framework can accommodateequity-awareconstraints to preserve an equitable allocation of incentives across socioeconomic groups while achieving 83.34% of the carbon reductions of the optimal solution on average. 

Motivated by the emerging paradigm of resource allocation that integrates classical objectives, such as cost minimization, with societal objectives, such as carbon awareness, this paper proposes a general framework for the online fair allocation of reusable resources. Within this framework, an online decision-maker seeks to allocate a finite resource with capacityCto a sequence of requests arriving with unknown distributions of types, utilities, and resource usage durations. To accommodate diverse objectives, the framework supports multiple actions and utility types, and the goal is to achieve max-min fairness among utilities, i.e., maximize the minimum time-averaged utility across all utility types. Our performance metric is an (α,β)-competitive guarantee of the form: ALG ≥ α • OPT^*- O(T^β-1),; α, β ∈ (0, 1], where OPT^*and ALG are the time-averaged optimum and objective value achieved by the decision maker, respectively. We propose a novel algorithm that achieves a competitive guarantee of (1-O(√(log C/C)), 2/3) under the bandit feedback. As resource capacity increases, the multiplicative competitive ratio term 1-O(√ logC/C) asymptotically approaches optimality. Notably, when the resource capacity exceeds a certain threshold, our algorithm achieves an improved competitive guarantee of (1, 2/3). Our algorithm employs an optimistic penalty-weight mechanism coupled with a dual exploration-discarding strategy to balance resource feasibility, exploration, and fairness among utilities. 

We introduce and study spatiotemporal online allocation with deadline constraints (SOAD), a new online problem motivated by emerging challenges in sustainability and energy. In SOAD, an online player completes a workload by allocating and scheduling it on the points of a metric space (X,d) while subject to a deadlineT. At each time step, a service cost function is revealed that represents the cost of servicing the workload at each point, and the player must irrevocably decide the current allocation of work to points. Whenever the player moves this allocation, they incur a movement cost defined by the distance metricd(⋅, ⋅) that captures, e.g., an overhead cost. SOAD formalizes the open problem of combining general metrics and deadline constraints in the online algorithms literature, unifying problems such as metrical task systems and online search. We propose a competitive algorithm for SOAD along with a matching lower bound establishing its optimality. Our main algorithm, ST-CLIP, is a learning-augmented algorithm that takes advantage of predictions (e.g., forecasts of relevant costs) and achieves an optimal consistency-robustness trade-off. We evaluate our proposed algorithms in a simulated case study of carbon-aware spatiotemporal workload management, an application in sustainable computing that schedules a delay-tolerant batch compute job on a distributed network of data centers. In these experiments, we show that ST-CLIP substantially improves on heuristic baseline methods.