5 papers
Distortion-Oblivious Algorithms for Minimizing Flow Time
Yossi Azar, Stefano Leonardi, Noam Touitou
We consider the classic online problem of scheduling on a single machine to minimize total flow time. In STOC 2021, the concept of robustness to distortion in processing times was…
Flow Time Scheduling with Uncertain Processing Time
Yossi Azar, Stefano Leonardi, Noam Touitou
We consider the problem of online scheduling on a single machine in order to minimize weighted flow time. The existing algorithms for this problem (STOC '01, SODA '03, FOCS '18) al…
Beyond Tree Embeddings -- a Deterministic Framework for Network Design with Deadlines or Delay
Yossi Azar, Noam Touitou
We consider network design problems with deadline or delay. All previous results for these models are based on randomized embedding of the graph into a tree (HST) and then solving…
General Framework for Metric Optimization Problems with Delay or with Deadlines
Yossi Azar, Noam Touitou
In this paper, we present a framework used to construct and analyze algorithms for online optimization problems with deadlines or with delay over a metric space. Using this framewo…
Set Cover with Delay -- Clairvoyance is not Required
Yossi Azar, Ashish Chiplunkar, Shay Kutten +1
In most online problems with delay, clairvoyance (i.e. knowing the future delay of a request upon its arrival) is required for polylogarithmic competitiveness. In this paper, we sh…