Zobrazeno 1 - 10
of 110
pro vyhledávání: '"Purohit, Manish"'
In this work we study the problem of using machine-learned predictions to improve the performance of online algorithms. We consider two classical problems, ski rental and non-clairvoyant job scheduling, and obtain new online algorithms that use predi
Externí odkaz:
http://arxiv.org/abs/2407.17712
Online load balancing for heterogeneous machines aims to minimize the makespan (maximum machine workload) by scheduling arriving jobs with varying sizes on different machines. In the adversarial setting, where an adversary chooses not only the collec
Externí odkaz:
http://arxiv.org/abs/2405.07949
We study scheduling of computation graphs to minimize peak memory consumption, an increasingly critical task due to the surge in popularity of large deep-learning models. This problem corresponds to the weighted version of the classical one-shot blac
Externí odkaz:
http://arxiv.org/abs/2312.13526
Autor:
Wang, Pengming, Sazanovich, Mikita, Ilbeyi, Berkin, Phothilimthana, Phitchaya Mangpo, Purohit, Manish, Tay, Han Yang, Vũ, Ngân, Wang, Miaosen, Paduraru, Cosmin, Leurent, Edouard, Zhernov, Anton, Huang, Po-Sen, Schrittwieser, Julian, Hubert, Thomas, Tung, Robert, Kurylowicz, Paula, Milan, Kieran, Vinyals, Oriol, Mankowitz, Daniel J.
Resource scheduling and allocation is a critical component of many high impact systems ranging from congestion control to cloud computing. Finding more optimal solutions to these problems often has significant impact on resource and time savings, red
Externí odkaz:
http://arxiv.org/abs/2305.07440
Online caching is among the most fundamental and well-studied problems in the area of online algorithms. Innovative algorithmic ideas and analysis -- including potential functions and primal-dual techniques -- give insight into this still-growing are
Externí odkaz:
http://arxiv.org/abs/2305.02508
Caching is a crucial component of many computer systems, so naturally it is a well-studied topic in algorithm design. Much of traditional caching research studies cache management for a single-user or single-processor environment. In this paper, we p
Externí odkaz:
http://arxiv.org/abs/2207.05975
Learning-augmented algorithms -- in which, traditional algorithms are augmented with machine-learned predictions -- have emerged as a framework to go beyond worst-case analysis. The overarching goal is to design algorithms that perform near-optimally
Externí odkaz:
http://arxiv.org/abs/2202.04262
Autor:
Saha, Sagnik, Purohit, Manish
In this paper, we study the active time scheduling problem. We are given n jobs with integral processing times each of which has an integral release time and deadline. The goal is to schedule all the jobs on a machine that can work on b jobs simultan
Externí odkaz:
http://arxiv.org/abs/2112.03255
We consider the online linear optimization problem, where at every step the algorithm plays a point $x_t$ in the unit ball, and suffers loss $\langle c_t, x_t\rangle$ for some cost vector $c_t$ that is then revealed to the algorithm. Recent work show
Externí odkaz:
http://arxiv.org/abs/2111.05257
We consider the problem of efficiently scheduling jobs with precedence constraints on a set of identical machines in the presence of a uniform communication delay. Such precedence-constrained jobs can be modeled as a directed acyclic graph, $G = (V,
Externí odkaz:
http://arxiv.org/abs/2108.02770