A5064272947- Optimization and Search Problems
- Complexity and Algorithms in Graphs
- Scheduling and Optimization Algorithms
- Computability, Logic, AI Algorithms
- Advanced Bandit Algorithms Research
- Facility Location and Emergency Management
- Auction Theory and Applications
- Distributed systems and fault tolerance
- Cryptography and Data Security
- Advanced Graph Theory Research
- Distributed and Parallel Computing Systems
- Advanced Manufacturing and Logistics Optimization
- VLSI and FPGA Design Techniques
- Sparse and Compressive Sensing Techniques
- Advanced Image Processing Techniques
- Cooperative Communication and Network Coding
- Mobile Crowdsensing and Crowdsourcing
- Advanced Wireless Network Optimization
- Stochastic Gradient Optimization Techniques
Tel Aviv University
2017-2023
We consider the problem of online scheduling on a single machine in order to minimize weighted flow time. The existing algorithms for this (STOC '01, SODA '03, FOCS '18) all require exact knowledge processing time each job. This assumption is crucial, as even slight perturbation would lead polynomial competitive ratio. However, very rarely holds real-life scenarios.
In this paper, we present a framework used to construct and analyze algorithms for online optimization problems with deadlines or delay over metric space. Using framework, several different problems. We an O(D <sup xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">^</sup> 2) -competitive deterministic algorithm multilevel aggregation on tree of depth D, exponential improvement the xmlns:xlink="http://www.w3.org/1999/xlink">4</sup> 2...
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 problem this tree. show that is not necessary. In particular, we deterministic framework which embedding. This enables us to provide poly-log( n)-competitive algorithms Steiner tree, generalized node weighted (non-uniform) facility location directed deadlines delay (where n number nodes). Our also give improved...
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 for this problem, Azar Touitou (FOCS 2019), is O(log2 n)-competitive, where n number points in space. This also result special case deadlines, which independent interest.
We discuss one of the most fundamental scheduling problem processing jobs on a single machine to minimize weighted flow time (weighted response time). Our main result is O(log P)-competitive algorithm, where P maximum-to-minimum ratio, improving upon <sup xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">2</sup> P)competitive algorithm Chekuri, Khanna and Zhu (STOC 2001). also design D)-competitive D density ratio jobs. Finally, we show how combine...
In most online problems with delay, clairvoyance (i.e. knowing the future delay of a request upon its arrival) is required for polylogarithmic competitiveness. this paper, we show that not case set cover (SCD) - specifically, present first non-clairvoyant algorithm, which O(log n log m)-competitive, where number elements and m sets. This matches best known result classic (a special SCD). Moreover, does allow significant improvement lower bounds Ω(√{log n}) m}) SCD apply clairvoyant case....
Online algorithms with predictions is a popular and elegant framework for bypassing pessimistic lower bounds in competitive analysis. In this model, online are supplied future predictions, the goal ratio to smoothly interpolate between best offline as function of prediction error. paper, we study graph problems predictions. Our contributions following: * The first question defining For graph/metric problems, there can be two types error, locations that not predicted, predicted but actual do...
We consider the classic online problem of scheduling on a single machine to minimize total flow time. In STOC 2021, concept robustness distortion in processing times was introduced: for every factor $μ$, an $O(μ^2)$-competitive algorithm $\operatorname{ALG}_μ$ which handles distortions up $μ$ presented. However, using that result requires one know input advance, is impractical. present first \emph{distortion-oblivious} algorithms: algorithms are competitive \emph{every} distortion, and thus...
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 for this problem, Azar Touitou (FOCS 2019), is $O(\log^2 n)$-competitive, where $n$ number points in space. This also result special case deadlines, which independent interest. In paper, we present $O(\log n)$-competitive deterministic algorithms deadlines or delay, improving upon results from FOCS 2019....
We discuss one of the most fundamental scheduling problem processing jobs on a single machine to minimize weighted flow time (weighted response time). Our main result is $O(\log P)$-competitive algorithm, where $P$ maximum-to-minimum ratio, improving upon $O(\log^{2}P)$-competitive algorithm Chekuri, Khanna and Zhu (STOC 2001). also design D)$-competitive $D$ density ratio jobs. Finally, we show how combine these results with Bansal Dhamdhere (SODA 2003) achieve...
In most online problems with delay, clairvoyance (i.e. knowing the future delay of a request upon its arrival) is required for polylogarithmic competitiveness. this paper, we show that not case set cover (SCD) -- specifically, present first non-clairvoyant algorithm, which $O(\log n \log m)$-competitive, where $n$ number elements and $m$ sets. This matches best known result classic (a special SCD). Moreover, does allow significant improvement - lower bounds $Ω(\sqrt{\log n})$ m})$ SCD apply...
In this paper, we present a framework used to construct and analyze algorithms for online optimization problems with deadlines or delay over metric space. Using framework, several different problems. We an $O(D^{2})$-competitive deterministic algorithm multilevel aggregation on tree of depth $D$, exponential improvement the $O(D^{4}2^{D})$-competitive Bienkowski et al. (ESA '16), where only previously-known was special case by Buchbinder (SODA '17). also $O(\log^{2}n)$-competitive randomized...
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 problem this tree. show that is not necessary. In particular, we deterministic framework which embedding. This enables us to provide $\text{poly-log}(n)$-competitive algorithms Steiner tree, generalized node weighted (non-uniform) facility location directed deadlines delay (where $n$ number nodes). Our also give...
Abstract Motivated by placement of jobs in physical machines, we introduce and analyze the problem online recoloring, or disengagement. In this problem, are given a set $n$ weighted vertices $k$-coloring (vertices represent jobs, colors machines). Edges, representing conflicts between inserted an fashion. After every edge insertion, algorithm must output proper vertices. The cost recoloring is sum weights whose color changed. Our aim to minimize competitive ratio algorithm, i.e., paid...
We consider the problem of online scheduling on a single machine in order to minimize weighted flow time. The existing algorithms for this (STOC '01, SODA '03, FOCS '18) all require exact knowledge processing time each job. This assumption is crucial, as even slight perturbation would lead polynomial competitive ratio. However, very rarely holds real-life scenarios. In paper, we present first algorithm which do not times jobs. Specifically, introduce Scheduling with Predicted Processing Time...