Guy Kortsarz

2007
79	EE	Chandra Chekuri, Mohammad Taghi Hajiaghayi, Guy Kortsarz, Mohammad R. Salavatipour: Approximation algorithms for node-weighted buy-at-bulk network design. SODA 2007: 1265-1274
78	EE	Michael Elkin, Guy Kortsarz: An improved algorithm for radio broadcast. ACM Transactions on Algorithms 3(1): (2007)
77	EE	Mohammad Taghi Hajiaghayi, Guy Kortsarz, Vahab S. Mirrokni, Zeev Nutov: Power optimization for connectivity problems. Math. Program. 110(1): 195-208 (2007)
76	EE	Eran Halperin, Guy Kortsarz, Robert Krauthgamer, Aravind Srinivasan, Nan Wang: Integrality Ratio for Group Steiner Trees and Directed Steiner Trees. SIAM J. Comput. 36(5): 1494-1511 (2007)
2006
75	EE	Mohammad Taghi Hajiaghayi, Guy Kortsarz, Mohammad R. Salavatipour: Approximating Buy-at-Bulk and Shallow-Light k-Steiner Trees. APPROX-RANDOM 2006: 152-163
74	EE	Chandra Chekuri, Mohammad Taghi Hajiaghayi, Guy Kortsarz, Mohammad R. Salavatipour: Approximation Algorithms for Non-Uniform Buy-at-Bulk Network Design. FOCS 2006: 677-686
73	EE	Guy Kortsarz, Zeev Nutov: Tight Approximation Algorithm for Connectivity Augmentation Problems. ICALP (1) 2006: 443-452
72	EE	Rajiv Gandhi, Magnús M. Halldórsson, Guy Kortsarz, Hadas Shachnai: Improved results for data migration and open shop scheduling. ACM Transactions on Algorithms 2(1): 116-129 (2006)
71	EE	Michael Elkin, Guy Kortsarz: An Approximation Algorithm for the Directed Telephone Multicast Problem. Algorithmica 45(4): 569-583 (2006)
70	EE	Chandra Chekuri, Guy Even, Guy Kortsarz: A greedy approximation algorithm for the group Steiner problem. Discrete Applied Mathematics 154(1): 15-34 (2006)
69	EE	Mohammad Taghi Hajiaghayi, Guy Kortsarz, Mohammad R. Salavatipour: Approximating Buy-at-Bulk k-Steiner trees Electronic Colloquium on Computational Complexity (ECCC)(007): (2006)
68	EE	Mohammad Taghi Hajiaghayi, Guy Kortsarz, Mohammad R. Salavatipour: Polylogarithmic Approximation Algorithm for Non-Uniform Multicommodity Buy-at-Bulk Electronic Colloquium on Computational Complexity (ECCC)(008): (2006)
67	EE	Rajiv Gandhi, Eran Halperin, Samir Khuller, Guy Kortsarz, Aravind Srinivasan: An improved approximation algorithm for vertex cover with hard capacities. J. Comput. Syst. Sci. 72(1): 16-33 (2006)
66	EE	Michael Elkin, Guy Kortsarz: Sublogarithmic approximation for telephone multicast. J. Comput. Syst. Sci. 72(4): 648-659 (2006)
2005
65	EE	Mohammad Taghi Hajiaghayi, Guy Kortsarz, Vahab S. Mirrokni, Zeev Nutov: Power Optimization for Connectivity Problems. IPCO 2005: 349-361
64	EE	Michael Elkin, Guy Kortsarz: Improved schedule for radio broadcast. SODA 2005: 222-231
63	EE	Guy Kortsarz, Jaikumar Radhakrishnan, Sivaramakrishnan Sivasubramanian: Complete partitions of graphs. SODA 2005: 860-869
62	EE	Guy Even, Guy Kortsarz, Wolfgang Slany: On network design problems: fixed cost flows and the covering steiner problem. ACM Transactions on Algorithms 1(1): 74-101 (2005)
61	EE	Julia Chuzhoy, Sudipto Guha, Eran Halperin, Sanjeev Khanna, Guy Kortsarz, Robert Krauthgamer, Joseph Naor: Asymmetric k-center is log* n-hard to approximate. J. ACM 52(4): 538-551 (2005)
60	EE	Yana Kortsarts, Guy Kortsarz, Zeev Nutov: Greedy approximation algorithms for directed multicuts. Networks 45(4): 214-217 (2005)
59	EE	Guy Kortsarz, Zeev Nutov: Approximating k-node Connected Subgraphs via Critical Graphs. SIAM J. Comput. 35(1): 247-257 (2005)
58	EE	Michael Elkin, Guy Kortsarz: A Combinatorial Logarithmic Approximation Algorithm for the Directed Telephone Broadcast Problem. SIAM J. Comput. 35(3): 672-689 (2005)
57	EE	Michael Elkin, Guy Kortsarz: Polylogarithmic Additive Inapproximability of the Radio Broadcast Problem. SIAM J. Discrete Math. 19(4): 881-899 (2005)
2004
56	EE	Michael Elkin, Guy Kortsarz: Polylogarithmic Inapproximability of the Radio Broadcast Problem. APPROX-RANDOM 2004: 105-116
55	EE	Rajiv Gandhi, Magnús M. Halldórsson, Guy Kortsarz, Hadas Shachnai: Improved Results for Data Migration and Open Shop Scheduling. ICALP 2004: 658-669
54	EE	Magnús M. Halldórsson, Guy Kortsarz: Multicoloring: Problems and Techniques. MFCS 2004: 25-41
53	EE	Guy Kortsarz, Zeev Nutov: Approximation algorithm for k-node connected subgraphs via critical graphs. STOC 2004: 138-145
52	EE	Julia Chuzhoy, Sudipto Guha, Eran Halperin, Sanjeev Khanna, Guy Kortsarz, Joseph Naor: Asymmetric k-center is log* n-hard to approximate. STOC 2004: 21-27
51	EE	Yana Kortsarts, Guy Kortsarz, Zeev Nutov: Approximation Algorithm for Directed Multicuts. WAOA 2004: 61-67
50	EE	Rajiv Gandhi, Magnús M. Halldórsson, Guy Kortsarz, Hadas Shachnai: Improved Bounds for Sum Multicoloring and Scheduling Dependent Jobs with Minsum Criteria. WAOA 2004: 68-82
49	EE	Michael Elkin, Guy Kortsarz: Logarithmic inapproximability of the radio broadcast problem. J. Algorithms 52(1): 8-25 (2004)
48	EE	Guy Kortsarz, Robert Krauthgamer, James R. Lee: Hardness of Approximation for Vertex-Connectivity Network Design Problems. SIAM J. Comput. 33(3): 704-720 (2004)
2003
47	EE	Guy Kortsarz, Sunil M. Shende: Approximating the Achromatic Number Problem on Bipartite Graphs. ESA 2003: 385-396
46	EE	Luca Di Gaspero, Johannes Gärtner, Guy Kortsarz, Nysret Musliu, Andrea Schaerf, Wolfgang Slany: The Minimum Shift Design Problem: Theory and Practice. ESA 2003: 593-604
45	EE	Rajiv Gandhi, Eran Halperin, Samir Khuller, Guy Kortsarz, Aravind Srinivasan: An Improved Approximation Algorithm for Vertex Cover with Hard Capacities. ICALP 2003: 164-175
44	EE	Michael Elkin, Guy Kortsarz: Approximation Algorithm for Directed Telephone Multicast Problem. ICALP 2003: 212-223
43	EE	Eran Halperin, Guy Kortsarz, Robert Krauthgamer, Aravind Srinivasan, Nan Wang: Integrality ratio for group Steiner trees and directed steiner trees. SODA 2003: 275-284
42	EE	Michael Elkin, Guy Kortsarz: Sublogarithmic approximation for telephone multicast: path out of jungle. SODA 2003: 76-85
41	EE	Guy Kortsarz, Zeev Nutov: Approximating Node Connectivity Problems via Set Covers. Algorithmica 37(2): 75-92 (2003)
40	EE	Magnús M. Halldórsson, Guy Kortsarz, Hadas Shachnai: Sum Coloring Interval and k-Claw Free Graphs with Application to Scheduling Dependent Jobs. Algorithmica 37(3): 187-209 (2003)
39	EE	Eran Halperin, Guy Kortsarz, Robert Krauthgamer: Tight lower bounds for the asymmetric k-center problem Electronic Colloquium on Computational Complexity (ECCC) 10(035): (2003)
38	EE	Magnús M. Halldórsson, Guy Kortsarz, Andrzej Proskurowski, Ravit Salman, Hadas Shachnai, Jan Arne Telle: Multicoloring trees. Inf. Comput. 180(2): 113-129 (2003)
2002
37	EE	Guy Kortsarz, Robert Krauthgamer, James R. Lee: Hardness of Approximation for Vertex-Connectivity Network-Design Problems. APPROX 2002: 185-199
36	EE	Guy Even, Guy Kortsarz: An approximation algorithm for the group Steiner problem. SODA 2002: 49-58
35	EE	Michael Elkin, Guy Kortsarz: Combinatorial logarithmic approximation algorithm for directed telephone broadcast problem. STOC 2002: 438-447
34	EE	Guy Even, Guy Kortsarz, Wolfgang Slany: On Network Design Problems: Fixed Cost Flows and the Covering Steiner Problem. SWAT 2002: 318-327
33	EE	Magnús M. Halldórsson, Guy Kortsarz: Tools for Multicoloring with Applications to Planar Graphs and Partial k-Trees. J. Algorithms 42(2): 334-366 (2002)
32	EE	Uriel Feige, Magnús M. Halldórsson, Guy Kortsarz, Aravind Srinivasan: Approximating the Domatic Number. SIAM J. Comput. 32(1): 172-195 (2002)
2001
31	EE	Magnús M. Halldórsson, Guy Kortsarz, Hadas Shachnai: Minimizing Average Completion of Dedicated Tasks and Interval Graphs. RANDOM-APPROX 2001: 114-126
30	EE	Guy Even, Jon Feldman, Guy Kortsarz, Zeev Nutov: A 3/2-Approximation Algorithm for Augmenting the Edge-Connectivity of a Graph from 1 to 2 Using a Subset of a Given Edge Set. RANDOM-APPROX 2001: 90-101
29	EE	Guy Kortsarz, Robert Krauthgamer: On approximating the achromatic number. SODA 2001: 309-318
28	EE	Uriel Feige, David Peleg, Guy Kortsarz: The Dense k-Subgraph Problem. Algorithmica 29(3): 410-421 (2001)
27	EE	Guy Kortsarz: On the Hardness of Approximating Spanners. Algorithmica 30(3): 432-450 (2001)
26	EE	Guy Kortsarz, Robert Krauthgamer: On Approximating the Achromatic Number. SIAM J. Discrete Math. 14(3): 408-422 (2001)
25	EE	Judit Bar-Ilan, Guy Kortsarz, David Peleg: Generalized submodular cover problems and applications. Theor. Comput. Sci. 250(1-2): 179-200 (2001)
2000
24	EE	Guy Kortsarz, Zeev Nutov: Approximating node connectivity problems via set covers. APPROX 2000: 194-205
23	EE	Uriel Feige, Magnús M. Halldórsson, Guy Kortsarz: Approximating the domatic number. STOC 2000: 134-143
22	EE	Dagmar Handke, Guy Kortsarz: Tree Spanners for Subgraphs and Related Tree Covering Problems. WG 2000: 206-217
21		Amotz Bar-Noy, Magnús M. Halldórsson, Guy Kortsarz, Ravit Salman, Hadas Shachnai: Sum Multicoloring of Graphs. J. Algorithms 37(2): 422-450 (2000)
1999
20	EE	Magnús M. Halldórsson, Guy Kortsarz, Andrzej Proskurowski, Ravit Salman, Hadas Shachnai, Jan Arne Telle: Multi-coloring Trees. COCOON 1999: 271-280
19	EE	Amotz Bar-Noy, Magnús M. Halldórsson, Guy Kortsarz, Ravit Salman, Hadas Shachnai: Sum Multi-coloring of Graphs. ESA 1999: 390-401
18		Magnús M. Halldórsson, Guy Kortsarz: Multicoloring Planar Graphs and Partial k-Trees. RANDOM-APPROX 1999: 73-84
17	EE	Guy Kortsarz, David Peleg: Approximating the Weight of Shallow Steiner Trees. Discrete Applied Mathematics 93(2-3): 265-285 (1999)
16	EE	Amotz Bar-Noy, Magnús M. Halldórsson, Guy Kortsarz: A Matched Approximation Bound for the Sum of a Greedy Coloring. Inf. Process. Lett. 71(3-4): 135-140 (1999)
1998
15	EE	Guy Kortsarz: On the Hardness of Approximation Spanners. APPROX 1998: 135-146
14		Amotz Bar-Noy, Guy Kortsarz: Minimum Color Sum of Bipartite Graphs. J. Algorithms 28(2): 339-365 (1998)
13	EE	Guy Kortsarz, David Peleg: Generating Low-Degree 2-Spanners. SIAM J. Comput. 27(5): 1438-1456 (1998)
1997
12		Amotz Bar-Noy, Guy Kortsarz: The Minimum Color Sum of Bipartite Graphs. ICALP 1997: 738-748
11		Guy Kortsarz, David Peleg: Approximating Shallow-Light Trees (Extended Abstract). SODA 1997: 103-110
1996
10		Judit Bar-Ilan, Guy Kortsarz, David Peleg: Generalized Submodular Cover Problems and Applications. ISTCS 1996: 110-118
1995
9	EE	Guy Kortsarz, David Peleg: Approximation Algorithms for Minimum-Time Broadcast. SIAM J. Discrete Math. 8(3): 401-427 (1995)
1994
8		Guy Kortsarz, David Peleg: Generating Low-Degree 2-Spanners. SODA 1994: 556-563
7		Guy Kortsarz, David Peleg: Traffic-light scheduling on the grid. Discrete Applied Mathematics 53(1-3): 211-234 (1994)
6		Guy Kortsarz, David Peleg: Generating Sparse 2-Spanners. J. Algorithms 17(2): 222-236 (1994)
1993
5		Guy Kortsarz, David Peleg: On Choosing a Dense Subgraph (Extended Abstract) FOCS 1993: 692-701
4		Judit Bar-Ilan, Guy Kortsarz, David Peleg: How to Allocate Network Centers. J. Algorithms 15(3): 385-415 (1993)
1992
3		Guy Kortsarz, David Peleg: Approximation Algorithms for Minimum Time Broadcast. ISTCS 1992: 67-78
2		Guy Kortsarz, David Peleg: Generating Sparse 2-spanners. SWAT 1992: 73-82
1		Guy Kortsarz, David Peleg: Traffic-Light Scheduling on the Grid (Extended Abstract). WDAG 1992: 238-252

Coauthor Index

1	Judit Bar-Ilan	[4] [10] [25]
2	Amotz Bar-Noy	[12] [14] [16] [19] [21]
3	Chandra Chekuri	[70] [74] [79]
4	Julia Chuzhoy	[52] [61]
5	Michael Elkin	[35] [42] [44] [49] [56] [57] [58] [64] [66] [71] [78]
6	Guy Even	[30] [34] [36] [62] [70]
7	Uriel Feige	[23] [28] [32]
8	Jon Feldman	[30]
9	Rajiv Gandhi	[45] [50] [55] [67] [72]
10	Johannes Gärtner	[46]
11	Luca Di Gaspero	[46]
12	Sudipto Guha	[52] [61]
13	Mohammad Taghi Hajiaghayi (MohammadTaghi Hajiaghayi)	[65] [68] [69] [74] [75] [77] [79]
14	Magnús M. Halldórsson	[16] [18] [19] [20] [21] [23] [31] [32] [33] [38] [40] [50] [54] [55] [72]
15	Eran Halperin	[39] [43] [45] [52] [61] [67] [76]
16	Dagmar Handke	[22]
17	Sanjeev Khanna	[52] [61]
18	Samir Khuller	[45] [67]
19	Yana Kortsarts	[51] [60]
20	Robert Krauthgamer	[26] [29] [37] [39] [43] [48] [61] [76]
21	James R. Lee	[37] [48]
22	Vahab S. Mirrokni (Seyed Vahab Mirrokni)	[65] [77]
23	Nysret Musliu	[46]
24	Joseph Naor (Seffi Naor)	[52] [61]
25	Zeev Nutov	[24] [30] [41] [51] [53] [59] [60] [65] [73] [77]
26	David Peleg	[1] [2] [3] [4] [5] [6] [7] [8] [9] [10] [11] [13] [17] [25] [28]
27	Andrzej Proskurowski	[20] [38]
28	Jaikumar Radhakrishnan	[63]
29	Mohammad R. Salavatipour	[68] [69] [74] [75] [79]
30	Ravit Salman	[19] [20] [21] [38]
31	Andrea Schaerf	[46]
32	Hadas Shachnai	[19] [20] [21] [31] [38] [40] [50] [55] [72]
33	Sunil M. Shende	[47]
34	Sivaramakrishnan Sivasubramanian	[63]
35	Wolfgang Slany	[34] [46] [62]
36	Aravind Srinivasan	[32] [43] [45] [67] [76]
37	Jan Arne Telle	[20] [38]
38	Nan Wang	[43] [76]

Colors in the list of coauthors