Guy Kortsarz

Publication Activity (10 Years)

Years Active: 1992-2024
Publications (10 Years): 47

Top Venues

CoRR

Theor. Comput. Sci.

ACM Trans. Algorithms

APPROX-RANDOM

Publications

Ilan Doron Arad, Guy Kortsarz, Joseph Naor, Baruch Schieber, Hadas Shachnai
Approximations and Hardness of Packing Partially Ordered Items. CoRR (2024)
Michael Dinitz, Guy Kortsarz, Shi Li
Degrees and Network Design: New Problems and Approximations. CoRR (2023)
Michael Dinitz, Ama Koranteng, Guy Kortsarz, Zeev Nutov
Improved Approximations for Relative Survivable Network Design. CoRR (2023)
Michael Dinitz, Ama Koranteng, Guy Kortsarz, Zeev Nutov
Improved Approximations for Relative Survivable Network Design. WAOA (2023)
Guy Kortsarz, Zeev Nutov, Eli Shalom
Approximating activation edge-cover and facility location problems. Theor. Comput. Sci. 930 (2022)
Xiangyu Guo, Guy Kortsarz, Bundit Laekhanukit, Shi Li, Daniel Vaz, Jiayi Xian
On Approximating Degree-Bounded Network Design Problems. Algorithmica 84 (5) (2022)
Michael Dinitz, Ama Koranteng, Guy Kortsarz
Relative Survivable Network Design. CoRR (2022)
Guy Kortsarz, Zeev Nutov
The minimum degree Group Steiner problem. Discret. Appl. Math. 309 (2022)
Michael Dinitz, Ama Koranteng, Guy Kortsarz
Relative Survivable Network Design. APPROX/RANDOM (2022)
Magnús M. Halldórsson, Guy Kortsarz, Pradipta Mitra, Tigran Tonoyan
Network Design under General Wireless Interference. Algorithmica 83 (11) (2021)
Parinya Chalermsook, Marek Cygan, Guy Kortsarz, Bundit Laekhanukit, Pasin Manurangsi, Danupon Nanongkai, Luca Trevisan
From Gap-Exponential Time Hypothesis to Fixed Parameter Tractable Inapproximability: Clique, Dominating Set, and More. SIAM J. Comput. 49 (4) (2020)
Eden Chlamtác, Michael Dinitz, Guy Kortsarz, Bundit Laekhanukit
Approximating Spanners and Directed Steiner Forest: Upper and Lower Bounds. ACM Trans. Algorithms 16 (3) (2020)
MohammadTaghi Hajiaghayi, Guy Kortsarz, Robert MacDavid, Manish Purohit, Kanthi K. Sarpatwar
Approximation algorithms for connected maximum cut and related problems. Theor. Comput. Sci. 814 (2020)
Guy Kortsarz, Zeev Nutov
Bounded Degree Group Steiner Tree Problems. IWOCA (2020)
Xiangyu Guo, Guy Kortsarz, Bundit Laekhanukit, Shi Li, Daniel Vaz, Jiayi Xian
On Approximating Degree-Bounded Network Design Problems. APPROX-RANDOM (2020)
Marek Cygan, Magnús M. Halldórsson, Guy Kortsarz
Tight Bounds on Subexponential Time Approximation of Set Cover and Related Problems. CoRR (2020)
Magnús M. Halldórsson, Guy Kortsarz, Marek Cygan
Tight Bounds on Subexponential Time Approximation of Set Cover and Related Problems. WAOA (2020)
Rajiv Gandhi, Magnús M. Halldórsson, Christian Konrad, Guy Kortsarz, Hoon Oh
Radio aggregation scheduling. Theor. Comput. Sci. 840 (2020)
Zeev Nutov, Guy Kortsarz, Eli Shalom
Approximating Activation Edge-Cover and Facility Location Problems. MFCS (2019)
Gruia Calinescu, Guy Kortsarz, Zeev Nutov
Improved approximation algorithms for minimum power covering problems. Theor. Comput. Sci. 795 (2019)
Guy Kortsarz, Zeev Nutov
Bounded Degree Group Steiner Tree Problems. CoRR (2019)
Hossein Esfandiari, Guy Kortsarz
A bounded-risk mechanism for the kidney exchange game. Discret. Appl. Math. 243 (2018)
Magnús M. Halldórsson, Guy Kortsarz, Pradipta Mitra, Tigran Tonoyan
Spanning Trees With Edge Conflicts and Wireless Connectivity. CoRR (2018)
Eden Chlamtác, Michael Dinitz, Christian Konrad, Guy Kortsarz, George Rabanca
The Densest k-Subhypergraph Problem. SIAM J. Discret. Math. 32 (2) (2018)
Magnús M. Halldórsson, Guy Kortsarz, Pradipta Mitra, Tigran Tonoyan
Spanning Trees With Edge Conflicts and Wireless Connectivity. ICALP (2018)
Guy Kortsarz, Zeev Nutov
LP-relaxations for tree augmentation. Discret. Appl. Math. 239 (2018)
Gruia Calinescu, Guy Kortsarz, Zeev Nutov
Improved Approximation Algorithms for Minimum Power Covering Problems. WAOA (2018)
Rajiv Gandhi, Mohammad Taghi Hajiaghayi, Guy Kortsarz, Manish Purohit, Kanthi K. Sarpatwar
On maximum leaf trees and connections to connected maximum cut problems. Inf. Process. Lett. 129 (2018)
Marek Cygan, Guy Kortsarz, Bundit Laekhanukit
On subexponential running times for approximating directed Steiner tree and related problems. CoRR (2018)
Parinya Chalermsook, Marek Cygan, Guy Kortsarz, Bundit Laekhanukit, Pasin Manurangsi, Danupon Nanongkai, Luca Trevisan
From Gap-ETH to FPT-Inapproximability: Clique, Dominating Set, and More. FOCS (2017)
Amey Bhangale, Rajiv Gandhi, Mohammad Taghi Hajiaghayi, Rohit Khandekar, Guy Kortsarz
Bi-Covering: Covering Edges with Two Small Subsets of Vertices. SIAM J. Discret. Math. 31 (4) (2017)
Guy Kortsarz, Zeev Nutov
Approximating source location and star survivable network problems. Theor. Comput. Sci. 674 (2017)
Eden Chlamtác, Michael Dinitz, Guy Kortsarz, Bundit Laekhanukit
Approximating Spanners and Directed Steiner Forest: Upper and Lower Bounds. SODA (2017)
Rajesh Chitnis, Hossein Esfandiari, Mohammad Taghi Hajiaghayi, Rohit Khandekar, Guy Kortsarz, Saeed Seddighin
A Tight Algorithm for Strongly Connected Steiner Subgraph on Two Terminals with Demands. Algorithmica 77 (4) (2017)
Parinya Chalermsook, Marek Cygan, Guy Kortsarz, Bundit Laekhanukit, Pasin Manurangsi, Danupon Nanongkai, Luca Trevisan
From Gap-ETH to FPT-Inapproximability: Clique, Dominating Set, and More. CoRR (2017)
Michael Dinitz, Guy Kortsarz, Zeev Nutov
-Forest with Nearly Uniform Weights. ACM Trans. Algorithms 13 (3) (2017)
Hossein Esfandiari, Guy Kortsarz
A Bounded-Risk Mechanism for the Kidney Exchange Game. LATIN (2016)
Michael Dinitz, Guy Kortsarz, Ran Raz
-Spanner. ACM Trans. Algorithms 12 (2) (2016)
Eden Chlamtác, Michael Dinitz, Christian Konrad, Guy Kortsarz, George Rabanca
The Densest k-Subhypergraph Problem. CoRR (2016)
MohammadTaghi Hajiaghayi, Rohit Khandekar, Guy Kortsarz, Zeev Nutov
On Fixed Cost k-Flow Problems. Theory Comput. Syst. 58 (1) (2016)
Eden Chlamtác, Michael Dinitz, Guy Kortsarz, Bundit Laekhanukit
Approximating Spanners and Directed Steiner Forest: Upper and Lower Bounds. CoRR (2016)
Eden Chlamtác, Michael Dinitz, Christian Konrad, Guy Kortsarz, George Rabanca
The Densest k-Subhypergraph Problem. APPROX-RANDOM (2016)
Mohammad Taghi Hajiaghayi, Amey Bhangale, Rajiv Gandhi, Rohit Khandekar, Guy Kortsarz
Bicovering: Covering edges with two small subsets of vertices. Electron. Colloquium Comput. Complex. 23 (2016)
Guy Kortsarz, Zeev Nutov
LP-Relaxations for Tree Augmentation. APPROX-RANDOM (2016)
Guy Kortsarz, Zeev Nutov
A Simplified 1.5-Approximation Algorithm for Augmenting Edge-Connectivity of a Graph from 1 to 2. ACM Trans. Algorithms 12 (2) (2016)
Mohammad Taghi Hajiaghayi, Rohit Khandekar, Mohammad Reza Khani, Guy Kortsarz
Approximation Algorithms for Movement Repairmen. ACM Trans. Algorithms 12 (4) (2016)
Amey Bhangale, Rajiv Gandhi, Mohammad Taghi Hajiaghayi, Rohit Khandekar, Guy Kortsarz
Bicovering: Covering Edges With Two Small Subsets of Vertices. ICALP (2016)
Rajesh Hemant Chitnis, Hossein Esfandiari, MohammadTaghi Hajiaghayi, Rohit Khandekar, Guy Kortsarz, Saeed Seddighin
A Tight Algorithm for Strongly Connected Steiner Subgraph On Two Terminals With Demands. CoRR (2015)
Guy Kortsarz, Zeev Nutov
A simplified 1.5-approximation algorithm for augmenting edge-connectivity of a graph from 1 to 2. CoRR (2015)
Guy Kortsarz, Zeev Nutov
Approximating Source Location and Star Survivable Network Problems. WG (2015)
Guy Kortsarz, Zeev Nutov
A 1.75 LP approximation for the Tree Augmentation Problem. CoRR (2015)
Mohammad Taghi Hajiaghayi, Guy Kortsarz, Robert MacDavid, Manish Purohit, Kanthi K. Sarpatwar
Approximation Algorithms for Connected Maximum Cut and Related Problems. ESA (2015)
MohammadTaghi Hajiaghayi, Guy Kortsarz, Robert MacDavid, Manish Purohit, Kanthi K. Sarpatwar
Approximation Algorithms for Connected Maximum Cut and Related Problems. CoRR (2015)
Hossein Efsandiari, Guy Kortsarz
Brief Announcement: New Mechanisms for Pairwise Kidney Exchange. SAGT (2015)
Hossein Esfandiari, Guy Kortsarz
Low-Risk Mechanisms for the Kidney Exchange Game. CoRR (2015)
Rajiv Gandhi, Magnús M. Halldórsson, Christian Konrad, Guy Kortsarz, Hoon Oh
Radio Aggregation Scheduling. ALGOSENSORS (2015)
Rajiv Gandhi, Guy Kortsarz
On set expansion problems and the small set expansion conjecture. Discret. Appl. Math. 194 (2015)
Rajiv Gandhi, Guy Kortsarz
On Set Expansion Problems and the Small Set Expansion Conjecture. WG (2014)
Rohit Khandekar, Guy Kortsarz, Vahab S. Mirrokni
On the Advantage of Overlapping Clusters for Minimizing Conductance. Algorithmica 69 (4) (2014)
Mohammad Taghi Hajiaghayi, Rohit Khandekar, Guy Kortsarz, Vahid Liaghat
On a Local Protocol for Concurrent File Transfers. Theory Comput. Syst. 55 (3) (2014)
Michael Dinitz, Guy Kortsarz, Zeev Nutov
Improved Approximation Algorithm for Steiner k-Forest with Nearly Uniform Weights. APPROX-RANDOM (2014)
Rajesh Hemant Chitnis, Hossein Esfandiari, MohammadTaghi Hajiaghayi, Rohit Khandekar, Guy Kortsarz, Saeed Seddighin
A Tight Algorithm for Strongly Connected Steiner Subgraph on Two Terminals with Demands (Extended Abstract). IPEC (2014)
Michael Dinitz, Guy Kortsarz
Matroid Secretary for Regular and Decomposable Matroids. SIAM J. Comput. 43 (5) (2014)
Mohammad Taghi Hajiaghayi, Rohit Khandekar, Guy Kortsarz
The Foundations of Fixed Parameter Inapproximability. CoRR (2013)
Marek Cygan, Guy Kortsarz, Zeev Nutov
Steiner Forest Orientation Problems. SIAM J. Discret. Math. 27 (3) (2013)
Rajesh Hemant Chitnis, MohammadTaghi Hajiaghayi, Guy Kortsarz
Fixed-Parameter and Approximation Algorithms: A New Look. IPEC (2013)
MohammadTaghi Hajiaghayi, Rohit Khandekar, M. Reza Khani, Guy Kortsarz
Approximation Algorithms for Movement Repairmen. APPROX-RANDOM (2013)
MohammadTaghi Hajiaghayi, Rohit Khandekar, Guy Kortsarz, Zeev Nutov
On Fixed Cost k-Flow Problems. WAOA (2013)
Rohit Khandekar, Guy Kortsarz, Zeev Nutov
On some network design problems with degree constraints. J. Comput. Syst. Sci. 79 (5) (2013)
Rajiv Gandhi, Guy Kortsarz
Edge covering with budget constrains. CoRR (2013)
MohammadTaghi Hajiaghayi, Rohit Khandekar, M. Reza Khani, Guy Kortsarz
Approximation Algorithms for Movement Repairmen. CoRR (2013)
Rajiv Gandhi, Magnús M. Halldórsson, Guy Kortsarz, Hadas Shachnai
Corrigendum: Improved results for data migration and open shop scheduling. ACM Trans. Algorithms 9 (4) (2013)
Michael Dinitz, Guy Kortsarz
Matroid Secretary for Regular and Decomposable Matroids. SODA (2013)
Rohit Khandekar, Guy Kortsarz, Vahab S. Mirrokni, Mohammad R. Salavatipour
Two-stage Robust Network Design with Exponential Scenarios. Algorithmica 65 (2) (2013)
Rajesh Hemant Chitnis, MohammadTaghi Hajiaghayi, Guy Kortsarz
Fixed-Parameter and Approximation Algorithms: A New Look. CoRR (2013)
MohammadTaghi Hajiaghayi, Rohit Khandekar, Guy Kortsarz
Local Search Algorithms for the Red-Blue Median Problem. Algorithmica 63 (4) (2012)
Mohammad Taghi Hajiaghayi, Rohit Khandekar, Guy Kortsarz, Zeev Nutov
Prize-collecting steiner network problems. ACM Trans. Algorithms 9 (1) (2012)
Rohit Khandekar, Guy Kortsarz, Vahab S. Mirrokni
Advantage of Overlapping Clusters for Minimizing Conductance. LATIN (2012)
Moran Feldman, Guy Kortsarz, Zeev Nutov
Improved approximation algorithms for Directed Steiner Forest. J. Comput. Syst. Sci. 78 (1) (2012)
Michael Dinitz, Guy Kortsarz, Ran Raz
Label Cover instances with large girth and the hardness of approximating basic k-spanner CoRR (2012)
MohammadTaghi Hajiaghayi, Rohit Khandekar, Guy Kortsarz, Julián Mestre
The checkpoint problem. Theor. Comput. Sci. 452 (2012)
Rohit Khandekar, Guy Kortsarz, Zeev Nutov
Approximating fault-tolerant group-Steiner problems. Theor. Comput. Sci. 416 (2012)
Michael Dinitz, Guy Kortsarz, Ran Raz
Label Cover Instances with Large Girth and the Hardness of Approximating Basic k-Spanner. ICALP (1) (2012)
Michael Dinitz, Guy Kortsarz
Matroid Secretary for Regular and Decomposable Matroids CoRR (2012)
Marek Cygan, Guy Kortsarz, Zeev Nutov
Steiner Forest Orientation Problems. ESA (2012)
Marek Cygan, Guy Kortsarz, Zeev Nutov
Steiner Forest Orientation Problems CoRR (2011)
Guy Kortsarz, Zeev Nutov
Approximating some network design problems with node costs. Theor. Comput. Sci. 412 (35) (2011)
MohammadTaghi Hajiaghayi, Rohit Khandekar, Guy Kortsarz, Vahid Liaghat
On a local protocol for concurrent file transfers. SPAA (2011)
MohammadTaghi Hajiaghayi, Rohit Khandekar, Guy Kortsarz, Zeev Nutov
Combinatorial Algorithms for Capacitated Network Design CoRR (2011)
Guy Even, Guy Kortsarz, Zeev Nutov
A 1.5-approximation algorithm for augmenting edge-connectivity of a graph from 1 to 2. Inf. Process. Lett. 111 (6) (2011)
Magnús M. Halldórsson, Guy Kortsarz, Maxim Sviridenko
Sum edge coloring of multigraphs via configuration LP. ACM Trans. Algorithms 7 (2) (2011)
Guy Kortsarz, Vahab S. Mirrokni, Zeev Nutov, Elena Tsanko
Approximating Minimum-Power Degree and Connectivity Problems. Algorithmica 60 (4) (2011)
Rohit Khandekar, Guy Kortsarz, Zeev Nutov
Network-Design with Degree Constraints. APPROX-RANDOM (2011)
MohammadTaghi Hajiaghayi, Rohit Khandekar, Guy Kortsarz
Budgeted Red-Blue Median and Its Generalizations. ESA (1) (2010)
MohammadTaghi Hajiaghayi, Rohit Khandekar, Guy Kortsarz, Zeev Nutov
Prize-Collecting Steiner Network Problems. IPCO (2010)
Chandra Chekuri, Mohammad Taghi Hajiaghayi, Guy Kortsarz, Mohammad R. Salavatipour
Approximation Algorithms for Nonuniform Buy-at-Bulk Network Design. SIAM J. Comput. 39 (5) (2010)
MohammadTaghi Hajiaghayi, Rohit Khandekar, Guy Kortsarz, Julián Mestre
The Checkpoint Problem. APPROX-RANDOM (2010)
Guy Kortsarz, Michael Langberg, Zeev Nutov
Approximating Maximum Subgraphs without Short Cycles. SIAM J. Discret. Math. 24 (1) (2010)
Guy Kortsarz, Zeev Nutov
Approximating minimum cost connectivity problems. Parameterized complexity and approximation algorithms (2009)
Guy Kortsarz, Zeev Nutov
Approximating minimum-power edge-covers and 2, 3-connectivity. Discret. Appl. Math. 157 (8) (2009)

Guy Kortsarz.css-eqlu8i{font-size:small;padding-left:4px;}

Publication Activity (10 Years)

Top Topics

Top Venues

Guy Kortsarz