Yossi Azar's home page

Prof. Yossi Azar
Dept. of Computer Science
Tel-Aviv University
Tel-Aviv 69978
Israel

• E-mail: azar at tau dot ac dot il
  

Fields of interest

• ON-LINE ALGORITHMS
• APPROXIMATION METHODS
• LOAD BALANCING
• ROUTING SCHEMES
• PROBABILISTIC METHODS
• ALGORITHMIC GAME THEORY

Program Committee

ESA 2006 (Chairman),
WAOA 2008, FOCS 2008, ESA 2008, ICALP 2007, ESCAPE 2007, SODA 2006,
SODA 2005, WAOA 2004, APPROX 2003, WEA 2001, ESA 2000, RANDOM 2000.

• Spring 2009/10 Online and Approximation Algorithms

Survey

• On-line Load Balancing
  Online Algorithms - The State of the Art, chapter 8, 178-195, Springer, 1998.
  
  

Available papers

• Optimal Node Routing
  Y. Azar, Y. Chaiutin.
  Proc. 23rd STACS (2006), 596-607.
  
  
• The hardness of network design for unsplittable flow with selfish users
  Y. Azar, A. Epstein.
  Proc. of 3rd WAOA (2005), 41-54.
  
  
• Packet routing and information gathering in lines, rings and trees
  Y. Azar, R. Zachut.
  Proc. of 13th ESA (2005), 484-495.
  
  
• Admission control to minimize rejections and online set cover with repetitions
  N. Alon, Y. Azar, S. Gutner.
  Proc. of 17th SPAA (2005), 238-244.
  
  
• Collaborate with strangers To find own preferences
  B. Awerbuch, Y. Azar, Z. Lotker, B. Patt-Shamir, M. Tuttle.
  Proc. of 17th SPAA (2005), 263-269.
  
  
• Convex programming for scheduling unrelated parallel machines
  Y. Azar, A. Epstein.
  Proc. of 37th STOC (2005), 331-337.
  
  
• The price of routing unsplittable flow
  B. Awerbuch, Y. Azar, A. Epstein.
  Proc. of 37th STOC (2005), 57-66.
  
  
• Truthful approximation mechanisms for scheduling selfish related machines
  N. Andelman, Y. Azar, M. Sorani.
  Proc. of 22nd STACS (2005), 69-82.
  
  
• Maximizing throughput in multi-queue switches
  Y. Azar, A. Litichevskey.
  Proc. of 12th ESA (2004), 53-64.
  
  
• An improved algorithm for CIOQ switches
  Y. Azar, Y. Richter.
  Proc. of 12th ESA (2004), 65-76.
  
  
• All-Norm Approximation for Scheduling on Identical Machines
  Y. Azar, S. Taub.
  Proc. of 9th SWAT (2004), 298-310.
  
  
• The zero-one principle for switching networks
  Y. Azar, Y. Richter.
  Proc. of 36th STOC (2004), 64-71.
  
  
• A general approach to online network optimization problems
  N. Alon, B. Awerbuch, Y. Azar, N. Buchbinder, J. Naor.
  Proc. of 15th SODA (2004), 570-579.
  
  
• Tradeoffs in worst-case equilibria
  B. Awerbuch, Y. Azar, Y. Richter, D. Tsur.
  Proc. of 1st WAOA (2003), 41-52.
  
  
• Load balancing of temporary tasks in the l_p norm
  Y. Azar, A. Epstein, L. Epstein.
  Proc. of 1st WAOA (2003), 53-66.
  
  
• The online set cover problem
  N. Alon, B. Awerbuch, Y. Azar, N. Buchbinder, J. Naor.
  Proc. of 35th STOC (2003), 100-105.
  
  
• Optimal oblivious routing in polynomial time
  Y. Azar, E. Cohen, A. Fiat, H. Kaplan, H. R\"acke.
  Proc. of 35th STOC (2003), 383-388.
  
  
• Reducing truth-telling online mechanisms to online optimization
  B. Awerbuch, Y. Azar, A. Meyerson.
  Proc. of 35th STOC (2003), 503-510.
  
  
• Management of multi-queue switches in QoS networks
  Y. Azar, Y. Richter.
  Proc. of 35th STOC (2003), 82-89.
  
  
• Combining online algorithms for rejection and acceptance
  Y. Azar, A. Blum, Y. Mansour.
  Proc. of 15th SPAA (2003), 159-163.
  
  
• Minimizing total flow time and total completion time with immediate dispatching
  N. Avrahami, Y. Azar.
  Proc. of 15th SPAA (2003), 11-18.
  
  
• A generic scheme for building overlay networks in adversarial scenarios
  I. Abraham, B. Awerbuch, Y. Azar, Y. Bartal, D. Malkhi, E. Pavlov.
  Proc. of 17th IPDPS (2003).
  
  
• Distributed error confinement
  Y. Azar, S. Kutten, B. Patt-Shamir.
  Proc. of 22nd PODC (2003), 33-42.
  
  
• All-norm approximation algorithms
  Y. Azar, L. Epstein, Y. Richter, G. Woeginger.
  Proc. of 8th SWAT (2002), 288-297.
  
  
• Temporary tasks assignment resolved
  A. Armon, Y. Azar, L. Epstein, O. Regev.
  Proc. of 13th SODA (2002), 116-124.
  
  
• The Multicast Bandwidth Advantage in Serving a Web Site
  Y. Azar, M. Feder, E. Lubetzky, D. Rajwan, N. Shulman.
  Proc. of 3rd NGC (2001), 88-99.
  
  
• Strongly polynomial algorithms for the unsplittable flow problem
  Y. Azar, O. Regev.
  Proc. of 8th IPCO (2001), 15-29.
  
  
• Spectral analysis for data dining
  Y. Azar, A. Fiat, A. Karlin, F. McSherry, J. Saia.
  Proc. of 33rd STOC (2001), 619-626.
  
  
• Maximizing job benefits on-line
  B. Awerbuch, Y. Azar, O. Regev.
  Proc. of 3rd APPROX (2000), 42-50.
  
  
• Resource augmentation in load balancing
  Y. Azar, L. Epstein, R. van Stee.
  Proc. of 7th SWAT (2000), 189-199. Also in J. of Scheduling 3 (2000), 249-258.
  
  
• On-line scheduling with precedence constraints
  Y. Azar, L. Epstein.
  Proc. of 7th SWAT (2000), 164-174.
  
  
• Fair versus unrestricted bin packing
  Y. Azar, J. Boyar, L. Favrholdt, K. S. Larsen, M. Nielsen.
  Proc. of 7th SWAT (2000), 200-213.
  
  
• Independent sets in hypergraphs with applications to routing via fixed paths
  N. Alon, U. Arad, Y. Azar.
  Proc. of 2nd APPROX (1999), 16-27.
  
  
• Off-line temporary tasks assignment
  Y. Azar, O. Regev.
  Proc. of 7th ESA (1999), 163-171.
  
  
• Minimizing the flow time without migration
  B. Awerbuch, Y. Azar, S. Leonardi, O. Regev.
  Proc. of 31st STOC (1999), 198-205.
  
  
• Beating the logarithmic lower bound: randomized preemptive disjoint paths and call control algorithms
  R. Adler, Y. Azar.
  Proc. of 10th SODA (1999), 1-10. Also in Journal of Scheduling.
  
  
• On-line bin-stretching
  Y. Azar, O. Regev.
  Proc. of 2nd. RANDOM (1998), 71-81. Also in TCS 268 (2001), pp. 17-41.
  
  
• Approximation schemes for covering and scheduling on related machines
  Y. Azar, L. Epstein.
  Proc. of 1st APPROX (1998), 39-47.
  
  
• On-line and off-line approximation algorithms for vector covering problems
  N. Alon, Y. Azar, J. Csirik, L. Epstein, S. Sevastianov, A. Vestjens, G. Woeginger.
  Algorithmica 21 (1998), 104-118.
  
  
• Ancient and new algorithms for load balancing in the L_p norm
  A. Avidor, Y. Azar, J. Sgall.
  Proc. of 9th SODA (1998), 426-435. Also in Algorithmica 29 (2001), 422-441.
  
  
• Approximating probability distributions using small sample spaces
  Y. Azar, R. Motwani, J. Naor.
  Combinatorica 18(2) (1998), 151-171.
  
  
• Buy-at-bulk network design
  B. Awerbuch, Y. Azar.
  Proc. of 38th FOCS (1997), 542-547.
  
  
• On-Line machine covering
  Y. Azar, L. Epstein.
  Proc. of 5th ESA (1997), 23-36. Also in J. of Scheduling 1 (1998), 67-77.
  
  
• On-line load balancing of temporary tasks on identical machines
  Y. Azar, L. Epstein.
  Proc. of 5th ISTCS (1997), 119-125.
  
  
• Approximation schemes for scheduling
  N. Alon, Y. Azar, G. Woeginger, T. Yadid.
  Proc. of 8th SODA (1997), 493-500. Also in J. of Scheduling 1 (1998), 55-66.
  
  
• On-line competitive algorithms for call admission in optical networks
  B. Awerbuch, Y. Azar, A. Fiat, S. Leonardi, A. Rosen.
  Proc. of 4th ESA (1996), 431-444. Also in Algorithmica 31:1 (2001), 29-43.
  
  
• On capital investment
  Y. Azar, Y. Bartal, E. Feuerstein, A. Fiat, S. Leonardi, A. Rosen.
  Proc. of 23rd ICALP (1996), 429-441. Also in Algorithmica 25 (1999), 22-36.
  
  
• On two dimensional packing
  Y. Azar, L. Epstein.
  Proc. of 5th SWAT (1996), 321-332. Also in J. of Algorithms 25 (1997), 290-310.
  
  
• Packet routing via min-cost circuit routing
  B. Awerbuch, Y. Azar, A. Fiat.
  Proc. of 4th ISTCS (1996), 37-42.
  
  
• Making commitments in the face of uncertainty: how to pick a winner almost every time
  B. Awerbuch, Y. Azar, A. Fiat, T. Leighton.
  Proc. of 28th STOC (1996), 519-530.
  
  
• On-line generalized steiner problem
  B. Awerbuch, Y. Azar, Y. Bartal.
  Proc. of 7th SODA (1996), 68-74.
  
  
• Competitive multicast routing
  B. Awerbuch, Y. Azar.
  Wireless Networks 1 (1995), 107-114.
  
  
• Load balancing in the L_p norm
  B. Awerbuch, Y. Azar, E. Grove, M. Kao, P. Krishnan, J. Vitter.
  Proc. of 36th FOCS (1995), 383-391.
  
  
• Improved approximation guarantees for minimum-weight k-trees and prize-collecting salesmen
  B. Awerbuch, Y. Azar, A. Blum, S. Vempala.
  Proc. of 27th STOC (1995), 277-283. Also in SIAM J. Computing, 28 (1999), 254-262.
  
  
• Local optimization of global objectives: competitive distributed deadlock resolution and resource allocation
  B. Awerbuch, Y. Azar.
  Proc. of 35th FOCS (1994), 240-249.
  
  
• Balanced allocation
  Y. Azar, A. Broder, A. Karlin, E. Upfal.
  Proc. of 26th STOC (1994), 593-602. Also in SIAM J. Computing, 29 (1999), 180-200.
  
  
• On the problem of approximating the number of bases of a matroid
  Y. Azar, A. Broder, A. Frieze.
  Information Processing Letters 50 (1994), 9-11.
  
  
• Lower bounds for insertion methods for TSP
  Y. Azar.
  Combinatorics, Probability and Computing 3 (1994), 285-292.
  
  
• Competitive routing of virtual circuits with unknown duration
  B. Awerbuch, Y. Azar, S. Plotkin, O. Waarts.
  Proc. of 5th SODA (1994), 321-327. Also in JCSS 62 (2001), 385-397.
  
  
• Throughput-competitive online routing
  B. Awerbuch, Y. Azar, S. Plotkin.
  Proc. of 34th FOCS (1993), 32-40.
  
  
• On-line load balancing of temporary tasks
  Y. Azar, B. Kalyanasundaram, S. Plotkin, K. Pruhs, O. Waarts.
  Proc. of 3rd WADS (1993), 119-130. Also in Journal of Algorithms 22 (1997), 93-110.
  
  
• On-line load balancing with applications to machine scheduling and virtual circuit routing
  J. Aspnes, Y. Azar, A. Fiat, S. Plotkin, O. Waarts.
  Proc. of 25th STOC (1993), 623-631. Also in Journal of the ACM 44 (1997), 486-504.
  
  
• On-line choice of on-line algorithms
  Y. Azar, A. Broder, M. Manasse.
  Proc. of 4th SODA (1993), 432-440.
  
  
• On-line Steiner trees in the Euclidean plane
  N. Alon, Y. Azar.
  Proc. of 8th Computational Geometry (1992), 337-343. Also in Discrete and Computational Geometry 10 (1993), 113-121.
  
  
• Routing strategies for fast networks
  Y. Azar, J. Naor, R. Rom.
  Proc. of 11th INFOCOM (1992), 170-179. Also in IEEE Transactions on Computers 45 (1996), 165-173.
  
  
• On-line load balancing
  Y. Azar, A. Broder, A. Karlin.
  Proc. of 33rd FOCS (1992), 218-225. Also in Theoretical Computer Science 130 (1994), 73-84.
  
  
• Biased random walks
  Y. Azar, A. Broder, A. Karlin, N. Linial, S. Phillips.
  Proc. of 24th STOC (1992), 1-9. Also in Combinatorica 16 (1996), 1-18.
  
  
• The competitiveness of on-line assignments
  Y. Azar, J. Naor, R. Rom.
  Proc. of 3rd SODA (1992), 203-210. Also in Journal of Algorithms 18 (1995), 221-237.
  
  
• Comparison sorting and selecting in totally monotone matrices
  N. Alon, Y. Azar.
  Proc. of 3rd SODA (1992), 403-408.
  
  
• Lower bounds for threshold and symmetric functions in parallel computation
  Y. Azar.
  SIAM J. Computing 21 (1992), 329-338.
  
  
• Parallel comparison merging of many ordered lists
  Y. Azar.
  Theoretical Computer Science 83 (1991), 275-285.
  
  
• Universal sequences for complete graphs
  N. Alon, Y. Azar, Y. Ravid.
  Discrete Applied Math. 27 (1990), 25-28.
  
  
• Parallel selection
  Y. Azar, N. Pippenger.
  Discrete Applied Math. 27 (1990), 49-58.
  
  
• Finding an approximate maximum
  N. Alon, Y. Azar.
  SIAM J. Computing 18 (1989), 258-267.
  
  
• Parallel comparison algorithms for approximation problems
  N. Alon, Y. Azar.
  Proc. of 29th FOCS (1988), 194-203. Also in Combinatorica 11 (1991), 97-122.
  
  
• Sorting, approximate sorting and searching in rounds
  N. Alon, Y. Azar.
  SIAM J. Discrete Math. 1 (1988), 269-280.
  
  
• The average complexity of deterministic and randomized parallel comparison sorting algorithms
  N. Alon, Y. Azar.
  Proc. of 28th FOCS (1987), 489-498. Also in SIAM J. Computing 17 (1988), 1178-1192.
  
  
• Tight complexity bounds for parallel comparison sorting
  N. Alon, Y. Azar, U. Vishkin.
  Proc. of 27th FOCS (1986), 502-510. Also in SIAM J. Computing 16 (1987), 458-464.
  
  

Useful links

• NEC Search
• DBLP
• The Electronic Colloquium on Computational Complexity