Guy Kortsarz

According to our database1, Guy Kortsarz authored at least 133 papers between 1992 and 2019.

Collaborative distances:

Timeline

Legend:

Book 
In proceedings 
Article 
PhD thesis 
Other 

Links

On csauthors.net:

Bibliography

2019
Improved approximation algorithms for minimum power covering problems.
Theor. Comput. Sci., 2019

Bounded Degree Group Steiner Tree Problems.
CoRR, 2019

Approximating Activation Edge-Cover and Facility Location Problems.
Proceedings of the 44th International Symposium on Mathematical Foundations of Computer Science, 2019

2018
The Densest k-Subhypergraph Problem.
SIAM J. Discrete Math., 2018

On maximum leaf trees and connections to connected maximum cut problems.
Inf. Process. Lett., 2018

LP-relaxations for tree augmentation.
Discret. Appl. Math., 2018

A bounded-risk mechanism for the kidney exchange game.
Discret. Appl. Math., 2018

On subexponential running times for approximating directed Steiner tree and related problems.
CoRR, 2018

Spanning Trees With Edge Conflicts and Wireless Connectivity.
Proceedings of the 45th International Colloquium on Automata, Languages, and Programming, 2018

Algorithms for Chromatic Sums, Multicoloring, and Scheduling Dependent Jobs.
Proceedings of the Handbook of Approximation Algorithms and Metaheuristics, 2018

2017
Approximating source location and star survivable network problems.
Theor. Comput. Sci., 2017

Improved Approximation Algorithm for Steiner k-Forest with Nearly Uniform Weights.
ACM Trans. Algorithms, 2017

Bi-Covering: Covering Edges with Two Small Subsets of Vertices.
SIAM J. Discrete Math., 2017

A Tight Algorithm for Strongly Connected Steiner Subgraph on Two Terminals with Demands.
Algorithmica, 2017

Approximating Spanners and Directed Steiner Forest: Upper and Lower Bounds.
Proceedings of the Twenty-Eighth Annual ACM-SIAM Symposium on Discrete Algorithms, 2017

From Gap-ETH to FPT-Inapproximability: Clique, Dominating Set, and More.
Proceedings of the 58th IEEE Annual Symposium on Foundations of Computer Science, 2017

2016
Fixed-Parameter Approximability and Hardness.
Encyclopedia of Algorithms, 2016

A Simplified 1.5-Approximation Algorithm for Augmenting Edge-Connectivity of a Graph from 1 to 2.
ACM Trans. Algorithms, 2016

Approximation Algorithms for Movement Repairmen.
ACM Trans. Algorithms, 2016

Label Cover Instances with Large Girth and the Hardness of Approximating Basic k-Spanner.
ACM Trans. Algorithms, 2016

On Fixed Cost k-Flow Problems.
Theory Comput. Syst., 2016

Bicovering: Covering edges with two small subsets of vertices.
Electronic Colloquium on Computational Complexity (ECCC), 2016

2015
On set expansion problems and the small set expansion conjecture.
Discret. Appl. Math., 2015

A 1.75 LP approximation for the Tree Augmentation Problem.
CoRR, 2015

Low-Risk Mechanisms for the Kidney Exchange Game.
CoRR, 2015

Brief Announcement: New Mechanisms for Pairwise Kidney Exchange.
Proceedings of the Algorithmic Game Theory - 8th International Symposium, 2015

Approximation Algorithms for Connected Maximum Cut and Related Problems.
Proceedings of the Algorithms - ESA 2015, 2015

Radio Aggregation Scheduling.
Proceedings of the Algorithms for Sensor Systems, 2015

2014
Matroid Secretary for Regular and Decomposable Matroids.
SIAM J. Comput., 2014

On a Local Protocol for Concurrent File Transfers.
Theory Comput. Syst., 2014

On the Advantage of Overlapping Clusters for Minimizing Conductance.
Algorithmica, 2014

A Tight Algorithm for Strongly Connected Steiner Subgraph on Two Terminals with Demands (Extended Abstract).
Proceedings of the Parameterized and Exact Computation - 9th International Symposium, 2014

Improved Approximation Algorithm for Steiner k-Forest with Nearly Uniform Weights.
Proceedings of the Approximation, 2014

2013
Corrigendum: Improved results for data migration and open shop scheduling.
ACM Trans. Algorithms, 2013

Steiner Forest Orientation Problems.
SIAM J. Discrete Math., 2013

On some network design problems with degree constraints.
J. Comput. Syst. Sci., 2013

The Foundations of Fixed Parameter Inapproximability.
CoRR, 2013

Edge covering with budget constrains.
CoRR, 2013

Two-stage Robust Network Design with Exponential Scenarios.
Algorithmica, 2013

Fixed-Parameter and Approximation Algorithms: A New Look.
Proceedings of the Parameterized and Exact Computation - 8th International Symposium, 2013

2012
Approximating fault-tolerant group-Steiner problems.
Theor. Comput. Sci., 2012

The checkpoint problem.
Theor. Comput. Sci., 2012

Prize-collecting steiner network problems.
ACM Trans. Algorithms, 2012

Improved approximation algorithms for Directed Steiner Forest.
J. Comput. Syst. Sci., 2012

Local Search Algorithms for the Red-Blue Median Problem.
Algorithmica, 2012

Label Cover Instances with Large Girth and the Hardness of Approximating Basic k-Spanner.
Proceedings of the Automata, Languages, and Programming - 39th International Colloquium, 2012

2011
Approximating some network design problems with node costs.
Theor. Comput. Sci., 2011

Sum edge coloring of multigraphs via configuration LP.
ACM Trans. Algorithms, 2011

A 1.5-approximation algorithm for augmenting edge-connectivity of a graph from 1 to 2.
Inf. Process. Lett., 2011

Combinatorial Algorithms for Capacitated Network Design
CoRR, 2011

Approximating Minimum-Power Degree and Connectivity Problems.
Algorithmica, 2011

Network-Design with Degree Constraints.
Proceedings of the Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques, 2011

2010
Approximating Maximum Subgraphs without Short Cycles.
SIAM J. Discrete Math., 2010

Approximation Algorithms for Nonuniform Buy-at-Bulk Network Design.
SIAM J. Comput., 2010

Budgeted Red-Blue Median and Its Generalizations.
Proceedings of the Algorithms, 2010

2009
A 1.8 approximation algorithm for augmenting edge-connectivity of a graph from 1 to 2.
ACM Trans. Algorithms, 2009

Approximating minimum-power edge-covers and 2, 3-connectivity.
Discret. Appl. Math., 2009

Approximating Buy-at-Bulk and Shallow-Light k-Steiner Trees.
Algorithmica, 2009

Improved approximating algorithms for Directed Steiner Forest.
Proceedings of the Twentieth Annual ACM-SIAM Symposium on Discrete Algorithms, 2009

Approximating minimum cost connectivity problems.
Proceedings of the Parameterized complexity and approximation algorithms, 13.12., 2009

2008
Improved bounds for scheduling conflicting jobs with minsum criteria.
ACM Trans. Algorithms, 2008

A note on two source location problems.
J. Discrete Algorithms, 2008

Tight approximation algorithm for connectivity augmentation problems.
J. Comput. Syst. Sci., 2008

Min Sum Edge Coloring in Multigraphs Via Configuration LP.
Proceedings of the Integer Programming and Combinatorial Optimization, 2008

2007
Approximating Minimum-Cost Connectivity Problems.
Proceedings of the Handbook of Approximation Algorithms and Metaheuristics., 2007

An improved algorithm for radio broadcast.
ACM Trans. Algorithms, 2007

An Improved Approximation of the Achromatic Number on Bipartite Graphs.
SIAM J. Discrete Math., 2007

Integrality Ratio for Group Steiner Trees and Directed Steiner Trees.
SIAM J. Comput., 2007

Power optimization for connectivity problems.
Math. Program., 2007

A Lower Bound for Approximating Grundy Numbering.
Discrete Mathematics & Theoretical Computer Science, 2007

Complete partitions of graphs.
Combinatorica, 2007

The minimum shift design problem.
Annals OR, 2007

Approximation algorithms for node-weighted buy-at-bulk network design.
Proceedings of the Eighteenth Annual ACM-SIAM Symposium on Discrete Algorithms, 2007

2006
Improved results for data migration and open shop scheduling.
ACM Trans. Algorithms, 2006

An improved approximation algorithm for vertex cover with hard capacities.
J. Comput. Syst. Sci., 2006

Sublogarithmic approximation for telephone multicast.
J. Comput. Syst. Sci., 2006

Polylogarithmic Approximation Algorithm for Non-Uniform Multicommodity Buy-at-Bulk
Electronic Colloquium on Computational Complexity (ECCC), 2006

Approximating Buy-at-Bulk k-Steiner trees
Electronic Colloquium on Computational Complexity (ECCC), 2006

Approximating the Minimal Sensor Selection for Supervisory Control.
Discrete Event Dynamic Systems, 2006

A greedy approximation algorithm for the group Steiner problem.
Discret. Appl. Math., 2006

An Approximation Algorithm for the Directed Telephone Multicast Problem.
Algorithmica, 2006

Approximation Algorithms for Non-Uniform Buy-at-Bulk Network Design.
Proceedings of the 47th Annual IEEE Symposium on Foundations of Computer Science (FOCS 2006), 2006

2005
On network design problems: fixed cost flows and the covering steiner problem.
ACM Trans. Algorithms, 2005

Polylogarithmic Additive Inapproximability of the Radio Broadcast Problem.
SIAM J. Discrete Math., 2005

Approximating k-node Connected Subgraphs via Critical Graphs.
SIAM J. Comput., 2005

A Combinatorial Logarithmic Approximation Algorithm for the Directed Telephone Broadcast Problem.
SIAM J. Comput., 2005

Greedy approximation algorithms for directed multicuts.
Networks, 2005

Asymmetric k-center is log* n-hard to approximate.
J. ACM, 2005

Complete partitions of graphs.
Proceedings of the Sixteenth Annual ACM-SIAM Symposium on Discrete Algorithms, 2005

Improved schedule for radio broadcast.
Proceedings of the Sixteenth Annual ACM-SIAM Symposium on Discrete Algorithms, 2005

2004
Hardness of Approximation for Vertex-Connectivity Network Design Problems.
SIAM J. Comput., 2004

Logarithmic inapproximability of the radio broadcast problem.
J. Algorithms, 2004

Approximation Algorithm for Directed Multicuts.
Proceedings of the Approximation and Online Algorithms, Second International Workshop, 2004

Improved Bounds for Sum Multicoloring and Scheduling Dependent Jobs with Minsum Criteria.
Proceedings of the Approximation and Online Algorithms, Second International Workshop, 2004

Approximation algorithm for k-node connected subgraphs via critical graphs.
Proceedings of the 36th Annual ACM Symposium on Theory of Computing, 2004

Asymmetric k-center is log* n-hard to approximate.
Proceedings of the 36th Annual ACM Symposium on Theory of Computing, 2004

Multicoloring: Problems and Techniques.
Proceedings of the Mathematical Foundations of Computer Science 2004, 2004

Polylogarithmic Inapproximability of the Radio Broadcast Problem.
Proceedings of the Approximation, 2004

2003
Multicoloring trees.
Inf. Comput., 2003

Tight lower bounds for the asymmetric k-center problem
Electronic Colloquium on Computational Complexity (ECCC), 2003

Approximating Node Connectivity Problems via Set Covers.
Algorithmica, 2003

Sum Coloring Interval and k-Claw Free Graphs with Application to Scheduling Dependent Jobs.
Algorithmica, 2003

Sublogarithmic approximation for telephone multicast: path out of jungle.
Proceedings of the Fourteenth Annual ACM-SIAM Symposium on Discrete Algorithms, 2003

Approximation Algorithm for Directed Telephone Multicast Problem.
Proceedings of the Automata, Languages and Programming, 30th International Colloquium, 2003

Approximating the Achromatic Number Problem on Bipartite Graphs.
Proceedings of the Algorithms, 2003

The Minimum Shift Design Problem: Theory and Practice.
Proceedings of the Algorithms, 2003

2002
Approximating the Domatic Number.
SIAM J. Comput., 2002

Tools for Multicoloring with Applications to Planar Graphs and Partial k-Trees.
J. Algorithms, 2002

An approximation algorithm for the group Steiner problem.
Proceedings of the Thirteenth Annual ACM-SIAM Symposium on Discrete Algorithms, 2002

2001
Generalized submodular cover problems and applications.
Theor. Comput. Sci., 2001

On Approximating the Achromatic Number.
SIAM J. Discrete Math., 2001

On the Hardness of Approximating Spanners.
Algorithmica, 2001

The Dense k-Subgraph Problem.
Algorithmica, 2001

Minimizing Average Completion of Dedicated Tasks and Interval Graphs.
Proceedings of the Approximation, 2001

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.
Proceedings of the Approximation, 2001

2000
Sum Multicoloring of Graphs.
J. Algorithms, 2000

Tree Spanners for Subgraphs and Related Tree Covering Problems.
Proceedings of the Graph-Theoretic Concepts in Computer Science, 2000

Approximating the domatic number.
Proceedings of the Thirty-Second Annual ACM Symposium on Theory of Computing, 2000

1999
A Matched Approximation Bound for the Sum of a Greedy Coloring.
Inf. Process. Lett., 1999

Approximating the Weight of Shallow Steiner Trees.
Discret. Appl. Math., 1999

Multicoloring Planar Graphs and Partial k-Trees.
Proceedings of the Randomization, 1999

Sum Multi-coloring of Graphs.
Proceedings of the Algorithms, 1999

Multi-coloring Trees.
Proceedings of the Computing and Combinatorics, 5th Annual International Conference, 1999

1998
Generating Low-Degree 2-Spanners.
SIAM J. Comput., 1998

Minimum Color Sum of Bipartite Graphs.
J. Algorithms, 1998

On the Hardness of Approximation Spanners.
Proceedings of the Approximation Algorithms for Combinatorial Optimization, 1998

1997
Approximating Shallow-Light Trees (Extended Abstract).
Proceedings of the Eighth Annual ACM-SIAM Symposium on Discrete Algorithms, 1997

1995
Approximation Algorithms for Minimum-Time Broadcast.
SIAM J. Discrete Math., 1995

1994
Generating Sparse 2-Spanners.
J. Algorithms, 1994

Traffic-light scheduling on the grid.
Discret. Appl. Math., 1994

1993
How to Allocate Network Centers.
J. Algorithms, 1993

On Choosing a Dense Subgraph (Extended Abstract)
Proceedings of the 34th Annual Symposium on Foundations of Computer Science, 1993

1992
Traffic-Light Scheduling on the Grid (Extended Abstract).
Proceedings of the Distributed Algorithms, 6th International Workshop, 1992


  Loading...