1 citations · 1 across the 5 of their papers we have counts for
8 papers · 1 filter
Improved and Deterministic Online Service with Deadlines or Delay
Noam Touitou
We consider the problem of online service with delay on a general metric space, first presented by Azar, Ganesh, Ge and Panigrahi (STOC 2017). The best known randomized algorithm f…
Online Graph Algorithms with Predictions
Yossi Azar, Debmalya Panigrahi, Noam Touitou
Online algorithms with predictions is a popular and elegant framework for bypassing pessimistic lower bounds in competitive analysis. In this model, online algorithms are supplied…
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…
Improved Online Algorithm for Weighted Flow Time
Yossi Azar, Noam Touitou
We discuss one of the most fundamental scheduling problem of processing jobs on a single machine to minimize the weighted flow time (weighted response time). Our main result is a $…