dblp.uni-trier.dewww.uni-trier.de

Guy Kortsarz Vis

List of publications from the DBLP Bibliography Server - FAQ
Coauthor Index - Ask others: ACM DL/Guide - CiteSeerX - CSB - MetaPress - Google - Bing - Yahoo

*2009
96EEGuy Kortsarz, Zeev Nutov: Approximating Some Network Design Problems with Node Costs. APPROX-RANDOM 2009: 231-243
95EEMoran Feldman, Guy Kortsarz, Zeev Nutov: Improved approximating algorithms for Directed Steiner Forest. SODA 2009: 922-931
94EEGuy Even, Jon Feldman, Guy Kortsarz, Zeev Nutov: A 1.8 approximation algorithm for augmenting edge-connectivity of a graph from 1 to 2. ACM Transactions on Algorithms 5(2): (2009)
93EEMohammad Taghi Hajiaghayi, Guy Kortsarz, Mohammad R. Salavatipour: Approximating Buy-at-Bulk and Shallow-Light k-Steiner Trees. Algorithmica 53(1): 89-103 (2009)
92EEGuy Kortsarz, Zeev Nutov: Approximating minimum-power edge-covers and 2, 3-connectivity. Discrete Applied Mathematics 157(8): 1840-1847 (2009)
2008
91EEGuy Kortsarz, Michael Langberg, Zeev Nutov: Approximating Maximum Subgraphs without Short Cycles. APPROX-RANDOM 2008: 118-131
90EERohit Khandekar, Guy Kortsarz, Vahab S. Mirrokni, Mohammad R. Salavatipour: Two-Stage Robust Network Design with Exponential Scenarios. ESA 2008: 589-600
89EEMagnús M. Halldórsson, Guy Kortsarz, Maxim Sviridenko: Min Sum Edge Coloring in Multigraphs Via Configuration LP. IPCO 2008: 359-373
88EEGuy Kortsarz, Vahab S. Mirrokni, Zeev Nutov, Elena Tsanko: Approximating Minimum-Power Degree and Connectivity Problems. LATIN 2008: 423-435
87EERajiv Gandhi, Magnús M. Halldórsson, Guy Kortsarz, Hadas Shachnai: Improved bounds for scheduling conflicting jobs with minsum criteria. ACM Transactions on Algorithms 4(1): (2008)
86EEGuy Kortsarz, Zeev Nutov: Tight approximation algorithm for connectivity augmentation problems. J. Comput. Syst. Sci. 74(5): 662-670 (2008)
85EEGuy Kortsarz, Zeev Nutov: A note on two source location problems. J. Discrete Algorithms 6(3): 520-525 (2008)
2007
84EEChandra Chekuri, Mohammad Taghi Hajiaghayi, Guy Kortsarz, Mohammad R. Salavatipour: Approximation algorithms for node-weighted buy-at-bulk network design. SODA 2007: 1265-1274
83EEMichael Elkin, Guy Kortsarz: An improved algorithm for radio broadcast. ACM Transactions on Algorithms 3(1): (2007)
82EELuca Di Gaspero, Johannes Gärtner, Guy Kortsarz, Nysret Musliu, Andrea Schaerf, Wolfgang Slany: The minimum shift design problem. Annals OR 155(1): 79-105 (2007)
81EEGuy Kortsarz: A Lower Bound for Approximating Grundy Numbering. Discrete Mathematics & Theoretical Computer Science 9(1): (2007)
80EESharon Feldman, Guy Kortsarz, Zeev Nutov: Improved approximation algorithms for directed Steiner forest. Electronic Colloquium on Computational Complexity (ECCC) 14(120): (2007)
79EEMohammad Taghi Hajiaghayi, Guy Kortsarz, Vahab S. Mirrokni, Zeev Nutov: Power optimization for connectivity problems. Math. Program. 110(1): 195-208 (2007)
78EEEran 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)
77EEGuy Kortsarz, Sunil M. Shende: An Improved Approximation of the Achromatic Number on Bipartite Graphs. SIAM J. Discrete Math. 21(2): 361-373 (2007)
2006
76EEMohammad Taghi Hajiaghayi, Guy Kortsarz, Mohammad R. Salavatipour: Approximating Buy-at-Bulk and Shallow-Light k-Steiner Trees. APPROX-RANDOM 2006: 152-163
75EEChandra Chekuri, Mohammad Taghi Hajiaghayi, Guy Kortsarz, Mohammad R. Salavatipour: Approximation Algorithms for Non-Uniform Buy-at-Bulk Network Design. FOCS 2006: 677-686
74EEGuy Kortsarz, Zeev Nutov: Tight Approximation Algorithm for Connectivity Augmentation Problems. ICALP (1) 2006: 443-452
73EERajiv 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)
72EEMichael Elkin, Guy Kortsarz: An Approximation Algorithm for the Directed Telephone Multicast Problem. Algorithmica 45(4): 569-583 (2006)
71EEChandra Chekuri, Guy Even, Guy Kortsarz: A greedy approximation algorithm for the group Steiner problem. Discrete Applied Mathematics 154(1): 15-34 (2006)
70EEKurt Rohloff, Samir Khuller, Guy Kortsarz: Approximating the Minimal Sensor Selection for Supervisory Control. Discrete Event Dynamic Systems 16(1): 143-170 (2006)
69EEMohammad Taghi Hajiaghayi, Guy Kortsarz, Mohammad R. Salavatipour: Approximating Buy-at-Bulk k-Steiner trees Electronic Colloquium on Computational Complexity (ECCC)(007): (2006)
68EEMohammad 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)
67EERajiv 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)
66EEMichael Elkin, Guy Kortsarz: Sublogarithmic approximation for telephone multicast. J. Comput. Syst. Sci. 72(4): 648-659 (2006)
2005
65EEMohammad Taghi Hajiaghayi, Guy Kortsarz, Vahab S. Mirrokni, Zeev Nutov: Power Optimization for Connectivity Problems. IPCO 2005: 349-361
64EEMichael Elkin, Guy Kortsarz: Improved schedule for radio broadcast. SODA 2005: 222-231
63EEGuy Kortsarz, Jaikumar Radhakrishnan, Sivaramakrishnan Sivasubramanian: Complete partitions of graphs. SODA 2005: 860-869
62EEGuy 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)
61EEJulia 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)
60EEYana Kortsarts, Guy Kortsarz, Zeev Nutov: Greedy approximation algorithms for directed multicuts. Networks 45(4): 214-217 (2005)
59EEGuy Kortsarz, Zeev Nutov: Approximating k-node Connected Subgraphs via Critical Graphs. SIAM J. Comput. 35(1): 247-257 (2005)
58EEMichael Elkin, Guy Kortsarz: A Combinatorial Logarithmic Approximation Algorithm for the Directed Telephone Broadcast Problem. SIAM J. Comput. 35(3): 672-689 (2005)
57EEMichael Elkin, Guy Kortsarz: Polylogarithmic Additive Inapproximability of the Radio Broadcast Problem. SIAM J. Discrete Math. 19(4): 881-899 (2005)
2004
56EEMichael Elkin, Guy Kortsarz: Polylogarithmic Inapproximability of the Radio Broadcast Problem. APPROX-RANDOM 2004: 105-116
55EERajiv Gandhi, Magnús M. Halldórsson, Guy Kortsarz, Hadas Shachnai: Improved Results for Data Migration and Open Shop Scheduling. ICALP 2004: 658-669
54EEMagnús M. Halldórsson, Guy Kortsarz: Multicoloring: Problems and Techniques. MFCS 2004: 25-41
53EEGuy Kortsarz, Zeev Nutov: Approximation algorithm for k-node connected subgraphs via critical graphs. STOC 2004: 138-145
52EEJulia Chuzhoy, Sudipto Guha, Eran Halperin, Sanjeev Khanna, Guy Kortsarz, Joseph Naor: Asymmetric k-center is log* n-hard to approximate. STOC 2004: 21-27
51EEYana Kortsarts, Guy Kortsarz, Zeev Nutov: Approximation Algorithm for Directed Multicuts. WAOA 2004: 61-67
50EERajiv 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
49EEMichael Elkin, Guy Kortsarz: Logarithmic inapproximability of the radio broadcast problem. J. Algorithms 52(1): 8-25 (2004)
48EEGuy Kortsarz, Robert Krauthgamer, James R. Lee: Hardness of Approximation for Vertex-Connectivity Network Design Problems. SIAM J. Comput. 33(3): 704-720 (2004)
2003
47EEGuy Kortsarz, Sunil M. Shende: Approximating the Achromatic Number Problem on Bipartite Graphs. ESA 2003: 385-396
46EELuca 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
45EERajiv Gandhi, Eran Halperin, Samir Khuller, Guy Kortsarz, Aravind Srinivasan: An Improved Approximation Algorithm for Vertex Cover with Hard Capacities. ICALP 2003: 164-175
44EEMichael Elkin, Guy Kortsarz: Approximation Algorithm for Directed Telephone Multicast Problem. ICALP 2003: 212-223
43EEEran Halperin, Guy Kortsarz, Robert Krauthgamer, Aravind Srinivasan, Nan Wang: Integrality ratio for group Steiner trees and directed steiner trees. SODA 2003: 275-284
42EEMichael Elkin, Guy Kortsarz: Sublogarithmic approximation for telephone multicast: path out of jungle. SODA 2003: 76-85
41EEGuy Kortsarz, Zeev Nutov: Approximating Node Connectivity Problems via Set Covers. Algorithmica 37(2): 75-92 (2003)
40EEMagnú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)
39EEEran Halperin, Guy Kortsarz, Robert Krauthgamer: Tight lower bounds for the asymmetric k-center problem Electronic Colloquium on Computational Complexity (ECCC) 10(035): (2003)
38EEMagnú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
37EEGuy Kortsarz, Robert Krauthgamer, James R. Lee: Hardness of Approximation for Vertex-Connectivity Network-Design Problems. APPROX 2002: 185-199
36EEGuy Even, Guy Kortsarz: An approximation algorithm for the group Steiner problem. SODA 2002: 49-58
35EEMichael Elkin, Guy Kortsarz: Combinatorial logarithmic approximation algorithm for directed telephone broadcast problem. STOC 2002: 438-447
34EEGuy Even, Guy Kortsarz, Wolfgang Slany: On Network Design Problems: Fixed Cost Flows and the Covering Steiner Problem. SWAT 2002: 318-327
33EEMagnú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)
32EEUriel Feige, Magnús M. Halldórsson, Guy Kortsarz, Aravind Srinivasan: Approximating the Domatic Number. SIAM J. Comput. 32(1): 172-195 (2002)
2001
31EEMagnús M. Halldórsson, Guy Kortsarz, Hadas Shachnai: Minimizing Average Completion of Dedicated Tasks and Interval Graphs. RANDOM-APPROX 2001: 114-126
30EEGuy 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
29EEGuy Kortsarz, Robert Krauthgamer: On approximating the achromatic number. SODA 2001: 309-318
28EEUriel Feige, David Peleg, Guy Kortsarz: The Dense k-Subgraph Problem. Algorithmica 29(3): 410-421 (2001)
27EEGuy Kortsarz: On the Hardness of Approximating Spanners. Algorithmica 30(3): 432-450 (2001)
26EEGuy Kortsarz, Robert Krauthgamer: On Approximating the Achromatic Number. SIAM J. Discrete Math. 14(3): 408-422 (2001)
25EEJudit Bar-Ilan, Guy Kortsarz, David Peleg: Generalized submodular cover problems and applications. Theor. Comput. Sci. 250(1-2): 179-200 (2001)
2000
24EEGuy Kortsarz, Zeev Nutov: Approximating node connectivity problems via set covers. APPROX 2000: 194-205
23EEUriel Feige, Magnús M. Halldórsson, Guy Kortsarz: Approximating the domatic number. STOC 2000: 134-143
22EEDagmar 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
20EEMagnús M. Halldórsson, Guy Kortsarz, Andrzej Proskurowski, Ravit Salman, Hadas Shachnai, Jan Arne Telle: Multi-coloring Trees. COCOON 1999: 271-280
19EEAmotz 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
17EEGuy Kortsarz, David Peleg: Approximating the Weight of Shallow Steiner Trees. Discrete Applied Mathematics 93(2-3): 265-285 (1999)
16EEAmotz 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
15EEGuy 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)
13EEGuy Kortsarz, David Peleg: Generating Low-Degree 2-Spanners. SIAM J. Comput. 27(5): 1438-1456 (1998)
1997
12EEAmotz 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
9EEGuy 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
3EEGuy Kortsarz, David Peleg: Approximation Algorithms for Minimum Time Broadcast. ISTCS 1992: 67-78
2EEGuy Kortsarz, David Peleg: Generating Sparse 2-spanners. SWAT 1992: 73-82
1EEGuy Kortsarz, David Peleg: Traffic-Light Scheduling on the Grid (Extended Abstract). WDAG 1992: 238-252

Coauthor Index

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

Colors in the list of coauthors

Copyright © Tue Nov 3 08:52:44 2009 by Michael Ley (ley@uni-trier.de)