Yair Bartal

	2012
80		Yair Bartal, Lee-Ad Gottlieb, Robert Krauthgamer: The traveling salesman problem: low-dimensionality implies a polynomial time approximation scheme. STOC 2012: 663-672
	2011
79		Yair Bartal, Douglas E. Carroll, Adam Meyerson, Ofer Neiman: Bandwidth and Low Dimensional Embedding. APPROX-RANDOM 2011: 50-61
78		Yair Bartal, Lee-Ad Gottlieb, Tsvi Kopelowitz, Moshe Lewenstein, Liam Roditty: Fast, precise and dynamic distance queries. SODA 2011: 840-853
77		Yair Bartal, Ben Recht, Leonard J. Schulman: Dimensionality reduction: Beyond the Johnson-Lindenstrauss bound. SODA 2011: 868-887
76		Yair Bartal, Lee-Ad Gottlieb, Robert Krauthgamer: The Traveling Salesman Problem: Low-Dimensionality Implies a Polynomial Time Approximation Scheme CoRR abs/1112.0699: (2011)
	2010
75		Ittai Abraham, Yair Bartal, Ofer Neiman, Leonard J. Schulman: Volume in General Metric Spaces. ESA (2) 2010: 87-99
74		Yair Bartal, Lee-Ad Gottlieb, Tsvi Kopelowitz, Moshe Lewenstein, Liam Roditty: Fast, precise and dynamic distance queries CoRR abs/1008.1480: (2010)
	2009
73		Ittai Abraham, Yair Bartal, Ofer Neiman: On low dimensional local embeddings. SODA 2009: 875-884
72		Yair Bartal, Leonard J. Schulman: Universal Immersion Spaces for Edge-Colored Graphs and Nearest-Neighbor Metrics. SIAM J. Discrete Math. 23(2): 1110-1115 (2009)
	2008
71		Ittai Abraham, Yair Bartal, Ofer Neiman: Nearly Tight Low Stretch Spanning Trees. FOCS 2008: 781-790
70		Ittai Abraham, Yair Bartal, Ofer Neiman: Embedding metric spaces in their intrinsic dimension. SODA 2008: 363-372
69		Ittai Abraham, Yair Bartal, Ofer Neiman: Nearly Tight Low Stretch Spanning Trees CoRR abs/0808.2017: (2008)
	2007
68		Ittai Abraham, Yair Bartal, Ofer Neiman: Embedding metrics into ultrametrics and graphs into spanning trees with constant average distortion. SODA 2007: 502-511
67		Ittai Abraham, Yair Bartal, Ofer Neiman: Local embeddings of metric spaces. STOC 2007: 631-640
	2006
66		Yair Bartal, Stefano Leonardi, Gil Shallom, René Sitters: On the Value of Preemption in Scheduling. APPROX-RANDOM 2006: 39-48
65		Ittai Abraham, Yair Bartal, Ofer Neiman: Advances in metric embedding theory. STOC 2006: 271-286
64		Ittai Abraham, Yair Bartal, Ofer Neiman: Embedding Metrics into Ultrametrics and Graphs into Spanning Trees with Constant Average Distortion CoRR abs/cs/0610003: (2006)
63		Yair Bartal, Béla Bollobás, Manor Mendel: Ramsey-type theorems for metric spaces with applications to online problems. J. Comput. Syst. Sci. 72(5): 890-921 (2006)
62		Yair Bartal, Amos Fiat, Stefano Leonardi: Lower Bounds for On-line Graph Problems with Application to On-line Circuit and Optical Routing. SIAM J. Comput. 36(2): 354-393 (2006)
	2005
61		Ittai Abraham, Yair Bartal, Hubert T.-H. Chan, Kedar Dhamdhere, Anupam Gupta, Jon M. Kleinberg, Ofer Neiman, Aleksandrs Slivkins: Metric Embeddings with Relaxed Guarantees. FOCS 2005: 83-100
60		Yair Bartal, Nathan Linial, Manor Mendel, Assaf Naor: Some Low Distortion Metric Ramsey Problems. Discrete & Computational Geometry 33(1): 27-41 (2005)
59		Yair Bartal, Manor Mendel: Randomized k-server algorithms for growth-rate bounded graphs. J. Algorithms 55(2): 192-202 (2005)
	2004
58		Yair Bartal, Rica Gonen, Pierfrancesco La Mura: Negotiation-range mechanisms: exploring the limits of truthful efficient markets. ACM Conference on Electronic Commerce 2004: 1-8
57		Yair Bartal: Graph Decomposition Lemmas and Their Role in Metric Embedding Methods. ESA 2004: 89-97
56		Yair Bartal, Manor Mendel: Dimension reduction for ultrametrics. SODA 2004: 664-665
55		Yair Bartal, Manor Mendel: Randomized k-server algorithms for growth-rate bounded graphs. SODA 2004: 666-671
54		Yair Bartal, Francis Y. L. Chin, Marek Chrobak, Stanley P. Y. Fung, Wojciech Jawor, Ron Lavi, Jiri Sgall, Tomás Tichý: Online Competitive Algorithms for Maximizing Weighted Throughput of Unit Jobs. STACS 2004: 187-198
53		Yair Bartal, Alain J. Mayer, Kobbi Nissim, Avishai Wool: Firmato: A novel firewall management toolkit. ACM Trans. Comput. Syst. 22(4): 381-420 (2004)
52		Yair Bartal, Béla Bollobás, Manor Mendel: Ramsey-type theorems for metric spaces with applications to online problems CoRR cs.DS/0406028: (2004)
51		Yair Bartal, Manor Mendel: Randomized k-server algorithms for growth-rate bounded graphs CoRR cs.DS/0406033: (2004)
50		Yair Bartal, Manor Mendel: Multi-Embedding of Metric Spaces CoRR cs.DS/0408003: (2004)
49		Yair Bartal, Nathan Linial, Manor Mendel, Assaf Naor: Low dimensional embeddings of ultrametrics. Eur. J. Comb. 25(1): 87-92 (2004)
48		Yair Bartal, John W. Byers, Danny Raz: Fast, Distributed Approximation Algorithms for Positive Linear Programming with Applications to Flow Control. SIAM J. Comput. 33(6): 1261-1279 (2004)
47		Yair Bartal, Manor Mendel: Multiembedding of Metric Spaces. SIAM J. Comput. 34(1): 248-259 (2004)
46		Baruch Awerbuch, Yossi Azar, Yair Bartal: On-line generalized Steiner problem. Theor. Comput. Sci. 324(2-3): 313-324 (2004)
45		Yair Bartal, Elias Koutsoupias: On the competitive ratio of the work function algorithm for the k-server problem. Theor. Comput. Sci. 324(2-3): 337-345 (2004)
	2003
44		Ittai Abraham, Baruch Awerbuch, Yossi Azar, Yair Bartal, Dahlia Malkhi, Elan Pavlov: A Generic Scheme for Building Overlay Networks in Adversarial Scenarios. IPDPS 2003: 40
43		Yair Bartal, Manor Mendel: Multi-embedding and path approximation of metric spaces. SODA 2003: 424-433
42		Yair Bartal, Nathan Linial, Manor Mendel, Assaf Naor: On metric ramsey-type phenomena. STOC 2003: 463-472
41		Yair Bartal, Rica Gonen, Noam Nisan: Incentive compatible multi unit combinatorial auctions. TARK 2003: 72-87
40		Baruch Awerbuch, Yair Bartal, Amos Fiat: Competitive distributed file allocation. Inf. Comput. 185(1): 1-40 (2003)
	2002
39		Yair Bartal, Martin Farach-Colton, Shibu Yooseph, Lisa Zhang: Fast, Fair and Frugal Bandwidth Allocation in ATM Networks. Algorithmica 33(3): 272-286 (2002)
38		Yair Bartal, Marek Chrobak, John Noga, Prabhakar Raghavan: More on random walks, electrical networks, and the harmonic k-server algorithm. Inf. Process. Lett. 84(5): 271-276 (2002)
	2001
37		Yair Bartal, Béla Bollobás, Manor Mendel: A Ramsy-type Theorem for Metric Spaces and its Applications for Metrical Task Systems and Related Problems. FOCS 2001: 396-405
36		Yair Bartal, Moses Charikar, Danny Raz: Approximating min-sum k-clustering in metric spaces. STOC 2001: 11-20
35		Yair Bartal, Moses Charikar, Piotr Indyk: On page migration and other relaxed task systems. Theor. Comput. Sci. 268(1): 43-66 (2001)
	2000
34		Yair Bartal, S. Muthukrishnan: Minimizing maximum response time in scheduling broadcasts. SODA 2000: 558-559
33		Yair Bartal, Elias Koutsoupias: On the Competitive Ratio of the Work Function Algorithm for the k-Server Problem. STACS 2000: 605-613
32		Yair Bartal, Marek Chrobak, Lawrence L. Larmore: A Randomized Algorithm for Two Servers on the Line. Inf. Comput. 158(1): 53-69 (2000)
31		Yair Bartal, Eddie Grove: The harmonic k-server algorithm is competitive. J. ACM 47(1): 1-15 (2000)
30		Yair Bartal, Stefano Leonardi, Alberto Marchetti-Spaccamela, Jiri Sgall, Leen Stougie: Multiprocessor Scheduling with Rejection. SIAM J. Discrete Math. 13(1): 64-78 (2000)
	1999
29		Yair Bartal, Alain J. Mayer, Kobbi Nissim, Avishai Wool: Firmato: A Novel Firewall Management Toolkit. IEEE Symposium on Security and Privacy 1999: 17-31
28		Yair Bartal, Martin Farach-Colton, Shibu Yooseph, Lisa Zhang: Fast, Fair, and Frugal Bandwidth Allocation in ATM Networks. SODA 1999: 92-101
27		Yossi Azar, Yair Bartal, Esteban Feuerstein, Amos Fiat, Stefano Leonardi, Adi Rosén: On Capital Investment. Algorithmica 25(1): 22-36 (1999)
26		Yair Bartal, Stefano Leonardi: On-Line Routing in All-Optical Networks. Theor. Comput. Sci. 221(1-2): 19-39 (1999)
	1998
25		Yair Bartal, Marek Chrobak, Lawrence L. Larmore: A Randomized Algorithm for Two Servers on the Line (Extended Abstract). ESA 1998: 247-258
24		Yair Bartal: On Approximating Arbitrary Metrices by Tree Metrics. STOC 1998: 161-168
23		Baruch Awerbuch, Yair Bartal, Amos Fiat: Distributed Paging for General Networks. J. Algorithms 28(1): 67-104 (1998)
	1997
22		Yair Bartal, John W. Byers, Danny Raz: Global Optimization Using Local Information with Applications to Flow Control. FOCS 1997: 303-312
21		Yair Bartal, Stefano Leonardi: On-Line Routing in All-Optical Networks. ICALP 1997: 516-526
20		Micah Adler, Yair Bartal, John W. Byers, Michael Luby, Danny Raz: A Modular Analysis of Network Transmission Protocols. ISTCS 1997: 54-62
19		Yair Bartal, Moses Charikar, Piotr Indyk: On Page Migration and Other Related Task Systems. SODA 1997: 43-52
18		Yair Bartal, Avrim Blum, Carl Burch, Andrew Tomkins: A polylog(n)-Competitive Algorithm for Metrical Task Systems. STOC 1997: 711-719
17		Yair Bartal, Adi Rosén: The Distributed k-Server Problem - A Competitive Distributed Translator for k-Server Algorithms. J. Algorithms 23(2): 241-264 (1997)
	1996
16		Yair Bartal: Probabilistic Approximations of Metric Spaces and Its Algorithmic Applications. FOCS 1996: 184-193
15		Yossi Azar, Yair Bartal, Esteban Feuerstein, Amos Fiat, Stefano Leonardi, Adi Rosén: On Capital Investment. ICALP 1996: 429-441
14		Yair Bartal: Distributed Paging. Online Algorithms 1996: 97-117
13		Baruch Awerbuch, Yair Bartal, Amos Fiat: Distributed Paging for General Networks. SODA 1996: 574-583
12		Baruch Awerbuch, Yossi Azar, Yair Bartal: On-line Generalized Steiner Problem. SODA 1996: 68-74
11		Yair Bartal, Stefano Leonardi, Alberto Marchetti-Spaccamela, Jiri Sgall, Leen Stougie: Multiprocessor Scheduling with Rejection. SODA 1996: 95-103
10		Yair Bartal, Amos Fiat, Stefano Leonardi: Lower Bounds for On-line Graph Problems with Application to On-line Circuit and Optical Routing. STOC 1996: 531-540
	1995
9		Yair Bartal, Amos Fiat, Yuval Rabani: Competitive Algorithms for Distributed Data Management. J. Comput. Syst. Sci. 51(3): 341-358 (1995)
8		Yair Bartal, Amos Fiat, Howard J. Karloff, Rakesh Vohra: New Algorithms for an Ancient Scheduling Problem. J. Comput. Syst. Sci. 51(3): 359-366 (1995)
	1994
7		Baruch Awerbuch, Yair Bartal, Amos Fiat, Adi Rosén: Competitive Non-Preemptive Call Control. SODA 1994: 312-320
6		Yair Bartal, Howard J. Karloff, Yuval Rabani: A Better Lower Bound for On-Line Scheduling. Inf. Process. Lett. 50(3): 113-116 (1994)
	1993
5		Baruch Awerbuch, Yair Bartal, Amos Fiat: Heat & Dump: Competitive Distributed Paging FOCS 1993: 22-31
4		Baruch Awerbuch, Yair Bartal, Amos Fiat: Competitive distributed file allocation. STOC 1993: 164-173
	1992
3		Yair Bartal, Adi Rosén: The Distributed k-Server Problem-A Competitive Distributed Translator for k-Server Algorithms FOCS 1992: 344-353
2		Yair Bartal, Amos Fiat, Yuval Rabani: Competitive Algorithms for Distributed Data Management (Extended Abstract) STOC 1992: 39-50
1		Yair Bartal, Amos Fiat, Howard J. Karloff, Rakesh Vohra: New Algorithms for an Ancient Scheduling Problem STOC 1992: 51-58

Coauthor Index

1	Ittai Abraham	[44] [61] [64] [65] [67] [68] [69] [70] [71] [73] [75]
2	Micah Adler	[20]
3	Baruch Awerbuch	[4] [5] [7] [12] [13] [23] [40] [44] [46]
4	Yossi Azar	[12] [15] [27] [44] [46]
5	Avrim Blum	[18]
6	Béla Bollobás	[37] [52] [63]
7	Carl Burch	[18]
8	John W. Byers	[20] [22] [48]
9	Douglas E. Carroll	[79]
10	T.-H. Hubert Chan (Hubert T.-H. Chan)	[61]
11	Moses Charikar	[19] [35] [36]
12	Francis Y. L. Chin (Francis Yuk-Lun Chin)	[54]
13	Marek Chrobak	[25] [32] [38] [54]
14	Kedar Dhamdhere	[61]
15	Martin Farach-Colton (Martin Farach)	[28] [39]
16	Esteban Feuerstein	[15] [27]
17	Amos Fiat	[1] [2] [4] [5] [7] [8] [9] [10] [13] [15] [23] [27] [40] [62]
18	Stanley P. Y. Fung	[54]
19	Rica Gonen	[41] [58]
20	Lee-Ad Gottlieb	[74] [76] [78] [80]
21	Eddie Grove	[31]
22	Anupam Gupta	[61]
23	Piotr Indyk	[19] [35]
24	Wojciech Jawor	[54]
25	Howard J. Karloff	[1] [6] [8]
26	Jon M. Kleinberg	[61]
27	Tsvi Kopelowitz	[74] [78]
28	Elias Koutsoupias	[33] [45]
29	Robert Krauthgamer	[76] [80]
30	Lawrence L. Larmore	[25] [32]
31	Ron Lavi	[54]
32	Stefano Leonardi	[10] [11] [15] [21] [26] [27] [30] [62] [66]
33	Moshe Lewenstein	[74] [78]
34	Nathan Linial (Nati Linial)	[42] [49] [60]
35	Michael Luby	[20]
36	Dahlia Malkhi (Dalia Malki)	[44]
37	Alberto Marchetti-Spaccamela	[11] [30]
38	Alain J. Mayer	[29] [53]
39	Manor Mendel	[37] [42] [43] [47] [49] [50] [51] [52] [55] [56] [59] [60] [63]
40	Adam Meyerson	[79]
41	Pierfrancesco La Mura	[58]
42	S. Muthukrishnan (S. Muthu Muthukrishnan)	[34]
43	Assaf Naor	[42] [49] [60]
44	Ofer Neiman	[61] [64] [65] [67] [68] [69] [70] [71] [73] [75] [79]
45	Noam Nisan	[41]
46	Kobbi Nissim	[29] [53]
47	John Noga	[38]
48	Elan Pavlov	[44]
49	Yuval Rabani	[2] [6] [9]
50	Prabhakar Raghavan	[38]
51	Danny Raz	[20] [22] [36] [48]
52	Ben Recht (Benjamin Recht)	[77]
53	Liam Roditty	[74] [78]
54	Adi Rosén	[3] [7] [15] [17] [27]
55	Leonard J. Schulman	[72] [75] [77]
56	Jiri Sgall	[11] [30] [54]
57	Gil Shallom	[66]
58	René Sitters (René A. Sitters)	[66]
59	Aleksandrs Slivkins	[61]
60	Leen Stougie	[11] [30]
61	Tomás Tichý	[54]
62	Andrew Tomkins	[18]
63	Rakesh V. Vohra (Rakesh Vohra)	[1] [8]
64	Avishai Wool	[29] [53]
65	Shibu Yooseph	[28] [39]
66	Lisa Zhang	[28] [39]

Colors in the list of coauthors

Last update Sun May 27 04:04:01 2012 CET by the DBLP Team — Data released under the ODC-BY 1.0 license — See also our legal information page