Yossi Azar

Yossi Azar

Auto-generated profile, based on publicly available information

Yossi Azar

Tel Aviv University, Tel Aviv, Israel

Research Focus & Metrics

Academic Career Length

41Years (1986-Present)

(Calculated once Scilit publication data is synced: current year − year of first publication + 1)

Representative Publications

View All Publications
1 January 1999 in SIAM Journal on Computing
Verified
Journal Article
Closed access
YAYossi Azar
Yossi Azar
ABAndrei Z. Broder
Andrei Z. Broder
AKAnna R. Karlin
Anna R. Karlin
EUEli Upfal
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))ln n/ln ln n balls in it. Suppose instead that for each ball we choose two boxes at random and place the ball into the one which is less full at the time of placement. We show that with high probability, the fullest box contains only ln ln n/ln 2 + O(1) balls---exponentially less than before. Furthermore, we show that a similar gap exists in the infinite process, where at each step one ball, chosen uniformly at random, is deleted, and one ball is added in the manner above. We discuss consequences of this and related theorems for dynamic resource allocation, hashing, and on-line load balancing.

1 May 1997 in Journal of the ACM
Verified
Journal Article
Open access
JAJames Aspnes
James Aspnes
YAYossi Azar
Yossi Azar
AFAmos Fiat
Amos Fiat
SPSerge Plotkin
Serge Plotkin
OWOrli Waarts
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 bandwidth. We concentrate on the case of Permanent virtual circuits (i.e., once a circuit is established it exists forever), and describe an algorithm that achieves on O (log n ) competitive ratio with respect to maximum congestin, where n is the number of nodes in the network. Informally, our results show that instead of knowing all of the future requests, it is sufficient to increase the bandwidth of the communication links by an O (log n ) factor. We also show that this result is tight, that is, for any on-line algorithm there exists a scenario in which Ω(log n ) increase in bandwidth is necessary in directed networks. We view virtual circuit routing as a generalization of an on-line load balancing problem, defined as follows: jobs arrive on line and each job must be assigned to one of the machines immediately upon arrival. Assigning a job to a machine increases the machine's load by an amount that depends both on the job and on the machine. The goal is to minimize the maximum load. For the related machines case, we describe the first algorithm that achieves constant competitive ratio. for the unrelated case (with n machines), we describe a new method that yields O (log n )-competitive algorithm. This stands in contrast to the natural greed approach, whose competitive ratio is exactly n .

6 July 2001
Verified
Conference Paper
Open access
PDF file
YAYossi Azar
Yossi Azar
AFAmos Fiat
Amos Fiat
AKAnna Karlin
Anna Karlin
FMFrank McSherry
Frank McSherry
JSJared Saia
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.

30 December 2002
Verified
Conference Paper
Closed access
BAB. Awerbuch
B. Awerbuch
YAY. Azar
Y. Azar
SPS. Plotkin
S. Plotkin

1 March 1995 in Journal of Algorithms
Verified
Journal Article
Closed access
YAY. Azar
Y. Azar
JNJ. Naor
J. Naor
RRR. Rom
R. Rom

1 January 2009 in SIAM Journal on Computing
Verified
Journal Article
Closed access
NANoga Alon
Noga Alon
BABaruch Awerbuch
Baruch Awerbuch
YAYossi Azar
Yossi Azar
NBNiv Buchbinder
Niv Buchbinder
JNJoseph (Seffi) Naor
Joseph (Seffi) Naor
Let $X=\{1,2,\ldots,n\}$ be a ground set of n elements, and let ${\cal S}$ be a family of subsets of X, $|{\cal S}|=m$, with a positive cost $c_S$ associated with each $S\in{\cal S}$. Consider the following online version of the set cover problem, described as a game between an algorithm and an adversary. An adversary gives elements to the algorithm from X one by one. Once a new element is given, the algorithm has to cover it by some set of ${\cal S}$ containing it. We assume that the elements of X and the members of ${\cal S}$ are known in advance to the algorithm; however, the set $X'\subseteq X$ of elements given by the adversary is not known in advance to the algorithm. (In general, $X'$ may be a strict subset of X.) The objective is to minimize the total cost of the sets chosen by the algorithm. Let ${\cal C}$ denote the family of sets in ${\cal S}$ that the algorithm chooses. At the end of the game the adversary also produces (offline) a family of sets ${\cal C}_{OPT}$ that covers $X'$. The performance of the algorithm is the ratio between the cost of ${\cal C}$ and the cost of ${\cal C}_{OPT}$. The maximum ratio, taken over all input sequences, is the competitive ratio of the algorithm. We present an $O(\log m\log n)$ competitive deterministic algorithm for the problem and establish a nearly matching $\Omega\bigl(\frac{\log n\log m}{\log\log m+\log\log n}\bigr)$ lower bound for all interesting values of m and n. The techniques used are motivated by similar techniques developed in computational learning theory for online prediction (e.g., the WINNOW algorithm) together with a novel way of converting a fractional solution into a deterministic online algorithm.