Yossi Azar's home page

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

• E-mail: azar at tau dot ac dot il
  
• Phone: +972-3-6407442
  

Fields of interest

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

Ph.D Students (current and previous)

• Leah Epstein
• Oded Regev
• Yossi Richter
• Amir Epstein
• Shai Gutner
• Iftah Gamzu
• Ilan Cohen
• Adi Vardi
• Danny Vainstein
• Noam Touitou
• Shahar Lewkowicz
• Or Vardi

M.Sc Students (current and previous)

• Leah Epstein, Oded Regev, Adi Avidor, Tal Yadid, Ran Adler, Uri Arad,
  Amitai Armon, Yossi Richter, Nir Avrahami, Amir Epstein, Shai Taub, Arik Ganot,
  Arik Litichevskey, Motti Sorani, Rafi Zachut, Yoel Chaiutin, Nir Levy, Iftah Gamzu,
  Daniel Glasner, Ilan Cohen, Ran Roth, Ety Haitsin, Eytan Kidron, Naama Ben-Aroya,
  Adi Vardi, Inna Kalp, Idan Maor, Oren Gilon, Danny Vainstein, Mark Berlin,
  Noam Touitou, Amit Jacob-Fanani, Ohad Shamir, Eldad Peretz, Shahar Lewkowicz, Tomer Epshtein,
  Or Vardi, Omri Porat

Program Committee

SODA 2025 (Chair) SPAA 2021 (Chair), HALG 2020 (Chair), ESA 2018 (Chair), ESA 2006 (Chair)
SPAA 2024, SODA 2024, SWAT 2022, FOCS 2021, ICALP 2021, SODA 2020,
ICALP 2019, FSTTCS 2018, ESA 2017, IPDPS 2017, WAOA 2017,
SPAA 2016, COCOON 2016, COCOON 2015, OLA 2014, COCOON 2014,
COCOON 2013, APPROX 2012, FSTTCS 2011, WAOA 2008, FOCS 2008,
ESA 2008, ICALP 2007, ESCAPE 2007, SODA 2006, SODA 2005,
WAOA 2004, APPROX 2003, WEA 2001, ESA 2000, RANDOM 2000.

Journal Editor Board

• ALGORITHMICA

• Advanced Algorithms Seminar

• Online and Approximation Algorithms 0368.4041
• Algorithmic Methods 0368.4139

Other Courses

• Algorithms - 0368.2160
• Algorithmic Game Theory Seminar - 0368.3354

DBLP List of publications

• DBLP List of publications
  

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.