On Revenue Maximization in Second-Price Ad Auctions (2009)
Azar, Yossi, Birnbaum, Benjamin, Karlin, Anna R., Nguyen, C. Thach
Most recent papers addressing the algorithmic problem of allocating advertisement space for keywords in sponsored search auctions assume that pricing is done via a first-price auction, which does not...
Convergence of Local Dynamics to Balanced Outcomes in Exchange Networks (2009)
Azar, Yossi, Birnbaum, Benjamin, Celis, L. Elisa, Devanur, Nikhil R., Peres, Yuval
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...
General General Terms Algorithms (2008)
Yossi Azar, Edith Cohen, Amos Fiat, Haim Kaplan, Harald Räcke
A recent seminal result of Räcke is that for any network there is an oblivious routing algorithm with a polylog competitive ratio with respect to congestion. Unfortunately, Räcke’s construction...
Thinking Twice about Second-Price Ad Auctions (2008)
Azar, Yossi, Birnbaum, Benjamin, Karlin, Anna R., Nguyen, C. Thach
Recent work has addressed the algorithmic problem of allocating advertisement space for keywords in sponsored search auctions so as to maximize revenue, most of which assume that pricing is done via...
Improved Approximation Algorithms for Budgeted Allocations (2008)
Yossi Azar, Benjamin Birnbaum, Anna R. Karlin, Claire Mathieu, C. Thach Nguyen
Abstract. We provide a 3/2-approximation algorithm for an offline budgeted allocations problem, an improvement over the e/(e − 1) approximation of Andelman and Mansour [1] and the e/(e − 1) −...
Truthful Unsplittable Flow for Large Capacity Networks (2008)
Azar, Yossi, Gamzu, Iftah, Gutner, Shai
In this paper, we focus our attention on the large capacities unsplittable flow problem in a game theoretic setting. In this setting, there are selfish agents, which control some of the requests...
On-Line Restricted Assignment of Temporary Tasks with Unknown Durations (2008)
Amitai Armon, Yossi Azar, Leah Epstein, Oded Regev
We consider load balancing of temporary tasks on m machines in the restricted assignment model. It is known that the best competitive ratio for this problem is Θ ( √ m). This bound is not achieved...
Combining online algorithms for acceptance and rejection (2008)
Yossi Azar, Avrim Blum, David P. Bunde, Yishay Mansour, C Yossi Azar, Avrim Blum, ...
Abstract: Resource allocation and admission control are critical tasks in a communication network that often must be performed online. Algorithms for these types of problems have been considered both...
Leiden University. Online scheduling and bin packing (2008)
Rob Van Stee, Prof. Dr. J. N. Kok, Rob Van Stee, My Coauthors, Han La Poutré, Leah Epstein, ...
and bin packing
The Online Set Cover Problem (Extended Abstract) (2008)
Noga Alon, Baruch Awerbuch, Yossi Azar, Niv Buchbinder, Joseph (seffi Naor
Let X = {1, 2,..., n} be a ground set of n elements, and let S be a family of subsets of X, |S | = m, with a positive cost cS associated with each S ∈ S. Consider the following online version of...
General General Terms Algorithms (2008)
Yossi Azar, Edith Cohen, Amos Fiat, Haim Kaplan, Harald Räcke
A recent seminal result of Räcke is that for any network there is an oblivious routing algorithm with a polylog competitive ratio with respect to congestion. Unfortunately, Räcke’s construction...
Categories and Subject Descriptors (2008)
Baruch Awerbuch, Yossi Azar, Zvi Lotker, Boaz Patt-shamir, Mark R. Tuttle, The Israel
We consider a model with n players and m objects. Each player has a “preference vector ” of length m that models his grade for each object. The grades are unknown to the players. A player can...
Truthful Unsplittable Flow for Large Capacity Networks ABSTRACT (2008)
The unsplittable flow problem is one of the most extensively studied optimization problems in the field of networking. An instance of it consists of an edge capacitated graph and a set of connection...
Baruch Awerbuch, Yossi Azar, Serge 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...
Abstract Tell Me Who I Am: An Interactive Recommendation System Extended Abstract (2008)
Noga Alon, Baruch Awerbuch, Yossi Azar, Boaz Patt-shamir, Neumann Fund
We consider a model of recommendation systems, where each member from a given set of players has a binary preference to each element in a given set of objects: intuitively, each player either likes...
Baruch Awerbuch, Yossi Azar, Zvi Lotker, Boaz Patt-shamir, Mark R. Tuttle, Springer Science+business Media, ...
Abstract We consider a model with n players and m objects. Each player has a “preference vector ” of length m, that models his grades for all objects. The grades are initially unknown to the...
Combining online algorithms for acceptance and rejection (2008)
Yossi Azar, Avrim Blum, David P. Bunde, Yishay Mansour, C Yossi Azar, Avrim Blum, ...
Abstract: Resource allocation and admission control are critical tasks in a communication network that often must be performed online. Algorithms for these types of problems have been considered both...
Admission Control to Minimize Rejections and Online Set Cover with Repetitions (2008)
Alon, Noga, Azar, Yossi, Gutner, Shai
We study the admission control problem in general networks. Communication requests arrive over time, and the online algorithm accepts or rejects each request while maintaining the capacity...
Baruch Awerbuch, Yossi Azar, Niv Buchbinder, Joseph (seffi Naor
Abstract Let X = f1; 2; : : : ; ng be a ground set of n elements, and let S be a family of subsets of X, jSj = m, with a positive cost cS associated with each S 2 S.
Abstract We consider the on-line problem of scheduling jobs with precedence constraints on m machines. We concentrate in two models, the model of uniformly related machines and the model of...
Combining online algorithms for acceptance and rejection (2008)
Yossi Azar, Avrim Blum, David P. Bunde, Yishay Mansour, C Yossi Azar, Avrim Blum, ...
Abstract: Resource allocation and admission control are critical tasks in a communication network that often must be performed online. Algorithms for these types of problems have been considered both...
Admission control to minimize rejections and online set cover with repetitions (2008)
Noga Alon, Yossi Azar, Shai Gutner
Abstract We study the admission control problem in general networks. Communication requests arrive overtime, and the online algorithm accepts or rejects each request while maintaining the capacity...
-- John Steinbeck, The Winter of Our Discontent. (2008)
Every action must be due to one or other of seven causes: chance, nature, compulsion, habit, reasoning, anger, or appetite.-- Aristotle, Rhetoric, Bk. II. No one wants advice-- only corroboration.
Load balancing of temporary tasks in the `p norm (2008)
Yossi Azar, Amir Epstein, Leah Epstein
Abstract 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...
Fast load balancing via bounded best response (2008)
Baruch Awerbuch, Yossi Azar, Rohit Kh
It is known that the dynamics of best response in an environment of non-cooperative users may converge to a good solution when users play sequentially, but may cycle far away from the global optimum...
almost) optimal coordination mechanisms for unrelated maching scheduling (2008)
Yossi Azar, Kamal Jain, Vahab Mirrokni
We investigate the influence of different algorithmic choices on the approximation ratio in selfish scheduling. Our goal is to design local policies that minimize the inefficiency of resulting...
Noga Alon, Baruch Awerbuch, Johns Hopkins U, Yossi Azar, Boaz Patt-shamir
We consider a model of recommendation systems, where each member from a given set of players has a binary preference to each element in a given set of objects: intuitively, each player either likes...
A Preemptive Algorithm for Maximizing Disjoint Paths on Trees (2008)
Yossi Azar, Uriel Feige, Daniel Glasner
We consider the online version of the maximum vertex disjoint path problem when the underlying network is a tree. In this problem, a sequence of requests arrives in an online fashion, where every...
Baruch Awerbuch, Yossi Azar, Serge 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...
Yossi Azar, Yair Bartal, Esteban Feuerstein, Stefano Leonardi
We deal with the problem of making capital investments in machines for manufacturing a product. Opportunities for investment occur over time, every such option consists of a capital cost for a new...
Baruch Awerbuch, Yossi Azar, Yair Bartal
The Generalized Steiner Problem (GSP) is defined as follows. We are given a graph with non-negative weights and a set of pairs of vertices. The algorithm has to construct minimum weight subgraph such...
Baruch Awerbuch, Yossi Azar, Stefano Leonardi
In the present work we study the on-line call admission problem in optical networks. We present a general technique to deal with the problem of call admission and wavelength selection by reducing...
Baruch Awerbuch, Yossi Azar, Stefano Leonardi, Oded Regev
We consider the classical problem of scheduling jobs in a multiprocessor setting in order to minimize the flow time (total time in the system). The performance of the algorithm, both in offline and...
James Aspnes, Yossi Azar, Amos Fiat, Serge Plotkin, Orli Waarts
In this paper we study the problem of on-line allocation of routes to virtual circuits (both point-topoint and multicast) where the goal is to minimize the required bandwidth. We concentrate on the...
Competitive Algorithms for On-line Set Cover or How to Beat Murphy's Law (2007)
Baruch Awerbuch, Yossi Azar, Amos Fiat
This paper considers an on-line optimization version of the set cover problem. We present a optimally competitive on-line randomized algorithm which is O(logn log m) competitive where n is the...
Blindly-Competitive Algorithms: Pricing Bidding as a Case Study (2007)
Extend Ed, Baruch Awerbuch, Yossi Azar
) Baruch Awerbuch Yossi Azar y April 26, 1995 Abstract The standard setting for competitive analysis of online algorithms assumes that online algorithm knows the past (but not future) inputs, and can...
Improved Approximation Guarantees for Minimum-Weight (2007)
Trees And, Baruch Awerbuch, Yossi Azar, Avrim Blum, Santosh Vempala
We consider a formalization of the following problem. A salesperson must sell some quota of brushes in order to win a trip to Hawaii. This salesperson has a map (a weighted graph) in which each city...
On-line Algorithms for Generalized Steiner Tree and Network Connectivity Leasing (2007)
Baruch Awerbuch, Yossi Azar, Yair Bartal
The Generalized Steiner Tree (GST) problem is defined as follows. We are given a graph with non-negative weights and a set of pairs of vertices. The algorithm has to construct minimum weight subgraph...
Maximal Dense Trees and Competitive On-line Selective Multicast (Extended Abstract) (2007)
Baruch Awerbuch, Yossi Azar, Rainer Gawlick
) Baruch Awerbuch 1;2 Yossi Azar 3 Rainer Gawlick 2 1 Johns Hopkins University 2 Laboratory for Computer Science, MIT 3 Tel-Aviv University Abstract In this paper we introduce the problem of...
Load balancing of temporary tasks in the # p norm (2007)
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...
Abstract. We consider the problem of assigning a set of jobs to m parallel related machines so as to maximize the minimum load over the machines. This situation corresponds to a case that a system...
Abstract. We consider the problem of scheduling a sequence of jobs to m parallel machines as to maximize the minimum load over the machines. This situation corresponds to a case that a system which...
Maximizing Job Benets On-line (2007)
Baruch Awerbuch, Yossi Azar, Oded Regev
We consider a benet model for on-line preemptive scheduling. In this model jobs arrive at the on-line scheduler at their release time. Each job arrives with its own execution time and benet function....
Baruch Awerbuch, Yossi Azar, Stefano Leonardi, Oded Regev
We consider the classical problem of scheduling jobs in a multiprocessor setting in order to minimize the ow time (total time in the system). The performance of the algorithm, both in oine and online...
Abstract. We provide the rst strongly polynomial algorithms with the best approximation ratio for all three variants of the unsplittable ow problem (UFP). In this problem we are given a (possibly...
Tel-Aviv Univ. We consider the on-line problem of scheduling jobs with precedence constraints on m machines. We concentrate in two models, the model of uniformly related machines and the model of...
Baruch Awerbuch, Yossi Azar, Serge 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...
The Multicast Bandwidth Advantage in Serving (2007)
Web Site Yossi, Yossi Azar, Meir Feder, Eyal Lubetzky, Doron Rajwan
Delivering popular web pages to the clients results in high bandwidth and high load on the web servers. A method to overcome this problem is to send these pages, requested by many users, via...
Dr. Frankenstein's Approach to On-line Algorithms (2007)
Extended Yossi, Yossi Azar, Andrei Z. Broder, Mark S. Manasse
Let be a set of on-line algorithms for a problem P with input set I . We assume that P can be represented as a metrical task system. Each A i has a competitive ratio a i with respect to the optimum...
A General Approach to Online Network Optimization Problems (2007)
Noga Alon, Baruch Awerbuch, Yossi Azar, Niv Buchbinder, Joseph (Seffi) Naor
We study a wide range of online graph and network optimization problems, focusing on problems that arise in the study of connectivity and cuts in graphs. In a general online network design problem,...
Tradeos in worst-case equilibria (2007)
Baruch Awerbuch, Yossi Azar, Yossi Richter, Dekel Tsur
We investigate the problem of routing trac through a congested network in an environment of non-cooperative users. We use the worst-case coordination ratio suggested by Koutsoupias and Papadimitriou...
Yossi Azar, Yair Bartal, Esteban Feuerstein, Stefano Leonardi
We deal with the problem of making capital investments in machines for manufacturing a product. Opportunities for investment occur over time, every such option consists of a capital cost for a new...
Baruch Awerbuch, Yossi Azar, Stefano Leonardi
We study the on-line call admission problem in optical networks. We present a general technique that allows us to reduce the problem of call admission and wavelength selection to the call admission...
Yossi Azar, Oded Regev, Presentation Tomer Greenberg, Boris Kapchits
Earlier results Additional problem variations
Fast convergence to nearly optimal solutions in potential games (2007)
Baruch Awerbuch, Yossi Azar, Amir Epstein, Vahab S. Mirrokni, Alexander Skopalik
We study the speed of convergence of decentralized dynamics to approximately optimal solutions in potential games. We consider α-Nash dynamics in which a player makes a move if the improvement in...
Scheduling, 6(2):131–147, 2003. (2007)
Arne Andersson, Rolf Fagerberg, Yossi Azar, Joan Boyar, Leah Epstein, Lene M. Favrholdt, ...
on Accommodating Sequences for the Seat Reservation Problem. Journal of
Improved Approximation Guarantees for Minimum-Weight k-Trees and Prize- Collecting Salesmen (2006)
Awerbuch, Baruch, Azar, Yossi, Blum, Avrim
Consider a salesperson that must sell some quota of brushes in order to win a trip to Hawaii. This salesperson has a map (a weighted graph) in which each city has an attached demand specifying the...
Tell me who I am: An interactive recommendation system (2006)
Noga Alon, Baruch Awerbuch, Yossi Azar, Boaz Patt-shamir
We consider a model of recommendation systems, where each member from a given set of players has a binary preference to each element in a given set of objects: intuitively, each player either likes...
Noga Alon, Baruch Awerbuch, Johns Hopkins U, Yossi Azar, Boaz Patt-shamir
We consider a model of recommendation systems, where each member from a given set of players has a binary preference to each element in a given set of objects: intuitively, each player either likes...
How Branch Mispredictions Affect Quicksort (2006)
Kaligosi, Kanela, Sanders, Peter, Azar, Yossi, Erlebach, Thomas
We explain the counterintuitive observation that finding “good” pivots (close to the median of the array to be partitioned) may not improve performance of quicksort. Indeed, an intentionally...
I/O-Efficient Undirected Shortest Paths with Unbounded Edge Lengths (2006)
Meyer, Ulrich, Zeh, Norbert, Azar, Yossi, Erlebach, Thomas
We show how to compute single-source shortest paths in undirected graphs with non-negative edge lengths in I/Os, where n is the number of vertices, m is the number of edges, B is the disk block size,...
Enumerating Spanning and Connected Subsets in Graphs and Matroids (2006)
Khachiyan, Leonid, Boros, Endre, Borys, Konrad, Elbassioni, Khaled, Gurvich, Vladimir, Makino, Kazuhisa, ...
We show that enumerating all minimal spanning and connected subsets of a given matroid can be solved in incremental quasi-polynomial time. In the special case of graphical matroids, we improve this...
On the Complexity of the Multiplication Method for Monotone CNF/DNF Dualization (2006)
Elbassioni, Khaled, Azar, Yossi, Erlebach, Thomas
Given the irredundant CNF representation $\phi$ of a monotone Boolean function $f:\{0,1\}^n\mapsto\{0,1\}$, the dualization problem calls for finding the corresponding unique irredundant DNF...
Collaborate With Strangers To Find Own Preferences (2005)
Baruch Awerbuch, Yossi Azar, Zvi Lotker, Boaz Patt-shamir, Mark R. Tuttle
We consider a model with n players and m objects. Each player has a “preference vector ” of length m, that models his grades for all objects. The grades are initially unknown to the players. A...
Convex programming for scheduling unrelated parallel machines (2005)
Abstract We consider the classical problem of scheduling parallel unrelated machines. Each job is tobe processed by exactly one machine. Processing job j on machine i requires time pij. The goalis to...
Packet Routing and Information Gathering in Lines, Rings and Trees (2005)
Abstract We study the problem of online packet routing and information gathering in lines, rings andtrees. A network consists of n nodes. At each node there is a buffer of size B. Each buffer...
Collaborate With Strangers To Find Own Preferences (2005)
Baruch Awerbuch, Yossi Azar, Zvi Lotker, Boaz Patt-shamir, Mark R. Tuttle
We consider a model with n players and m objects. Each player has a “preference vector ” of length m, that models his grades for all objects. The grades are initially unknown to the players. A...
Truthful Approximation Mechanisms for Scheduling Selfish Related Machines (2005)
Nir Andelman, Yossi Azar, Motti Sorani
Abstract We consider the problem of scheduling jobs on related machines owned by selfish agents. Pre-viously, Archer and Tardos showed a 2-approximation randomized mechanism which is truthful in...
Collaborate With Strangers To Find Own Preferences (2005)
Baruch Awerbuch, Yossi Azar, Zvi Lotker, Boaz Patt-shamir, Mark R. Tuttle
We consider a model with n players and m objects. Each player has an unknown grade for each object, modeled by a “preference vector ” of length m. A player can learn his grade for an object by...
An improved algorithm for CIOQ switches (2005)
The problem of maximizing the weighted throughput in various switching settings has been intensively studied recently through competitive analysis. To date, the most general model that has been...
The zero-one principle for switching networks (2004)
Recently, approximation analysis has been extensively used to study algorithms for routing weighted packets in various network settings. Although dierent techniques were applied in the analysis of...
All-norm approximation for scheduling on identical machines (2004)
We consider the problem of assigning jobs to m identical machines. The load of a machine is the sum of the weights of jobs assigned to it. The goal is to minimize the norm of the resulting load...
Maximizing throughput in multi-queue switches (2004)
We study a basic problem in Multi-Queue switches. A switch connects m input ports to a single output port. Each input port is equipped with an incoming FIFO queue with bounded capacity B. A switch...
An improved algorithm for CIOQ switches (2004)
Abstract The problem of maximizing the weighted throughput in various switching settings has beenintensively studied recently through competitive analysis. To date, the most general model that has...
A general approach to online network optimization problems (2004)
Noga Alon, Baruch Awerbuch, Yossi Azar, Niv Buchbinder, Joseph (seffi Naor
Abstract We study a wide range of online graph and network optimization problems, focusing on problems that arise in the study of connectivity and cuts in graphs. In a general online network design...
An improved algorithm for CIOQ switches (2004)
Abstract. The problem of maximizing the weighted throughput in various switching settings has been intensively studied recently through competitive analysis. To date, the most general model that has...
Distributed error confinement (2003)
Yossi Azar, Shay Kutten, Boaz Patt-shamir
We initiate the study of error confinement in distributed applications, where the goal is that only nodes that were directly hit by a fault may deviate from their correct external behavior, and only...
Optimal oblivious routing in polynomial time (2003)
Yossi Azar, Edith Cohen, Amos Fiat, Haim Kaplan, Harald Räcke
A recent seminal result of Räcke is that for any undirected network there is an oblivious routing algorithm with a polylogarithmic competitive ratio with respect to congestion. Unfortunately,...
A Generic Scheme for Building Overlay Networks in Adversarial (2003)
Scenarios Ittai Abraham, Ittai Abraham, Yossi Azar
This paper presents a generic scheme for a central, yet untackled issue in overlay dynamic networks: maintaining stability over long life and against malicious adversaries. The generic scheme...
A Generic Scheme for Building Overlay Networks in Adversarial Scenarios (2003)
Ittai Abraham, Baruch Awerbuch, Yossi Azar, Yair Bartal, Dahlia Malkhi, Elan Pavlov
This paper presents a generic scheme for a central, yet untackled issue in overlay dynamic networks: maintaining stability over long life and against malicious adversaries. The generic scheme...
Management of Multi-Queue Switches in QoS Networks (2003)
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...
The Online Set Cover Problem (2003)
Noga Alon, Baruch Awerbuch, Yossi Azar, Niv Buchbinder, Joseph (Seffi) Naor
Let X = f1; 2; : : : ; ng be a ground set of n elements, and let S be a family of subsets of X , jSj = m, with a positive cost c S associated with each S 2 S.
Reducing Truth-telling Online Mechanisms to Online Optimization (2003)
Baruch Awerbuch Yossi, Yossi Azar, Adam Meyerson
We describe a general technique for converting an online algorithm B to a truthtelling mechanism. We require that the original online competitive algorithm has certain "niceness" properties...
Optimal Oblivious Routing in Polynomial Time (2003)
Yossi Azar, Edith Cohen, Amos Fiat, Haim Kaplan, Harald Räcke
A recent seminal result of Räcke is that for any network there is an oblivious routing algorithm with a polylog competitive ratio with respect to congestion. Unfortunately, Räcke's...
Combining Online Algorithms for Rejection and Acceptance (2003)
Yossi Azar, Avrim Blum, Yishay Mansour
Resource allocation and admission control are critical tasks in a communication network, that often must be performed online. Algorithms for these types of problems have been considered both under...
Minimizing Total Flow Time and Total Completion Time with Immediate Dispatching (2003)
We consider the problem of scheduling jobs arriving over time in a multiprocessor setting, with immediate dispatching, disallowing job migration. The goal is to minimize both the total flow time...
A Generic Scheme for Building Overlay Networks in Adversarial Scenarios (2003)
Ittai Abraham, Yossi Azar, Baruch Awerbuch, Yair Bartal, Dahlia Malkhi, Elan Pavlov
This paper presents a generic scheme for a central, yet untackled issue in overlay dynamic networks: maintaining stability over long life and against malicious adversaries. The generic scheme...
Temporary tasks assignment resolved (2002)
Amitai Armon, Yossi Azar, Leah Epstein, Oded Regev
Among all basic on-line load balancing problems, the only unresolved problem was load balancing of temporary tasks on unrelated machines. This open problem exists for almost a decade, see [Borodin...
Fair versus Unrestricted Bin Packing (2002)
Yossi Azar, Joan Boyar, Leah Epstein, Lene M. Favrholdt, Kim S. Larsen, Morten N. Nielsen
We consider the Unrestricted Bin Packing problem where we have bins of equal size and a sequence of items. The goal is to maximize the number of items that are packed in the bins by an on-line...
Off-line Temporary Tasks Assignment (2002)
. 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...
Temporary Tasks Assignment Resolved (2002)
Amitai Armon, Yossi Azar, Leah Epstein, Oded Regev
Among all basic on-line load balancing problems, the only unresolved problem was load balancing of temporary tasks on unrelated machines. This open problem exists for almost a decade, see [Borodin...
Distributed Error Confinement EXTENDED ABSTRACT (2002)
Yossi Azar, Shay Kutten, Boaz Patt-shamir
We initiate the study of error confinement in reactive distributed applications, where the goal is that only nodes that were directly hit by a fault may deviate from their correct external behavior,...
Distributed Error Confinement EXTENDED ABSTRACT (2002)
Yossi Azar, Shay Kutten, Boaz Patt-shamir
We initiate the study of error confinement in reactive distributed applications, where the goal is that only nodes that were directly hit by a fault may deviate from their correct external behavior,...
Temporary Tasks Assignment Resolved (2002)
Amitai Armon Yossi, Yossi Azar, Leah Epstein, Oded Regev
Among all basic on-line load balancing problems, the only unresolved problem was load balancing of temporary tasks on unrelated machines. This open problem exists for almost a decade, see [Borodin...
All-norm approximation algorithms (2002)
Yossi Azar, Leah Epstein, Yossi Richter, Gerhard J. Woeginger
Abstract A major drawback in optimization problems and in particular in scheduling prob-lems is that for every measure there may be a different optimal solution. In many cases the various measures...
The multicast bandwidth advantage in serving a web site (2001)
Yossi Azar, Meir Feder, Eyal Lubetzky, Doron Rajwan
Abstract. Delivering popular web pages to the clients results in high bandwidth and high load on the web servers. A method to overcome this problem is to send these pages, requested by many users,...
Strongly polynomial algorithms for the unsplittable flow problem (2001)
We provide the rst strongly polynomial algorithms with the best approximation ratio for all three variants of the unsplittable ow problem (UFP). In this problem we are given a (possibly directed)...
Spectral analysis of data (2001)
Yossi Azar, Amos Fiat, Anna R. Karlin, Frank Mcsherry, Jared Saia
Every action must be due to one or other of seven causes: chance, nature, compulsion, habit, reasoning, anger, or appetite.
The multicast bandwidth advantage in serving a web site (2001)
Yossi Azar, Meir Feder, Eyal Lubetzky, Doron Rajwan
Abstract. Delivering popular web pages to the clients results in high bandwidth and high load on the web servers. A method to overcome this problem is to send these pages, requested by many users,...
Spectral Analysis of Data (2001)
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...
Resource Augmentation in Load Balancing (2000)
Yossi Azar, Leah Epstein, Rob Van Stee
We consider load-balancing in the following setting. The on-line algorithm is allowed to use n machines, whereas the optimal off-line algorithm is limited to m machines, for some fixed m ! n. We show...
On-line Scheduling with Precedence Constraints (2000)
We consider the on-line problem of scheduling jobs with precedence constraints on m machines. We concentrate in two models, the model of uniformly related machines and the model of restricted...
Fair versus Unrestricted Bin Packing (2000)
Yossi Azar, Joan Boyar, Lene M. Favrholdt, Kim S. Larsen, Morten N. Nielsen
We consider the Unrestricted Bin Packing problem where we have bins of equal size and a sequence of items. The goal is to maximize the number of items that are packed in the bins by an on-line...
Baruch Awerbuch, Yossi Azar, Oded Regev
We consider a bene t model for on-line preemptive scheduling. In this model jobs arrive at the on-line scheduler at their release time. Each job arrives with its own execution time and bene t...
Off-line Temporary Tasks Assignment \Lambda (2000)
Yossi Azar, Oded Regev, Gerhard J. Woeginger
Abstract 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...
Minimizing the flow time without migration (1999)
Baruch Awerbuch, Yossi Azar, Stefano Leonardi, Oded Regev
We consider the classical problem of scheduling jobs in a multiprocessor setting in order to minimize the flow time (total time in the system). The performance of the algorithm, both in offline and...
We consider the maximum disjoint paths problem and its generalization, the call control problem, in the on-line setting. In the maximum disjoint paths problem, we are given a sequence of connection...
O-line temporary tasks assignment (1999)
Yossi Azar, Oded Regev, Jir 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...
Resource augmentation in load balancing (1999)
Yossi Azar, Leah Epstein, Rob Van Stee
We consider load balancing in the following setting. The on-line algorithm is allowed to use n machines, whereas the optimal o-line algorithm is limited to m machines, for some xed m n. We show that...
Resource augmentation in load balancing (1999)
Y. Azar, L. Epstein, R. Van Stee, Issn -x, Mathematisch Centrum (smc, The Dutch Foundation, ...
and their applications. SMC is sponsored by the Netherlands Organization for Scientific Research (NWO). CWI is a member of
Independent Sets in Hypergraphs with Applications to Routing Via Fixed Paths (1999)
Noga Alon, Uri Arad, Yossi Azar
The problem of finding a large independent set in a hypergraph by an online algorithm is considered. We provide bounds for the best possible performance ratio of deterministic vs. randomized and...
New Approximation Guarantees for Minimum-Weight k-Trees and Prize-Collecting Salesmen (1999)
Baruch Awerbuch, Yossi Azar, Avrim Blum, Santosh Vempala
We consider a formalization of the following problem. A salesperson must sell some quota of brushes in order to win a trip to Hawaii. This salesperson has a map (a weighted graph) in which each city...
Off-line Temporary Tasks Assignment (1999)
Yossi Azar, Oded Regev, Jir 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...
Minimizing the Flow Time without Migration (1999)
Baruch Awerbuch Yossi, Yossi Azar, Stefano Leonardi, Oded Regev
We consider the classical problem of scheduling jobs in a multiprocessor setting in order to minimize the flow time (total time in the system). The performance of the algorithm, both in offline and...
On-line and off-line approximation algorithms for vector covering problems. Algorithmica (1998)
Noga Alon, Yossi Azar, János Csirik, Leah Epstein, Gerhard J. Woeginger
This paper deals with vector covering problems in d-dimensional space. The input to a vector covering problem consists of a set X of d-dimensional vectors in [0, 1] d. The goal is to partition X into...
Approximation schemes for scheduling on parallel machines (1998)
Noga Alon, Yossi Azar, Gerhard J. Woeginger, Tal Yadid
We discuss scheduling problems with m identical machines and n jobs where each job has to be assigned to some machine. The goal is to optimize objective functions that solely depend on the machine...
Approximation schemes for scheduling on parallel machines (1998)
Noga Alon, Yossi Azar, Gerhard J. Woeginger, Tal Yadid
We discuss scheduling problems with m identical machines and n jobs where each job has to be assigned to some machine. The goal is to optimize objective functions that solely depend on the machine...
On-line and off-line approximation algorithms for vector covering problems. Algorithmica (1998)
Noga Alon, Yossi Azar, J Anos Csirik, Leah Epstein, Sergey V. Sevastianov, ...
This paper deals with vector covering problems in d-dimensional space. The input to a vector covering problem consists of a set X of d-dimensional vectors in [0; 1] d. The goal is to partition X into...
We consider the maximum disjoint paths problem and its generalization, the call control problem, in the on-line setting. In the maximum disjoint paths problem, we are given a sequence of connection...
Ancient and New Algorithms for Load Balancing in the L_p Norm (1998)
Adi Avidor, Yossi Azar, Jirí Sgall
We consider the on-line load balancing problem where there are m identical machines (servers) and a sequence of jobs. The jobs arrive one by one and should be assigned to one of the machines in an...
Approximating Probability Distributions Using Small Sample Spaces (1998)
Yossi Azar, Rajeev Motwani, Joseph (seffi Naor
Dedicated to the memory of Paul Erdős We formulate the notion of a “good approximation ” to a probability distribution over a finite abelian group G. The quality of the approximating...
On Two Dimensional Packing (1997)
The paper considers packing of rectangles into an infinite bin. Similar to the Tetris game, the rectangles arrive from the top and, once placed, cannot be moved again. The rectangles are moved inside...
James Aspnes, Yossi Azar, Amos Fiat, Serge Plotkin, Orli Waarts
. In this paper we study the problem of on-line allocation of routes to virtual circuits (both point-to-point and multicast) where the goal is to route all requests while minimizing the required...
James Aspnes, Yossi Azar, Amos Fiat, Serge Plotkin, Orli Waarts
In this paper we study the problem of on-line allocation of routes to virtual circuits (both point-to-point and multicast) where the goal is to route all requests while minimizing the required...
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...
Buy-at-Bulk Network Design (1997)
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....
Approximation Schemes for Scheduling (1997)
Noga Alon, Yossi Azar, Gerhard J. Woeginger, Tal Yadid
We consider the classic scheduling/load balancing problems where there are m identical machines and n jobs, and each job should be assigned to some machine. Traditionally, the assignment of jobs to...
James Aspnes, Yossi Azar, Amos Fiat, Serge Plotkin, Orli Waarts
In this paper we study the problem of on-line allocation of routes to virtual circuits (both point-to-point and multicast) where the goal is to minimize the required bandwidth. We concentrate on the...
Ancient and New Algorithms for Load Balancing in the L_p Norm (1997)
Adi Avidor, Yossi Azar, Jirí Sgall
We consider the on-line load balancing problem where there are m identical machines (servers) and a sequence of jobs. The jobs arrive one by one and should be assigned to one of the machines in an...
On-Line Load Balancing of Temporary Tasks on Identical Machines (1997)
We prove an exact lower bound of 2 \Gamma 1 m on the competitive ratio of any deterministic algorithm for load balancing of temporary tasks on m identical machines. We also show a lower bound of 2...
Baruch Awerbuch, Yossi Azar, Tom Leighton
In this paper, we formulate and provide optimal solutions for a broad class of problems in which a decision-maker is required to select from among numerous competing options. The goal of the...
On-line Competitive Algorithms for Call Admission in Optical Networks (1996)
Baruch Awerbuch, Yossi Azar, Amos Fiat, Stefano Leonardi, Adi Rosén
In the present work we study the on-line call admission problem in optical networks. We present a general technique to deal with the problem of call admission and wavelength selection by reducing...
Packet Routing via Min-Cost Circuit Routing (1996)
Baruch Awerbuch, Yossi Azar, Amos Fiat
In this paper we initiate the study of competitive on-line packet routing algorithms. At any time, any network node may initiate sending a packet to another node. Our goal is to route these packets...
Baruch Awerbuch, Yossi Azar, Tom Leighton
In this paper, we formulate and provide optimal solutions for a broad class of problems in which a decision-maker is required to select from among numerous competing options. The goal of the...
On-line Generalized Steiner Problem (1996)
Baruch Awerbuch, Yossi Azar, Yair Bartal
The Generalized Steiner Problem (GSP) is defined as follows. We are given a graph with non-negative weights and a set of pairs of vertices. The algorithm has to construct minimum weight subgraph such...
Load balancing in the L_p norm (1995)
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....
Competitive multicast routing (1995)
In this paper, we introduce and solve the multicast routing problem for virtual circuit environment without making any assumptions about the communication patterns, or about the network topology. By...
Load balancing in the L_p norm (1995)
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....
Improved Approximation Guarantees for Minimum-Weight (1995)
Trees And, Baruch Awerbuch, Yossi Azar, Avrim Blum, Santosh Vempala
Consider a salesperson that must sell some quota of brushes in order to win a trip to Hawaii. This salesperson has a map (a weighted graph) in which each city has an attached demand specifying the...
Competitive Routing of Virtual Circuits with Unknown Duration (1995)
Baruch Awerbuch, Yossi Azar, Serge Plotkin, Orli Waarts
In this paper we present a strategy to route unknown duration virtual circuits in a highspeed communication network. Previous work on virtual circuit routing concentrated on the case where the call...
Improved Approximation Guarantees for Minimum-Weight k-Trees and Prize-Collecting Salesmen (1995)
Baruch Awerbuch, Yossi Azar, Avrim Blum, And Santosh Vempala, Santosh Vempala
Consider a salesperson that must sell some quota of brushes in order to win a trip to Hawaii. This salesperson has a map (a weighted graph) in which each city has an attached demand specifying the...
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....
Approximating Probability Distributions Using Small Sample Spaces (1995)
Yossi Azar, Rajeev Motwani, Joseph (Seffi) Naor
We formulate the notion of a "good approximation" to a probability distribution over a finite abelian group. The approximate distribution is characterized by a parameter ffl, the quality of...
Improved Approximation Guarantees for Minimum-Weight k-Trees and Prize-Collecting Salesmen (1995)
Baruch Awerbuch, Yossi Azar, Avrim Blum, Santosh Vempala
We consider a formalization of the following problem. A salesperson must sell some quota of brushes in order to win a trip to Hawaii. This salesperson has a map (a weighted graph) in which each city...
Load balancing in the lp norm (1995)
Baruch Awerbuch, Yossi Azar, P. Krishnan
Abstract. 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...
Approximating Probability Distributions Using Small Sample Spaces (1995)
Yossi Azar, Rajeev Motwani, Joseph (Seffi) Naor
We formulate the notion of a "good approximation" to a probability distribution over a finite abelian group G . The quality of the approximating distribution is characterized by a parameter...
Competitive Routing of Virtual Circuits with Unknown Duration (1994)
Baruch Awerbuch, Yossi Azar, Serge Plotkin, Orli Waarts
In this paper we present a strategy to route unknown duration virtual circuits in a highspeed communication network. Previous work on virtual circuit routing concentrated on the case where the call...
Combining online algorithms for rejection and acceptance (1994)
Yossi Azar, Avrim Blum, Yishay Mansour
Resource allocation and admission control are critical tasks in a communication network, that often must be performed online. Algorithms for these types of problems have been considered both under...
Yossi Azar, Andrei Z. Broder, Anna R. Karlin, Eli Upfal
Abstract. Suppose that we sequentially place n balls into n boxes by putting each ball into a randomly chosen box. It is well known that when we are done, the fullest box has with high probability (1...
Competitive Routing of Virtual Circuits with Unknown Duration (1994)
Baruch Awerbuch, Yossi Azar, Serge Plotkin, Orli Waarts
In this paper we present a strategy to route unknown duration virtual circuits in a highspeed communication network. Previous work on virtual circuit routing concentrated on the case where the call...
Lower Bounds for Insertion Methods for TSP (1994)
We show that the random insertion method for the traveling salesman problem (TSP) may produce a tour \Omega\Gammaur/ log n= log log log n) times longer than the optimal tour. The lower bound holds...
Improved Approximation Guarantees for Minimum-Weight (1994)
Trees And Prize-Collecting, Baruch Awerbuch, Yossi Azar, Avrim Blum, Santosh Vempala
Consider a salesperson that must sell some quota of brushes in order to win a trip to Hawaii. This salesperson has a map (a weighted graph) in which each city has an attached demand specifying the...
Competitive On-line Selective Multicast via Dense Trees Construction (Extended Abstract) (1994)
Baruch Awerbuch, Yossi Azar, Rainer Gawlick
) Baruch Awerbuch 1;2 Yossi Azar 3 Rainer Gawlick 2 1 Johns Hopkins University 2 Laboratory for Computer Science, MIT 3 Tel-Aviv University May 3, 1994 Abstract This paper introduces the problem of...
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...
Blindly-Competitive Algorithms for Pricing & Bidding (Extended Abstract) (1994)
) Baruch Awerbuch Yossi Azar y November 30, 1994 Abstract The standard setting for competitive analysis of online algorithms assumes that online algorithm knows the past (but not future) inputs, and...
Yossi Azar, Andrei Z. Broder, Anna R. Karlin, Eli Upfal
Suppose that we sequentially place n balls into n boxes by putting each ball into a randomly chosen box. It is well known that when we are done, the fullest box has with high probability (1 + o(1))...
Competitive Routing of Virtual Circuits with Unknown Duration (1994)
Baruch Awerbuch, Yossi Azar, Serge Plotkin, Orli Waarts
In this paper we present a strategy to route unknown duration virtual circuits in a highspeed communication network. Previous work on virtual circuit routing concentrated on the case where the call...
On-line Load Balancing of Temporary Tasks (1993)
Yossi Azar, Bala Kalyanasundaram, Serge Plotkin, Kirk R. Pruhs, Orli Waarts
This paper considers the non-preemptive on-line load balancing problem where tasks have limited duration in time. Upon arrival, each task has to be immediately assigned to one of the machines,...
On-line Choice of On-line Algorithms (1993)
Yossi Azar, Andrei Z. Broder, Mark S. Manasse
Let fA1 ; A2 ; : : : ; Amg be a set of on-line algorithms for a problem P with input set I. We assume that P can be represented as a metrical task system. Each A i has a competitive ratio a i with...
On-line Steiner Trees in the Euclidean Plane (1993)
Suppose we are given a sequence of n points in the Euclidean plane, and our objective is to construct, on-line, a connected graph that connects all of them, trying to minimize the total sum of...
On-line Load Balancing of Temporary Tasks (1993)
Yossi Azar, Bala Kalyanasundaram, Serge Plotkin, Kirk R. Pruhs, Orli Waarts
This paper considers the non-preemptive on-line load balancing problem where tasks have limited duration in time. Upon arrival, each task has to be immediately assigned to one of the machines,...
Throughput-Competitive On-Line Routing (1993)
Baruch Awerbuch, Yossi Azar, Serge 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...
Throughput-Competitive On-Line Routing (1993)
Baruch Awerbuch, Yossi Azar, Serge 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...
On-line Load Balancing of Temporary Tasks (1993)
Yossi Azar, Bala Kalyanasundaram, Serge Plotkin, Kirk R. Pruhs, Orli Waarts
This paper considers the non-preemptive on-line load balancing problem where tasks have limited duration in time. Upon arrival, each task has to be immediately assigned to one of the machines,...
Throughput-Competitive On-Line Routing (1993)
Baruch Awerbuch, Yossi Azar, Serge 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...
On-line Steiner trees in the Euclidean plane (1993)
Suppose we are given a sequence of n points in the Euclidean plane, and our objective is to construct, on-line, a connected graph that connects all of them, trying to minimize the total sum of...
. We survey on-line load balancing on various models. 1 Introduction General: The machine load balancing problem is defined as follows: There are n parallel machines and a number of independent tasks...
Lower Bounds For Threshold And Symmetric Functions In Parallel Computation (1992)
We consider the family of decision problems of the threshold languages L g . A threshold language L g is the set of n bit vectors having at least g(n) "1"s. Using a new technique for...
The Competitiveness of On-Line Assignments (1992)
Yossi Azar, Joseph (Seffi) Naor, Raphael Rom
Consider the on-line problem where a number of servers are ready to provide service to a set of customers. Each customer's job can be handled by any of a subset of the servers. Customers arrive...
Routing Strategies for Fast Networks (1992)
Yossi Azar, Joseph Naor, Raphael Rom
Modern fast packet switching networks forced to rethink the routing schemes that are used in more traditional networks. The reexamination is necessitated because in these fast networks switches on...
The Competitiveness of On-Line Assignments (1992)
Yossi Azar, Joseph (seffi Naor, Raphael Rom
Consider the on-line problem where a number of servers are ready to provide service to a set of customers. Each customer's job can be handled by any of a subset of the servers. Customers arrive...
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...
Yossi Azar, Andrei Z. Broder, Anna R. Karlin, Nathan Linial, Steven 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...
Comparison-Sorting and Selecting in Totally Monotone Matrices (1992)
An m \Theta n matrix A is called totally monotone if for all i 1 ! i 2 and j1 ! j2 , A[i1 ; j1 ] ? A[i1 ; j2 ] implies A[i2 ; j1 ] ? A[i2 ; j2 ]. We consider the complexity of comparison-based...
Tight Comparison Bounds On The Complexity Of Parallel Sorting (1987)
The problem of sorting n elements using p processors in a parallel comparison model is considered. Lower and upper bounds which imply that for p ³ n, the time complexity of this problem is Q( log(1...