Yossi Azar

AAAI Conference 2025 Conference Paper

List Update with Prediction

• Yossi Azar
• Shahar Lewkowicz
• Varun Suriyanarayana

List Update is a fundamental problem in online algorithms, with a well-known 2-competitive algorithm that moves every requested element to the front. Randomization can slightly improve the competitive ratio to 1.6, but not beyond 1.5. However, practical inputs are not adversarial and one hopes to do better, particularly when additional information from a machine learning oracle is available. With access to predictions, the goal is to incur only a slight overhead compared to the prediction's accuracy, avoiding significant costs in case of substantial deviation. We propose a (1+epsilon)-smooth randomized algorithm, offering robustness of O(1/epsilon^4). This guarantees that the algorithm never exceeds a cost greater than 1+epsilon times the prediction cost, while maintaining a bound within O(1/epsilon^4) of the optimal cost for every possible sequence. In cases where no paid swaps are permitted for the prediction, we can improve robustness to O(1/epsilon^2) while retaining 1+epsilon smoothness. We complement these findings by demonstrating a lower bound of 1/epsilon on the robustness for deterministic algorithms and log(1/epsilon) for randomized ones. Finally, the experiments we have made show that our algorithms perform better than the standard competitive algorithms for this problem

AIJ Journal 2024 Journal Article

An α-regret analysis of adversarial bilateral trade

• Yossi Azar
• Amos Fiat
• Federico Fusco

We study sequential bilateral trade where sellers and buyers valuations are completely arbitrary (i. e. , determined by an adversary). Sellers and buyers are strategic agents with private valuations for the good and the goal is to design a mechanism that maximizes efficiency (or gain from trade) while being incentive compatible, individually rational and budget balanced. In this paper we consider gain from trade, which is harder to approximate than social welfare. We consider a variety of feedback scenarios and distinguish the cases where the mechanism posts one price and when it can post different prices for buyer and seller. We show several surprising results about the separation between the different scenarios. In particular we show that (a) it is impossible to achieve sublinear α-regret for any α < 2, (b) but with full feedback sublinear 2-regret is achievable; (c) with a single price and partial feedback one cannot get sublinear α regret for any constant α (d) nevertheless, posting two prices even with one-bit feedback achieves sublinear 2-regret, and (e) there is a provable separation in the 2-regret bounds between full and partial feedback.

NeurIPS Conference 2023 Conference Paper

Discrete-Smoothness in Online Algorithms with Predictions

• Yossi Azar
• Debmalya Panigrahi
• Noam Touitou

In recent years, there has been an increasing focus on designing online algorithms with (machine-learned) predictions. The ideal learning-augmented algorithm is comparable to the optimum when given perfect predictions (consistency), to the best online approximation for arbitrary predictions (robustness), and should interpolate between these extremes as a smooth function of the prediction error. In this paper, we quantify these guarantees in terms of a general property that we call discrete-smoothness, and achieve discrete-smooth algorithms for online covering, specifically the facility location and set cover problems. For set cover, our work improves the results of Bamas, Maggiori, and Svensson (2020) by augmenting consistency and robustness with smoothness guarantees. For facility location, our work improves on prior work by Almanza et al. (2021) by generalizing to nonuniform costs and also providing smoothness guarantees by augmenting consistency and robustness.

NeurIPS Conference 2022 Conference Paper

An $\alpha$-regret analysis of Adversarial Bilateral Trade

• Yossi Azar
• Amos Fiat
• Federico Fusco

We study sequential bilateral trade where sellers and buyers valuations are completely arbitrary ({\sl i. e. }, determined by an adversary). Sellers and buyers are strategic agents with private valuations for the good and the goal is to design a mechanism that maximizes efficiency (or gain from trade) while being incentive compatible, individually rational and budget balanced. In this paper we consider gain from trade which is harder to approximate than social welfare. We consider a variety of feedback scenarios and distinguish the cases where the mechanism posts one price and when it can post different prices for buyer and seller. We show several surprising results about the separation between the different scenarios. In particular we show that (a) it is impossible to achieve sublinear $\alpha$-regret for any $\alpha<2$, (b) but with full feedback sublinear $2$-regret is achievable (c) with a single price and partial feedback one cannot get sublinear $\alpha$ regret for any constant $\alpha$ (d) nevertheless, posting two prices even with one-bit feedback achieves sublinear $2$-regret, and (e) there is a provable separation in the $2$-regret bounds between full and partial feedback.

SODA Conference 2022 Conference Paper

Distortion-Oblivious Algorithms for Minimizing Flow Time

• Yossi Azar
• Stefano Leonardi 0001
• 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 introduced: for every distortion factor μ, an O ( μ 2 )-competitive algorithm ALG μ which handles distortions up to μ was presented. However, using that result requires one to know the distortion of the input in advance, which is impractical. We present the first distortion-oblivious algorithms: algorithms which are competitive for every input of every distortion, and thus do not require knowledge of the distortion in advance. Moreover, the competitive ratios of our algorithms are Õ ( μ ), which is a quadratic improvement over the algorithm from STOC 2021, and is nearly optimal (we show a randomized lower bound of Ω( μ ) on competitiveness).

SODA Conference 2022 Conference Paper

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 with future predictions and the goal is for the competitive ratio to smoothly interpolate between the best offline and online bounds as a function of the prediction error. In this paper, we study online graph problems with predictions. Our contributions are the following: The first question is defining prediction error. For graph/metric problems, there can be two types of error, locations that are not predicted, and locations that are predicted but the predicted and actual locations do not coincide exactly. We design a novel definition of prediction error called metric error with outliers to simultaneously capture both types of errors, which thereby generalizes previous definitions of error that only capture one of the two error types. We give a general framework for obtaining online algorithms with predictions that combines, in a “black box” fashion, existing online and offline algorithms, under certain technical conditions. To the best of our knowledge, this is the first general-purpose tool for obtaining online algorithms with predictions. Using our framework, we obtain tight bounds on the competitive ratio of several classical graph problems as a function of metric error with outliers: Steiner tree, Steiner forest, priority Steiner tree/forest, and uncapacitated/capacitated facility location. Both the definition of metric error with outliers and the general framework for combining offline and online algorithms are not specific to the problems that we consider in this paper. We hope that these will be useful for future work on other problems in this domain.

STOC Conference 2021 Conference Paper

Flow time scheduling with uncertain processing time

• Yossi Azar
• Stefano Leonardi 0001
• 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) all require exact knowledge of the processing time of each job. This assumption is crucial, as even a slight perturbation of the processing time would lead to polynomial competitive ratio. However, this assumption very rarely holds in real-life scenarios. In this paper, we present the first algorithm for weighted flow time which do not require exact knowledge of the processing times of jobs. Specifically, we introduce the Scheduling with Predicted Processing Time (SPPT) problem, where the algorithm is given a prediction for the processing time of each job, instead of its real processing time. For the case of a constant factor distortion between the predictions and the real processing time, our algorithms match all the best known competitiveness bounds for weighted flow time – namely O (log P ), O (log D ) and O (log W ), where P , D , W are the maximum ratios of processing times, densities, and weights, respectively. For larger errors, the competitiveness of our algorithms degrades gracefully.

SODA Conference 2021 Conference Paper

The Min-Cost Matching with Concave Delays Problem

• Yossi Azar
• Runtian Ren
• Danny Vainstein

We consider the problem of online min-cost perfect matching with concave delays. We begin with the single location variant. Specifically, requests arrive in an online fashion at a single location. The algorithm must then choose between matching a pair of requests or delaying them to be matched later on. The cost is defined by a concave function on the delay. Given linear or even convex delay functions, matching any two available requests is trivially optimal. However, this does not extend to concave delays. We solve this by providing an O (1)-competitive algorithm that is defined through a series of delay counters. Thereafter we consider the problem given an underlying n -points metric. The cost of a matching is then defined as the connection cost (as defined by the metric) plus the delay cost. Given linear delays, this problem was introduced by Emek et al. and dubbed the Min-cost perfect matching with linear delays (MPMD) problem. Liu et al. considered convex delays and subsequently asked whether there exists a solution with small competitive ratio given concave delays. We show this to be true by extending our single location algorithm and proving O (log n ) competitiveness. Finally, we turn our focus to the bichromatic case, wherein requests have polarities and only opposite polarities may be matched. We show how to alter our former algorithms to again achieve O (1) and O (log n ) competitiveness for the single location and for the metric case.

FOCS Conference 2020 Conference Paper

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 the problem on this tree. We show that this is not necessary. In particular, we design a deterministic framework for these problems which is not based on embedding. This enables us to provide deterministic poly-log( $n$ )-competitive algorithms for Steiner tree, generalized Steiner tree, node weighted Steiner tree, (non-uniform) facility location and directed Steiner tree with deadlines or with delay (where $n$ is the number of nodes). Our deterministic algorithms also give improved guarantees over some previous randomized results. In addition, we show a lower bound of poly $\text{log}(n)$ for some of these problems, which implies that our framework is optimal up to the power of the poly-log. Our algorithms and techniques differ significantly from those in all previous considerations of these problems.

AAMAS Conference 2019 Conference Paper

Efficient Allocation of Free Stuff

• Yossi Azar
• Allan Borodin
• Michal Feldman
• Amos Fiat
• Kineret Segal

We study online matching settings with selfish agents when everything is free. Inconsiderate agents break ties arbitrarily amongst equal maximal value available choices, even if the maximal value is equal to zero. Even for the simplest case of zero/one valuations, where agents arrive online in an arbitrary order, and agents are restricted to taking at most one item, the resulting social welfare may be negligible for a deterministic algorithm. This may be surprising when contrasted with the 1/2 approximation of the greedy algorithm, analogous to this setting, except that agents are considerate (i. e. , they don’t take zero-valued items). We overcome this challenge by introducing a new class of algorithms, which we refer to as prioritization algorithms. We show that upgrading a random subset of the agents to “business class" already improves the approximation to a constant. For more general valuations, we achieve a constant approximation using logn priority classes, when the valuations are known in advance. We extend these results to settings where agents have additive valuations and are restricted to taking up to some q ≥ 1 items. Our results are tight up to a constant.

FOCS Conference 2019 Conference Paper

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 framework, we present algorithms for several different problems. We present an O(D ^ 2) -competitive deterministic algorithm for online multilevel aggregation with delay on a tree of depth D, an exponential improvement over the O(D 4 2 D ) -competitive algorithm of Bienkowski et al. (ESA '16), where the only previously-known improvement was for the special case of deadlines by Buchbinder et al. (SODA '17). We also present an O(log 2 n) -competitive randomized algorithm for online service with delay over any general metric space of n points, improving upon the O(log 4 n) -competitive algorithm by Azar et al. (STOC '17). In addition, we present the problem of online facility location with deadlines. In this problem, requests arrive over time in a metric space, and need to be served until their deadlines by facilities that are opened momentarily for some cost. We also consider the problem of facility location with delay, in which the deadlines are replaced with arbitrary delay functions. For those problems, we present O(log 2 n) -competitive algorithms, with n the number of points in the metric space. The algorithmic framework we present includes techniques for the design of algorithms as well as techniques for their analysis.

FOCS Conference 2018 Conference Paper

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 O(log P)-competitive algorithm, where P is the maximum-to-minimum processing time ratio, improving upon the O(log 2 P)competitive algorithm of Chekuri, Khanna and Zhu (STOC 2001). We also design a O(log D)-competitive algorithm, where D is the maximum-to-minimum density ratio of jobs. Finally, we show how to combine these results with the result of Bansal and Dhamdhere (SODA 2003) to achieve a O(log(min(P, D, W)))competitive algorithm (where W is the maximum-tominimum weight ratio), without knowing P, D, W in advance. As shown by Bansal and Chan (SODA 2009), no constant-competitive algorithm is achievable for this problem.

SODA Conference 2018 Conference Paper

Randomized Algorithms for Online Vector Load Balancing

• Yossi Azar
• Ilan Reuven Cohen
• Debmalya Panigrahi

SODA Conference 2017 Conference Paper

Online Lower Bounds via Duality

• Yossi Azar
• Ilan Reuven Cohen
• Alan Roytman

In this paper, we exploit linear programming duality in the online setting, where input arrives on the fly, from the unique perspective of designing lower bounds (i. e. , hardness results) on the competitive ratio. In particular, we provide a systematic method (as opposed to ad hoc case analysis that is typically done) for obtaining online deterministic and randomized lower bounds on the competitive ratio for a wide variety of problems. We show the usefulness of our approach by providing new, tight hardness results for three diverse online problems: the Vector Bin Packing problem, Ad-auctions (and various online matching problems), and the Capital Investment problem. Our methods are sufficiently general that they can also be used to reconstruct existing lower bounds. Our approach is in stark contrast to previous works, which exploit linear programming duality to obtain positive results, often via the useful primal- dual scheme. We design a general recipe with the opposite aim of obtaining negative results via duality. The general idea behind our approach is to construct a parameterized family of primal linear programs based on a candidate collection of input sequences for proving the lower bound, where the objective function corresponds to optimizing the competitive ratio. Solving the parameterized family of primal linear programs optimally would yield a valid lower bound, but is a challenging task and limits the tools that can be applied, since analysis must be done precisely and exact optimality needs to be proved. To this end, we consider the corresponding parameterized family of dual linear programs and provide feasible solutions, where the objective function yields a lower bound on the competitive ratio. This opens up additional doors for analysis, including some of the techniques we employ (e. g. , continuous analysis, differential equations, etc.), as we need not be so careful about exact optimality. We are confident that our methods can be successfully applied to produce many more lower bounds for a wide array of online problems.

STOC Conference 2017 Conference Paper

Online service with delay

• Yossi Azar
• Arun Ganesh
• Rong Ge 0001
• Debmalya Panigrahi

In this paper, we introduce the online service with delay problem. In this problem, there are n points in a metric space that issue service requests over time, and a server that serves these requests. The goal is to minimize the sum of distance traveled by the server and the total delay (or a penalty function thereof) in serving the requests. This problem models the fundamental tradeoff between batching requests to improve locality and reducing delay to improve response time, that has many applications in operations management, operating systems, logistics, supply chain management, and scheduling. Our main result is to show a poly-logarithmic competitive ratio for the online service with delay problem. This result is obtained by an algorithm that we call the preemptive service algorithm . The salient feature of this algorithm is a process called preemptive service, which uses a novel combination of (recursive) time forwarding and spatial exploration on a metric space. We also generalize our results to k > 1 servers, and obtain stronger results for special metrics such as uniform and star metrics that correspond to (weighted) paging problems.

SODA Conference 2017 Conference Paper

Polylogarithmic Bounds on the Competitiveness of Min-cost Perfect Matching with Delays

• Yossi Azar
• Ashish Chiplunkar
• Haim Kaplan

We consider the problem of online Min-cost Perfect Matching with Delays (MPMD) recently introduced by Emek et al, (STOC 2016). This problem is defined on an underlying n -point metric space. An adversary presents real-time requests online at points of the metric space, and the algorithm is required to match them, possibly after keeping them waiting for some time. The cost incurred is the sum of the distances between matched pairs of requests (the connection cost), and the sum of the waiting times of the requests (the delay cost). We prove the first logarithmic upper bound and the first polylogarithmic lower bound on the randomized competitive ratio of this problem. We present an algorithm with a competitive ratio of O (log n ), which improves the upper bound of O log 2 n + logΔ) of Emek et al, by removing the dependence on Δ, the aspect ratio of the metric space (which can be unbounded as a function of n ). The core of our algorithm is a deterministic algorithm for MPMD on metrics induced by edge-weighted trees of height h, whose cost is guaranteed to be at most O (1) times the connection cost plus O (h) times the delay cost of every feasible solution. The reduction from MPMD on arbitrary metrics to MPMD on trees is achieved using the result on embedding n -point metric spaces into distributions over weighted hierarchically separated trees of height O (log n ), with distortion O (log n ). We also prove a lower bound of on the competitive ratio of any randomized algorithm. This is the first lower bound which increases with n, and is attained on the metric of n equally spaced points on a line.

SODA Conference 2016 Conference Paper

Make-to-Order Integrated Scheduling and Distribution

• Yossi Azar
• Amir Epstein
• Lukasz Jez
• Adi Vardi

Production and distribution are fundamental operational functions in supply chains. The main challenge is to design algorithms that optimize operational performance by jointly scheduling production and delivery of customer orders. In this paper we study a model of scheduling customer orders on multiple identical machines and their distribution to customers afterwards. The goal is to minimize the total time from release to distribution plus total distribution cost to the customers. We design the first poly-logarithmic competitive algorithm for the problem, improving upon previous algorithms with linear competitive ratios. Our model generalizes two fundamental problems: scheduling of jobs on multiple identical machines (where the goal function is to minimize the total flow time) as well as the TCP Acknowledgment problem.

FOCS Conference 2016 Conference Paper

Online Algorithms for Covering and Packing Problems with Convex Objectives

• Yossi Azar
• Niv Buchbinder
• T. -H. Hubert Chan
• Shahar Chen
• Ilan Reuven Cohen
• Anupam Gupta 0001
• Zhiyi Huang 0002
• Ning Kang 0001

We present online algorithms for covering and packing problems with (non-linear) convex objectives. The convex covering problem is defined as: min xϵ R + n f(x) s. t. Ax ≥ 1, where f: R + n → R + is a monotone convex function, and A is an m×n matrix with non-negative entries. In the online version, a new row of the constraint matrix, representing a new covering constraint, is revealed in each step and the algorithm is required to maintain a feasible and monotonically non-decreasing assignment x over time. We also consider a convex packing problem defined as: max yϵR+ m Σ j=1 m yj - g(A T y), where g: R + n →R + is a monotone convex function. In the online version, each variable yj arrives online and the algorithm must decide the value of yj on its arrival. This represents the Fenchel dual of the convex covering program, when g is the convex conjugate of f. We use a primal-dual approach to give online algorithms for these generic problems, and use them to simplify, unify, and improve upon previous results for several applications.

SODA Conference 2016 Conference Paper

Packing Small Vectors

• Yossi Azar
• Ilan Reuven Cohen
• Amos Fiat
• Alan Roytman

Online d -dimensional vector packing models many settings such as minimizing resources in data centers where jobs have multiple resource requirements (CPU, Memory, etc.). However, no online d -dimensional vector packing algorithm can achieve a competitive ratio better than d. Fortunately, in many natural applications, vectors are relatively small, and thus the lower bound does not hold. For sufficiently small vectors, an O (log d )-competitive algorithm was known. We improve this to a constant competitive ratio, arbitrarily close to e ≈ 2. 718, given that vectors are sufficiently small. We give improved results for the two dimensional case. For arbitrarily small vectors, the First Fit algorithm for two dimensional vector packing is no better than 2-competitive. We present a natural family of First Fit variants, and for optimized parameters get a competitive ratio ≈ 1. 48 for sufficiently small vectors. We improve upon the 1. 48 competitive ratio – not via a First Fit variant – and give a competitive ratio arbitrarily close to 4/3 for packing small, two dimensional vectors. We show that no algorithm can achieve better than a 4/3 competitive ratio for two dimensional vectors, even if one allows the algorithm to split vectors among arbitrarily many bins.

SODA Conference 2013 Conference Paper

Online Mixed Packing and Covering

• Yossi Azar
• Umang Bhaskar
• Lisa Fleischer
• Debmalya Panigrahi

STOC Conference 2013 Conference Paper

The loss of serving in the dark

• Yossi Azar
• Ilan Reuven Cohen
• Iftah Gamzu

STOC Conference 2013 Conference Paper

Tight bounds for online vector bin packing

• Yossi Azar
• Ilan Reuven Cohen
• Seny Kamara
• F. Bruce Shepherd

AAMAS Conference 2012 Conference Paper

Mastering multi-player games

• Yossi Azar
• Uriel Feige
• Michal Feldman
• Moshe Tennenholtz

We consider multi-player games, and the guarantees that a master player that plays on behalf of a set of players can offer them, without making any assumptions on the rationality of the other players. Our model consists of an $(n+1)$-player game, with $m$ strategies per player, in which a \emph{master} player $M$ forms a coalition with nontransferable utilities among $n$ players, and the remaining player is called the {\em independent} player. Existentially, it is shown that every game admits a \emph{product-minimax-safe} strategy for $M$ -- a strategy that guarantees for every player in $M$'s coalition an expected value of at least her \emph{product minimax value} (which is at least as high as her minimax value and is often higher). Algorithmically, for any given vector of values for the players, one can decide in polytime whether it can be ensured by $M$, and if so, compute a mixed strategy that guarantees it. In symmetric games, a product minimax strategy for $M$ can be computed efficiently, even without being given the safety vector. We also consider the performance guarantees that $M$ can offer his players in repeated settings. Our main result here is the extension of the oblivious setting of Feldman, Kalai and Tennenholtz, showing that in every symmetric game, a master player who never observes a single payoff can guarantee for each of its players a {\em similar} performance to that of the independent player, even if the latter gets to choose the payoff matrix after the fact.

TCS Journal 2011 Journal Article

Maximum bipartite flow in networks with adaptive channel width

• Yossi Azar
• Aleksander Mądry
• Thomas Moscibroda
• Debmalya Panigrahi
• Aravind Srinivasan

Traditionally, network optimization problems assume that each link in the network has a fixed capacity. Recent research in wireless networking has shown that it is possible to design networks where the capacity of the links can be changed adaptively to suit the needs of specific applications. In particular, one gets a choice of having a few high capacity outgoing links or many low capacity ones at any node of the network. This motivates us to have a re-look at classical network optimization problems and design algorithms to solve them in this new framework. In particular, we consider the problem of maximum bipartite flow, which has been studied extensively in the fixed-capacity network model. One of the motivations for studying this problem arises from the need to maximize the throughput of an infrastructure wireless network comprising base-stations (one set of vertices in the bipartition) and clients (the other set of vertices in the bipartition). We show that this problem has a significantly different combinatorial structure in this new network model from the fixed-capacity one. While there are several polynomial time algorithms for the maximum bipartite flow problem in traditional networks, we show that the problem is NP-hard in the new model. In fact, our proof extends to showing that the problem is APX-hard. We complement our lower bound by giving two algorithms for solving the problem approximately. The first algorithm is deterministic and achieves an approximation factor of O ( log N ), where N is the number of nodes in the network, while the second algorithm is randomized and achieves an approximation factor of e e − 1.

SODA Conference 2011 Conference Paper

Ranking with Submodular Valuations

• Yossi Azar
• Iftah Gamzu

SODA Conference 2010 Conference Paper

Monotonicity in Bargaining Networks

• Yossi Azar
• Nikhil R. Devanur
• Kamal Jain
• Yuval Rabani

FOCS Conference 2009 Conference Paper

Convergence of Local Dynamics to Balanced Outcomes in Exchange Networks

• Yossi Azar
• Benjamin E. Birnbaum
• L. Elisa Celis
• Nikhil R. Devanur
• Yuval Peres

Bargaining games on exchange networks have been studied by both economists and sociologists. A Balanced Outcome for such a game is an equilibrium concept that combines notions of stability and fairness. In a recent paper, Kleinberg and Tardos introduced balanced outcomes to the computer science community and provided a polynomial-time algorithm to compute the set of such outcomes. Their work left open a pertinent question: are there natural, local dynamics that converge quickly to a balanced outcome? In this paper, we provide a partial answer to this question by showing that simple edge-balancing dynamics converge to a balanced outcome whenever one exists.

STOC Conference 2009 Conference Paper

Multiple intents re-ranking

• Yossi Azar
• Iftah Gamzu
• Xiaoxin Yin

One of the most fundamental problems in web search is how to re-rank result web pages based on user logs. Most traditional models for re-ranking assume each query has a single intent. That is, they assume all users formulating the same query have similar preferences over the result web pages. It is clear that this is not true for a large portion of queries as different users may have different preferences over the result web pages. Accordingly, a more accurate model should assume that queries have multiple intents. In this paper, we introduce the multiple intents re-ranking problem. This problem captures scenarios in which some user makes a query, and there is no information about its real search intent. In such cases, one would like to re-rank the search results in a way that minimizes the efforts of all users in finding their relevant web pages. More formally, the setting of this problem consists of various types of users, each of which interested in some subset of the search results. Moreover, each user type has a non-negative profile vector. Consider some ordering of the search results. This order sets a position for each search result, and induces a position vector of the results relevant to each user type. The overhead of a user type is the dot product of its profile vector and its induced position vector. The goal is to order the search results as to minimize the average overhead of the users. Our main result is an O(log r)-approximation algorithm for the problem, where r is the maximum number of search results that are relevant to any user type. The algorithm is based on a new technique, which we call harmonic interpolation. In addition, we consider two important special cases. The first case is when the profile vector of each user type is non-increasing. This case is a generalization of the well-known min-sum set cover problem. We extend the techniques of Feige, Lovasz and Tetali (Algorithmica '04), and present an algorithm achieving 4-approximation. The second case is when the profile vector of each user type is non-decreasing. This case generalizes the minimum latency set cover problem, introduced by Hassin and Levin (ESA '05). We devise an LP-based algorithm that attains 2-approximation for it.

SODA Conference 2008 Conference Paper

(Almost) optimal coordination mechanisms for unrelated machine scheduling

• Yossi Azar
• Kamal Jain
• Vahab Mirrokni

SODA Conference 2008 Conference Paper

Fast load balancing via bounded best response

• Baruch Awerbuch
• Yossi Azar
• Rohit Khandekar

TCS Journal 2006 Journal Article

An improved algorithm for online coloring of intervals with bandwidth

• Yossi Azar
• Amos Fiat
• Meital Levy
• N.S. Narayanaswamy

We present an improved online algorithm for coloring interval graphs with bandwidth. This problem has recently been studied by Adamy and Erlebach and a 195-competitive online strategy has been presented. We improve this by presenting a 10-competitive strategy. To achieve this result, we use variants of an optimal online coloring algorithm due to Kierstead and Trotter.

TCS Journal 2006 Journal Article

Load balancing of temporary tasks in the ℓ p norm

• Yossi Azar
• Amir Epstein
• Leah Epstein

We consider the on-line load balancing problem where there are m identical machines (servers). Jobs arrive at arbitrary times, where each job has a weight and a duration. A job has to be assigned upon its arrival to exactly one of the machines. The duration of each job becomes known only upon its termination (this is called temporary tasks of unknown durations). Once a job has been assigned to a machine it cannot be reassigned to another machine. The goal is to minimize the maximum over time of the sum (over all machines) of the squares of the loads, instead of the traditional maximum load. Minimizing the sum of the squares is equivalent to minimizing the load vector with respect to the ℓ 2 norm. We show that for the ℓ 2 norm the greedy algorithm performs within at most 1. 493 of the optimum. We show (an asymptotic) lower bound of 1. 33 on the competitive ratio of the greedy algorithm. We also show a lower bound of 1. 20 on the competitive ratio of any algorithm. We extend our techniques and analyze the competitive ratio of the greedy algorithm with respect to the ℓ p norm. We show that the greedy algorithm performs within at most 2 - Ω ( 1 / p ) of the optimum. We also show a lower bound of 2 - O ( ln p / p ) on the competitive ratio of any on-line algorithm.

TCS Journal 2006 Journal Article

Tradeoffs in worst-case equilibria

• Baruch Awerbuch
• Yossi Azar
• Yossi Richter
• Dekel Tsur

We investigate the problem of routing traffic through a congested network in an environment of non-cooperative users. We use the worst-case coordination ratio suggested by Koutsoupias and Papadimitriou to measure the performance degradation due to the lack of a centralized traffic regulating authority. We provide a full characterization of the worst-case coordination ratio in the restricted assignment and unrelated parallel links model. In particular, we quantify the tradeoff between the “negligibility” of the traffic controlled by each user and the worst-case coordination ratio. We analyze both pure and mixed strategies systems and identify the range where their performance is similar.

STOC Conference 2005 Conference Paper

Convex programming for scheduling unrelated parallel machines

• Yossi Azar
• Amir Epstein

We consider the classical problem of scheduling parallel unrelated machines. Each job is to be processed by exactly one machine. Processing job j on machine i requires time p ij . The goal is to find a schedule that minimizes the l p norm. Previous work showed a 2-approximation algorithm for the problem with respect to the l ∞ norm. For any fixed l p norm the previously known approximation algorithm has a performance of θ(p). We provide a 2-approximation algorithm for any fixed l p norm (p>1). This algorithm uses convex programming relaxation. We also give a √ 2-approximation algorithm for the l 2 norm. This algorithm relies on convex quadratic programming relaxation. To the best of our knowledge, this is the first time that general convex programming techniques (apart from SDPs and CQPs) are used in the area of scheduling. We show for any given l p norm a PTAS for any fixed number of machines. We also consider the multidimensional generalization of the problem in which the jobs are d-dimensional. Here the goal is to minimize the l p norm of the generalized load vector, which is a matrix where the rows represent the machines and the columns represent the jobs dimension. For this problem we give a (d+1)-approximation algorithm for any fixed l p norm (p>1).

STOC Conference 2005 Conference Paper

The Price of Routing Unsplittable Flow

• Baruch Awerbuch
• Yossi Azar
• Amir Epstein

The essence of the routing problem in real networks is that the traffic demand from a source to destination must be satisfied by choosing a single path between source and destination. The splittable version of this problem is when demand can be satisfied by many paths, namely a flow from source to destination. The unsplittable, or discrete version of the problem is more realistic yet is more complex from the algorithmic point of view; in some settings optimizing such unsplittable traffic flow is computationally intractable.In this paper, we assume this more realistic unsplittable model, and investigate the "price of anarchy", or deterioration of network performance measured in total traffic latency under the selfish user behavior. We show that for linear edge latency functions the price of anarchy is exactly $2.618 for weighted demand and exactly $2.5 for unweighted demand. These results are easily extended to (weighted or unweighted) atomic "congestion games", where paths are replaced by general subsets. We also show that for polynomials of degree d edge latency functions the price of anarchy is d δ (d). Our results hold also for mixed strategies.Previous results of Roughgarden and Tardos showed that for linear edge latency functions the price of anarchy is exactly 4/3 under the assumption that each user controls only a negligible fraction of the overall traffic (this result also holds for the splittable case). Note that under the assumption of negligible traffic pure and mixed strategies are equivalent and also splittable and unsplittable models are equivalent.

SODA Conference 2004 Conference Paper

A general approach to online network optimization problems

• Noga Alon
• Baruch Awerbuch
• Yossi Azar
• Niv Buchbinder
• Joseph Naor

TCS Journal 2004 Journal Article

On-line generalized Steiner problem

• Baruch Awerbuch
• Yossi Azar
• Yair Bartal

The generalized Steiner problem (GSP) is defined as follows. We are given a graph with non-negative edge weights and a set of pairs of vertices. The algorithm has to construct minimum weight subgraph such that the two nodes of each pair are connected by a path. Off-line GSP approximation algorithms were given in Agarwal et al. (SIAM J. Comput. 24(3) (1995) 440) and Goemans and Williamson (SIAM J. Comput. 24(2) (1995) 296). We consider the on-line GSP, in which pairs of vertices arrive on-line and are needed to be connected immediately. We show that the online Min-Cost (i. e. greedy) strategy for this problem has O(log 2 n) competitive ratio. The previous best algorithm was O( n log n) competitive (Workshop on Algorithms and Data Structures, 1993, pp. 622–633). Following this work a different (non-greedy) algorithm has been shown to achieve an O(log n) competitive ratio (Proceedings of the 29th ACM Symposium on Theory of Computing, 1997, pp. 344–353). We also consider the network connectivity leasing problem which is a generalization of the GSP. Here, edges of the graph can be either bought or leased for different costs. We provide simple randomized algorithm based on on-line generalized Steiner algorithms whose competitive ratio is within a constant factor of the best competitive algorithm for the on-line GSP.

STOC Conference 2004 Conference Paper

The zero-one principle for switching networks

• Yossi Azar
• Yossi Richter

Recently, approximation analysis has been extensively used to study algorithms for routing weighted packets in various network settings. Although different techniques were applied in the analysis of diverse models, one common property was evident: the analysis of input sequences composed solely of two different values is always substantially easier, and many results are known only for restricted value sequences. Motivated by this, we introduce our zero-one principle for switching networks which characterizes a wide range of algorithms for which achieving c-approximation (as well as c-competitiveness) with respect to sequences composed of 0's and 1's implies achieving c-approximation. The zero-one principle proves to be very efficient in the design of switching algorithms, and substantially facilitates their analysis. We present three applications. First, we consider the Multi-Queue QoS Switching model and design a 3-competitive algorithm, improving the result from [6]. Second, we study the Weighted Dynamic Routing problem on a line topology of length k and present a (k+1)-competitive algorithm, which improves and generalizes the results from [1,12]. As a third application, we consider the work of [11], that compares the performance of local algorithms to the global optimum in various network topologies, and generalize their results from 2-value sequences to arbitrary value sequences.

STOC Conference 2003 Conference Paper

Management of multi-queue switches in QoS networks

• Yossi Azar
• Yossi Richter

The concept of Quality of Service (QoS) networks has gained growing attention recently, as the traffic volume in the Internet constantly increases, and QoS guarantees are essential to ensure proper operation of most communication based applications. A QoS switch serves m incoming queues by transmitting packets arriving at these queues through one output port, one packet per time unit. Each packet is marked with a value indicating its guaranteed quality of service. Since the queues have bounded capacity and the rate of arriving packets can be much higher than the transmission rate, packets can be lost due to insufficient queue space. The goal is to maximize the total value of transmitted packets. This problem encapsulates two dependent questions: admission control, namely which packets to discard in case of queue overflow, and scheduling, i.e. which queue to use for transmission in each time unit. We use competitive analysis to study online switch performance in QoS based networks. Specifically, we provide a novel generic technique that decouples the admission control and scheduling problems. Our technique transforms any single queue admission control strategy (preemptive or nonpreemptive) to a scheduling and admission control algorithm for our general m queues model, whose competitive ratio is at most twice the competitive ratio of the given admission control strategy. We use our technique to derive concrete algorithms for the general preemptive and nonpreemptive cases, as well as for the interesting special cases of the 2-value model and the unit value model. To the best of our knowledge this is the first result combining both scheduling and admission control decisions for arbitrary packets sequences in multi-queue switches. We also provide a 1.58 -competitive randomized algorithm for the unit value case. This case is interesting by itself since most current networks (e.g. IP networks) only support a best-effort service in which all packets streams are treated equally.

STOC Conference 2003 Conference Paper

Optimal oblivious routing in polynomial time

• Yossi Azar
• Edith Cohen
• Amos Fiat
• Haim Kaplan
• Harald Räcke

A recent seminal result of Racke is that for any network there is an oblivious routing algorithm with a polylog competitive ratio with respect to congestion. Unfortunately, Racke's construction is not polynomial time. We give a polynomial time construction that guarantee's Racke's bounds, and more generally gives the true optimal ratio for any network.

STOC Conference 2003 Conference Paper

Reducing truth-telling online mechanisms to online optimization

• Baruch Awerbuch
• Yossi Azar
• Adam Meyerson

We describe a general technique for converting an online algorithm Β to a truthtelling mechanism. We require that the original online competitive algorithm has certain "niceness" properties in that actions on future requests are independent of the actual value of requests which were accepted (though these actions will of course depend upon the set of accepted requests). Under these conditions, we are able to give an online truthtelling mechanism (where the values of requests are given by bids which may not accurately represent the valuation of the requesters) such that our total profit is within O(ρ + log μ) of the optimum offline profit obtained by an omniscient algorithm (one which knows the true valuations of the users). Here ρ is the competitive ratio of Β for the optimization version of the problem, and μ is the ratio of the maximum to minimum valuation for a request. In general there is an Ω(log μ) lower bound on the ratio of worst-case profit for a truthtelling mechanism when compared to the profit obtained by an omniscient algorithm, so this result is in some sense best possible. In addition, we prove that our construction is resilient against many forms of "cheating" attempts, such as forming coalitions.We demonstrate applications of this result to several problems. We develop online truthtelling mechanisms for online routing and admission control of path or multicast requests, assuming large network capacities. Assuming the existance of an algorithm Β for the optimization version of the problem, our techniques provide truthtelling mechanisms for general combinatorial auctions. However, designing optimization algorithms may be difficult in general because of online or approximation lower bounds. For the cases described above, we are able to design optimization algorithms Β by amortizing the lost benefit from online computation (and from approximation hardness in the case of multicast) against the benefit obtained from accepted requests.We comment that our upper bounds on profit competitiveness imply, as an obvious corollary, similar bound on global efficiency , namely overall well-being of all the users. This contrasts with most other work on truthtelling mechanisms for general online resource allocation, where only efficiency is maximized, and competitiveness can be arbitrarily poor.

STOC Conference 2003 Conference Paper

The online set cover problem

• Noga Alon
• Baruch Awerbuch
• Yossi Azar
• Niv Buchbinder
• Joseph Naor

TCS Journal 2002 Journal Article

Off-line temporary tasks assignment

• Yossi Azar
• Oded Regev
• Jiřı́ Sgall
• Gerhard J. Woeginger

In this paper we consider the temporary tasks assignment problem. In this problem, there are m parallel machines and n independent jobs. Each job has an arrival time, a departure time and some weight. Each job should be assigned to one machine. The load on a machine at a certain time is the sum of the weights of jobs assigned to it at that time. The objective is to find an assignment that minimizes the maximum load over machines and time. We present a polynomial time approximation scheme for the case in which the number of machines is fixed. We also show that for the case in which the number of machines is given as part of the input (i. e. , not fixed), no polynomial algorithm can achieve a better approximation ratio than 3 2 unless P=NP.

SODA Conference 2002 Conference Paper

Temporary tasks assignment resolved

• Amitai Armon
• Yossi Azar
• Leah Epstein
• Oded Regev 0001

TCS Journal 2001 Journal Article

On-line bin-stretching

• Yossi Azar
• Oded Regev

We are given a sequence of items that can be packed into m unit size bins. In the classical bin packing problem we fix the size of the bins and try to pack the items in the minimum number of such bins. In contrast, in the bin-stretching problem we fix the number of bins and try to pack the items while stretching the size of the bins as least as possible. We present two on-line algorithms for the bin-stretching problem that guarantee a stretching factor of 5/3 for any number m of bins. We then combine the two algorithms and design an algorithm whose stretching factor is 1. 625 for any m. The analysis for the performance of this algorithm is tight. The best lower bound for any algorithm is 4/3 for any m⩾2. We note that the bin-stretching problem is also equivalent to the classical scheduling (load balancing) problem in which the value of the makespan (maximum load) is known in advance.

STOC Conference 2001 Conference Paper

Spectral analysis of data

• Yossi Azar
• Amos Fiat
• Anna R. Karlin
• Frank McSherry
• Jared Saia

Experimental evidence suggests that spectral techniques are valuable for a wide range of applications. A partial list of such applications include (i) semantic analysis of documents used to cluster documents into areas of interest, (ii) collaborative filtering --- the reconstruction of missing data items, and (iii) determining the relative importance of documents based on citation/link structure. Intuitive arguments can explain some of the phenomena that has been observed but little theoretical study has been done. In this paper we present a model for framing data mining tasks and a unified approach to solving the resulting data mining problems using spectral analysis. These results give strong justification to the use of spectral techniques for latent semantic indexing, collaborative filtering, and web site ranking.

SODA Conference 1999 Conference Paper

Beating the Logarithmic Lower Bound: Randomized Preemptive Disjoint Paths and Call Control Algorithms

• Ran Adler
• Yossi Azar

STOC Conference 1999 Conference Paper

Minimizing the Flow Time Without Migration

• Baruch Awerbuch
• Yossi Azar
• Stefano Leonardi 0001
• Oded Regev 0001

SODA Conference 1998 Conference Paper

Ancient and New Algorithms for Load Balancing in the L p Norm

• Adi Avidor
• Yossi Azar
• Jirí Sgall

SODA Conference 1997 Conference Paper

Approximation Schemes for Scheduling

• Noga Alon
• Yossi Azar
• Gerhard J. Woeginger
• Tal Yadid

FOCS Conference 1997 Conference Paper

Buy-at-Bulk Network Design

• Baruch Awerbuch
• Yossi Azar

The essence of the simplest buy-at-bulk network design problem is buying network capacity "wholesale" to guarantee connectivity from all network nodes to a certain central network switch. Capacity is sold with "volume discount": the more capacity is bought, the cheaper is the price per unit of bandwidth. We provide O(log/sup 2/n) randomized approximation algorithm for the problem. This solves the open problem in Salman et al. (1997). The only previously known solutions were restricted to special cases (Euclidean graphs). We solve additional natural variations of the problem, such as multi-sink network design, as well as selective network design. These problems can be viewed as generalizations of the the Generalized Steiner Connectivity and Prize-collecting salesman (K-MST) problems. In the selective network design problem, some subset of /spl kappa/ wells must be connected to the (single) refinery, so that the total cost is minimized.

STOC Conference 1996 Conference Paper

Making Commitments in the Face of Uncertainty: How to Pick a Winner Almost Every Time (Extended Abstract)

• Baruch Awerbuch
• Yossi Azar
• Amos Fiat
• Frank Thomson Leighton

SODA Conference 1996 Conference Paper

On-line Generalized Steiner Problem

• Baruch Awerbuch
• Yossi Azar
• Yair Bartal

STOC Conference 1995 Conference Paper

Improved approximation guarantees for minimum-weight k -trees and prize-collecting salesmen

• Baruch Awerbuch
• Yossi Azar
• Avrim Blum
• Santosh S. Vempala

FOCS Conference 1995 Conference Paper

Load Balancing in the L p Norm

• Baruch Awerbuch
• Yossi Azar
• Edward F. Grove
• Ming-Yang Kao
• P. Krishnan
• Jeffrey Scott Vitter

In the load balancing problem, there is a set of servers, and jobs arrive sequentially. Each job can be run on some subset of the servers, and must be assigned to one of them in an online fashion. Traditionally, the assignment of jobs to servers is measured by the L/sub /spl infin// norm; in other words, an assignment of jobs to servers is quantified by the maximum load assigned to any server. In this measure the performance of the greedy load balancing algorithm may be a logarithmic factor higher than the offline optimal. In many applications, the L/sub /spl infin// norm is not a suitable way to measure how well the jobs are balanced, If each job sees a delay that is proportional to the number of jobs on its server, then the average delay among all jobs is proportional to the sum of the squares of the numbers of jobs assigned to the servers. Minimizing the average delay is equivalent to minimizing the Euclidean (or L/sub 2/) norm. For any fixed p, 1/spl les/p</spl infin/, we show that the greedy algorithm performs within a constant factor of the offline optimal with respect to the L/sub p/ norm. The constant grows linearly with p, which is best possible, but does not depend on the number of servers and jobs.

STOC Conference 1994 Conference Paper

Balanced allocations (extended abstract)

• Yossi Azar
• Andrei Z. Broder
• Anna R. Karlin
• Eli Upfal

SODA Conference 1994 Conference Paper

Competitive Routing of Virtual Circuits with Unknown Duration

• Baruch Awerbuch
• Yossi Azar
• Serge A. Plotkin
• Orli Waarts

FOCS Conference 1994 Conference Paper

Local Optimization of Global Objectives: Competitive Distributed Deadlock Resolution and Resource Allocation

• Baruch Awerbuch
• Yossi Azar

The work is motivated by deadlock resolution and resource allocation problems, occurring in distributed server-client architectures. We consider a very general setting which includes, as special cases, distributed bandwidth management in communication networks, as well as variations of classical problems in distributed computing and communication networking such as deadlock: resolution and "dining philosophers". In the current paper, we exhibit first local solutions with globally-optimum performance guarantees. An application of our method is distributed bandwidth management in communication networks. In this setting, deadlock resolution (and maximum fractional independent set) corresponds to admission control maximizing network throughput. Job scheduling (and minimum fractional coloring) corresponds to route selection that minimizes load. >

TCS Journal 1994 Journal Article

On-line load balancing

• Yossi Azar
• Andrei Z. Broder
• Anna R. Karlin

The setup for our problem consists of n servers that must complete a set of tasks. Each task can be handled only by a subset of the servers, requires a different level of service, and once assigned cannot be reassigned. We make the natural assumption that the level of service is known at arrival time, but that the duration of service is not. The on-line load balancing problem is to assign each task to an appropriate server in such a way that the maximum load on the servers is minimized. In this paper we derive matching upper and lower bounds for the competitive ratio of the on-line greedy algorithm for this problem, namely, [(3n) 2 3 /2](1+o(1)), and derive a lower bound, Ω(n 1 2 ), for any other deterministic or randomized on-line algorithm.

SODA Conference 1993 Conference Paper

On-line Choice of On-line Algorithms

• Yossi Azar
• Andrei Z. Broder
• Mark S. Manasse

STOC Conference 1993 Conference Paper

On-line load balancing with applications to machine scheduling and virtual circuit routing

• James Aspnes
• Yossi Azar
• Amos Fiat
• Serge A. Plotkin
• Orli Waarts

FOCS Conference 1993 Conference Paper

Throughput-Competitive On-Line Routing

• Baruch Awerbuch
• Yossi Azar
• Serge A. Plotkin

We develop a framework that allows us to address the issues of admission control and routing in high-speed networks under the restriction that once a call is admitted and routed, it has to proceed to completion and no reroutings are allowed. The "no rerouting" restriction appears in all the proposals for future high-speed networks and stems from current hardware limitations, in particular the fact that the bandwidth-delay product of the newly developed optical communication links far exceeds the buffer capacity of the network. In case the goal is to maximize the throughput, our framework yields an on-line O(log nT)-competitive strategy, where n is the number of nodes in the network and T is the maximum call duration. In other words, our strategy results in throughput that is within O(log nT) factor of the highest possible throughput achievable by an omniscient algorithm that knows all of the requests in advance. Moreover, we show that no on-line strategy can achieve a better competitive ratio. Our framework leads to competitive strategies applicable in several more general settings. Extensions include assigning each connection an associated "profit" that represents the importance of this connection, and addressing the issue of call-establishment costs. >

STOC Conference 1992 Conference Paper

Biased Random Walks

• Yossi Azar
• Andrei Z. Broder
• Anna R. Karlin
• Nati Linial
• Steven J. Phillips

How much can an imperfect source of randomness affect an algorithm? We examine several simple questions of this type concerning the long-term behavior of a random walk on a finite graph. In our setup, each step of the random walk a “controller” can, with a certain small probability, fix the next step, thus introducing a bias. We analyze the extent to which the bias can affect the limit behavior of the walk. The controller is assumed to associate a real, nonnegative, “benefit” with each state, and to strive to maximize the long-term expected benefit. We derive tight bounds on the maximum of this objective function over all controller's strategies, and present polynomial time algorithms for computing the optimal controller strategy.

SODA Conference 1992 Conference Paper

Comparison-Sorting and Selecting in Totally Monotone Matrices

• Noga Alon
• Yossi Azar

FOCS Conference 1992 Conference Paper

On-line Load Balancing (Extended Abstract)

• Yossi Azar
• Andrei Z. Broder
• Anna R. Karlin

The setup for the authors' problem consists of n servers that must complete a set of tasks. Each task can be handled only by a subset of the servers, requires a different level of service, and once assigned can not be re-assigned. They make the natural assumption that the level of service is known at arrival time, but that the duration of service is not. The on-line load balancing problem is to assign each task to an appropriate server in such a way that the maximum load on the servers is minimized. The authors derive matching upper and lower bounds for the competitive ratio of the on-line greedy algorithm for this problem, namely /sup (3n)2/3///sub 2/(1+o(1)), and derive a lower bound, Omega ( square root n), for any other deterministic or randomized on-line algorithm. >

SODA Conference 1992 Conference Paper

The Competitiveness of On-Line Assignments

• Yossi Azar
• Joseph Naor
• Raphael Rom

FOCS Conference 1988 Conference Paper

Parallel Comparison Algorithms for Approximation Problems

• Noga Alon
• Yossi Azar

The authors consider that they have n elements from a totally ordered domain and are allowed to perform p parallel comparisons in each time unit (round). They determine, up to a constant factor, the time complexity of several approximation problems in the common parallel comparison tree model of L. G. Valiant, for all admissible values of n, p, and epsilon, where epsilon is an accuracy parameter determining the quality of the required approximation. The problems considered include the approximate maximum problem, approximate sorting, and approximate merging. The results imply, as special cases, all the known results about the time complexity of parallel sorting, parallel merging, and parallel selection of the maximum (in the comparison model). They highlight one very special but representative result concerning the approximate maximum problem. They wish to find, among the given n elements, one which belongs to the biggest n/2, where in each round they are allowed to ask n binary comparisons. They show that log/sup */n+ Theta (1) rounds are both necessary and sufficient in the best algorithm for this problem. >

FOCS Conference 1987 Conference Paper

The Average Complexity of Deterministic and Randomized Parallel Comparison Sorting Algorithms

• Noga Alon
• Yossi Azar

In practice, the average time of (deterministic or randomized) sorting algorithms seems to be more relevant than the worst case time of deterministic algorithms. Still, the many known complexity bounds for parallel comparison sorting include no nontrivial lower bounds for the average time required to sort by comparisons n elements with p processors (via deterministic or randomized algorithms). We show that for p ≥ n this time is Θ (log n/log(1 + p/n)), (it is easy to show that for p ≤ n the time is Θ (n log n/p) = Θ (log n/(p/n)). Therefore even the average case behaviour of randomized algorithms is not more efficient than the worst case behaviour of deterministic ones.

FOCS Conference 1986 Conference Paper

Tight Complexity Bounds for Parallel Comparison Sorting

• Noga Alon
• Yossi Azar
• Uzi Vishkin

The time complexity of sorting n elements using p ≥ n processors on Valiant's parallel comparison tree model is considered. The following results are obtained. 1. We show that this time complexity is Θ(logn/log(1+p/n)). This complements the AKS sorting network in settling the wider problem of comparison sort of n elements by p processors, where the problem for p ≤ n was resolved. To prove the lower bound, we show that to achieve time k ≤ logn, we need Ω(kn1+1/k) comparisons. Häggkvist and Hell proved a similar result only for fixed k. 2. For every fixed time k, we show that: (a) Ω(n1+1/k lognl/k) comparisons are required, (O(n1+1/k logn) are known to be sufficient in this case), and (b) there exists a randomized algorithm for comparison sort in time k with an expected number of O(n1+1/k) comparisons. This implies that for every fixed k, any deterministic comparison sort algorithm must be asymptotically worse than this randomized algorithm. The lower bound improves on Häggkvist-Hell's lower bound. 3. We show that "approximate sorting" in time 1 requires asymptotically more than nlogn processors. This settles a problem raised by M. Rabin.