 | 2009 |
|---|
| 96 |       | Guy Kortsarz,
Zeev Nutov:
Approximating Some Network Design Problems with Node Costs.
APPROX-RANDOM 2009: 231-243 |
| 95 | | Moran Feldman,
Guy Kortsarz,
Zeev Nutov:
Improved approximating algorithms for Directed Steiner Forest.
SODA 2009: 922-931 |
| 94 | | Guy 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) |
| 93 | | Mohammad Taghi Hajiaghayi,
Guy Kortsarz,
Mohammad R. Salavatipour:
Approximating Buy-at-Bulk and Shallow-Light k-Steiner Trees.
Algorithmica 53(1): 89-103 (2009) |
| 92 | | Guy Kortsarz,
Zeev Nutov:
Approximating minimum-power edge-covers and 2, 3-connectivity.
Discrete Applied Mathematics 157(8): 1840-1847 (2009) |
| 2008 |
|---|
| 91 | | Guy Kortsarz,
Michael Langberg,
Zeev Nutov:
Approximating Maximum Subgraphs without Short Cycles.
APPROX-RANDOM 2008: 118-131 |
| 90 | | Rohit Khandekar,
Guy Kortsarz,
Vahab S. Mirrokni,
Mohammad R. Salavatipour:
Two-Stage Robust Network Design with Exponential Scenarios.
ESA 2008: 589-600 |
| 89 | | Magnús M. Halldórsson,
Guy Kortsarz,
Maxim Sviridenko:
Min Sum Edge Coloring in Multigraphs Via Configuration LP.
IPCO 2008: 359-373 |
| 88 | | Guy Kortsarz,
Vahab S. Mirrokni,
Zeev Nutov,
Elena Tsanko:
Approximating Minimum-Power Degree and Connectivity Problems.
LATIN 2008: 423-435 |
| 87 | | Rajiv 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) |
| 86 | | Guy Kortsarz,
Zeev Nutov:
Tight approximation algorithm for connectivity augmentation problems.
J. Comput. Syst. Sci. 74(5): 662-670 (2008) |
| 85 | | Guy Kortsarz,
Zeev Nutov:
A note on two source location problems.
J. Discrete Algorithms 6(3): 520-525 (2008) |
| 2007 |
|---|
| 84 | | Chandra Chekuri,
Mohammad Taghi Hajiaghayi,
Guy Kortsarz,
Mohammad R. Salavatipour:
Approximation algorithms for node-weighted buy-at-bulk network design.
SODA 2007: 1265-1274 |
| 83 | | Michael Elkin,
Guy Kortsarz:
An improved algorithm for radio broadcast.
ACM Transactions on Algorithms 3(1): (2007) |
| 82 | | Luca 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) |
| 81 | | Guy Kortsarz:
A Lower Bound for Approximating Grundy Numbering.
Discrete Mathematics & Theoretical Computer Science 9(1): (2007) |
| 80 | | Sharon Feldman,
Guy Kortsarz,
Zeev Nutov:
Improved approximation algorithms for directed Steiner forest.
Electronic Colloquium on Computational Complexity (ECCC) 14(120): (2007) |
| 79 | | Mohammad Taghi Hajiaghayi,
Guy Kortsarz,
Vahab S. Mirrokni,
Zeev Nutov:
Power optimization for connectivity problems.
Math. Program. 110(1): 195-208 (2007) |
| 78 | | 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) |
| 77 | | Guy Kortsarz,
Sunil M. Shende:
An Improved Approximation of the Achromatic Number on Bipartite Graphs.
SIAM J. Discrete Math. 21(2): 361-373 (2007) |
| 2006 |
|---|
| 76 | | Mohammad Taghi Hajiaghayi,
Guy Kortsarz,
Mohammad R. Salavatipour:
Approximating Buy-at-Bulk and Shallow-Light k-Steiner Trees.
APPROX-RANDOM 2006: 152-163 |
| 75 | | Chandra Chekuri,
Mohammad Taghi Hajiaghayi,
Guy Kortsarz,
Mohammad R. Salavatipour:
Approximation Algorithms for Non-Uniform Buy-at-Bulk Network Design.
FOCS 2006: 677-686 |
| 74 | | Guy Kortsarz,
Zeev Nutov:
Tight Approximation Algorithm for Connectivity Augmentation Problems.
ICALP (1) 2006: 443-452 |
| 73 | | 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) |
| 72 | | Michael Elkin,
Guy Kortsarz:
An Approximation Algorithm for the Directed Telephone Multicast Problem.
Algorithmica 45(4): 569-583 (2006) |
| 71 | | Chandra Chekuri,
Guy Even,
Guy Kortsarz:
A greedy approximation algorithm for the group Steiner problem.
Discrete Applied Mathematics 154(1): 15-34 (2006) |
| 70 | | Kurt Rohloff,
Samir Khuller,
Guy Kortsarz:
Approximating the Minimal Sensor Selection for Supervisory Control.
Discrete Event Dynamic Systems 16(1): 143-170 (2006) |
| 69 | | Mohammad Taghi Hajiaghayi,
Guy Kortsarz,
Mohammad R. Salavatipour:
Approximating Buy-at-Bulk k-Steiner trees
Electronic Colloquium on Computational Complexity (ECCC)(007): (2006) |
| 68 | | 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 | | 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 | | Michael Elkin,
Guy Kortsarz:
Sublogarithmic approximation for telephone multicast.
J. Comput. Syst. Sci. 72(4): 648-659 (2006) |
| 2005 |
|---|
| 65 | | Mohammad Taghi Hajiaghayi,
Guy Kortsarz,
Vahab S. Mirrokni,
Zeev Nutov:
Power Optimization for Connectivity Problems.
IPCO 2005: 349-361 |
| 64 | | Michael Elkin,
Guy Kortsarz:
Improved schedule for radio broadcast.
SODA 2005: 222-231 |
| 63 | | Guy Kortsarz,
Jaikumar Radhakrishnan,
Sivaramakrishnan Sivasubramanian:
Complete partitions of graphs.
SODA 2005: 860-869 |
| 62 | | 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 | | 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 | | Yana Kortsarts,
Guy Kortsarz,
Zeev Nutov:
Greedy approximation algorithms for directed multicuts.
Networks 45(4): 214-217 (2005) |
| 59 | | Guy Kortsarz,
Zeev Nutov:
Approximating k-node Connected Subgraphs via Critical Graphs.
SIAM J. Comput. 35(1): 247-257 (2005) |
| 58 | | Michael Elkin,
Guy Kortsarz:
A Combinatorial Logarithmic Approximation Algorithm for the Directed Telephone Broadcast Problem.
SIAM J. Comput. 35(3): 672-689 (2005) |
| 57 | | Michael Elkin,
Guy Kortsarz:
Polylogarithmic Additive Inapproximability of the Radio Broadcast Problem.
SIAM J. Discrete Math. 19(4): 881-899 (2005) |
| 2004 |
|---|
| 56 | | Michael Elkin,
Guy Kortsarz:
Polylogarithmic Inapproximability of the Radio Broadcast Problem.
APPROX-RANDOM 2004: 105-116 |
| 55 | | 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 | | Magnús M. Halldórsson,
Guy Kortsarz:
Multicoloring: Problems and Techniques.
MFCS 2004: 25-41 |
| 53 | | Guy Kortsarz,
Zeev Nutov:
Approximation algorithm for k-node connected subgraphs via critical graphs.
STOC 2004: 138-145 |
| 52 | | 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 | | Yana Kortsarts,
Guy Kortsarz,
Zeev Nutov:
Approximation Algorithm for Directed Multicuts.
WAOA 2004: 61-67 |
| 50 | | 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 | | Michael Elkin,
Guy Kortsarz:
Logarithmic inapproximability of the radio broadcast problem.
J. Algorithms 52(1): 8-25 (2004) |
| 48 | | 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 | | Guy Kortsarz,
Sunil M. Shende:
Approximating the Achromatic Number Problem on Bipartite Graphs.
ESA 2003: 385-396 |
| 46 | | 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 | | 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 | | Michael Elkin,
Guy Kortsarz:
Approximation Algorithm for Directed Telephone Multicast Problem.
ICALP 2003: 212-223 |
| 43 | | 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 | | Michael Elkin,
Guy Kortsarz:
Sublogarithmic approximation for telephone multicast: path out of jungle.
SODA 2003: 76-85 |
| 41 | | Guy Kortsarz,
Zeev Nutov:
Approximating Node Connectivity Problems via Set Covers.
Algorithmica 37(2): 75-92 (2003) |
| 40 | | 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 | | 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 | | 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 | | Guy Kortsarz,
Robert Krauthgamer,
James R. Lee:
Hardness of Approximation for Vertex-Connectivity Network-Design Problems.
APPROX 2002: 185-199 |
| 36 | | Guy Even,
Guy Kortsarz:
An approximation algorithm for the group Steiner problem.
SODA 2002: 49-58 |
| 35 | | Michael Elkin,
Guy Kortsarz:
Combinatorial logarithmic approximation algorithm for directed telephone broadcast problem.
STOC 2002: 438-447 |
| 34 | | Guy Even,
Guy Kortsarz,
Wolfgang Slany:
On Network Design Problems: Fixed Cost Flows and the Covering Steiner Problem.
SWAT 2002: 318-327 |
| 33 | | 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 | | 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 | | Magnús M. Halldórsson,
Guy Kortsarz,
Hadas Shachnai:
Minimizing Average Completion of Dedicated Tasks and Interval Graphs.
RANDOM-APPROX 2001: 114-126 |
| 30 | | 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 | | Guy Kortsarz,
Robert Krauthgamer:
On approximating the achromatic number.
SODA 2001: 309-318 |
| 28 | | Uriel Feige,
David Peleg,
Guy Kortsarz:
The Dense k-Subgraph Problem.
Algorithmica 29(3): 410-421 (2001) |
| 27 | | Guy Kortsarz:
On the Hardness of Approximating Spanners.
Algorithmica 30(3): 432-450 (2001) |
| 26 | | Guy Kortsarz,
Robert Krauthgamer:
On Approximating the Achromatic Number.
SIAM J. Discrete Math. 14(3): 408-422 (2001) |
| 25 | | Judit Bar-Ilan,
Guy Kortsarz,
David Peleg:
Generalized submodular cover problems and applications.
Theor. Comput. Sci. 250(1-2): 179-200 (2001) |
| 2000 |
|---|
| 24 | | Guy Kortsarz,
Zeev Nutov:
Approximating node connectivity problems via set covers.
APPROX 2000: 194-205 |
| 23 | | Uriel Feige,
Magnús M. Halldórsson,
Guy Kortsarz:
Approximating the domatic number.
STOC 2000: 134-143 |
| 22 | | 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 | | Magnús M. Halldórsson,
Guy Kortsarz,
Andrzej Proskurowski,
Ravit Salman,
Hadas Shachnai,
Jan Arne Telle:
Multi-coloring Trees.
COCOON 1999: 271-280 |
| 19 | | 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 | | Guy Kortsarz,
David Peleg:
Approximating the Weight of Shallow Steiner Trees.
Discrete Applied Mathematics 93(2-3): 265-285 (1999) |
| 16 | | 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 | | 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 | | 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 | | 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 |
