Guy Kortsarz

R. Ravi

CoRR, 2024

Approximations and Hardness of Packing Partially Ordered Items.

[BibT_eX]

[DOI]

CoRR, 2024

Approximations and Hardness of Covering and Packing Partially Ordered Items.

[BibT_eX]

[DOI]

Proceedings of the Graph-Theoretic Concepts in Computer Science, 2024

The Telephone k-Multicast Problem.

[BibT_eX]

[DOI]

Daniel Hathcock

R. Ravi

Proceedings of the Approximation, 2024

Degrees and Network Design: New Problems and Approximations.

[BibT_eX]

[DOI]

Shi Li

Proceedings of the Approximation, 2024

2023

Improved Approximations for Relative Survivable Network Design.

[BibT_eX]

[DOI]

Proceedings of the Approximation and Online Algorithms - 21st International Workshop, 2023

2022

The minimum degree Group Steiner problem.

[BibT_eX]

[DOI]

Discret. Appl. Math., 2022

Relative Survivable Network Design.

[BibT_eX]

[DOI]

Ama Koranteng

Proceedings of the Approximation, 2022

2021

Network Design under General Wireless Interference.

[BibT_eX]

[DOI]

Pradipta Mitra

Tigran Tonoyan

Algorithmica, 2021

2020

From Gap-Exponential Time Hypothesis to Fixed Parameter Tractable Inapproximability: Clique, Dominating Set, and More.

[BibT_eX]

[DOI]

SIAM J. Comput., 2020

Tight Bounds on Subexponential Time Approximation of Set Cover and Related Problems.

[BibT_eX]

[DOI]

Marek Cygan

Proceedings of the Approximation and Online Algorithms - 18th International Workshop, 2020

Bounded Degree Group Steiner Tree Problems.

[BibT_eX]

[DOI]

Proceedings of the Combinatorial Algorithms - 31st International Workshop, 2020

On Approximating Degree-Bounded Network Design Problems.

[BibT_eX]

[DOI]

Proceedings of the Approximation, 2020

2019

Approximating Activation Edge-Cover and Facility Location Problems.

[BibT_eX]

[DOI]

Eli Shalom

Proceedings of the 44th International Symposium on Mathematical Foundations of Computer Science, 2019

2018

On maximum leaf trees and connections to connected maximum cut problems.

[BibT_eX]

[DOI]

Manish Purohit

Kanthi K. Sarpatwar

Inf. Process. Lett., 2018

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

[BibT_eX]

[DOI]

Marek Cygan

Bundit Laekhanukit

CoRR, 2018

Improved Approximation Algorithms for Minimum Power Covering Problems.

[BibT_eX]

[DOI]

Gruia Calinescu

Proceedings of the Approximation and Online Algorithms - 16th International Workshop, 2018

Spanning Trees With Edge Conflicts and Wireless Connectivity.

[BibT_eX]

[DOI]

Pradipta Mitra

Tigran Tonoyan

Proceedings of the 45th International Colloquium on Automata, Languages, and Programming, 2018

Algorithms for Chromatic Sums, Multicoloring, and Scheduling Dependent Jobs.

[BibT_eX]

[DOI]

Proceedings of the Handbook of Approximation Algorithms and Metaheuristics, 2018

2017

Improved Approximation Algorithm for Steiner k-Forest with Nearly Uniform Weights.

[BibT_eX]

[DOI]

ACM Trans. Algorithms, 2017

Bi-Covering: Covering Edges with Two Small Subsets of Vertices.

[BibT_eX]

[DOI]

Amey Bhangale

SIAM J. Discret. Math., 2017

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

[BibT_eX]

[DOI]

Rajesh Chitnis

Saeed Seddighin

Algorithmica, 2017

Approximating Spanners and Directed Steiner Forest: Upper and Lower Bounds.

[BibT_eX]

[DOI]

Proceedings of the Twenty-Eighth Annual ACM-SIAM Symposium on Discrete Algorithms, 2017

From Gap-ETH to FPT-Inapproximability: Clique, Dominating Set, and More.

[BibT_eX]

[DOI]

Proceedings of the 58th IEEE Annual Symposium on Foundations of Computer Science, 2017

2016

Fixed-Parameter Approximability and Hardness.

[BibT_eX]

[DOI]

Encyclopedia of Algorithms, 2016

A Simplified 1.5-Approximation Algorithm for Augmenting Edge-Connectivity of a Graph from 1 to 2.

[BibT_eX]

[DOI]

ACM Trans. Algorithms, 2016

Label Cover Instances with Large Girth and the Hardness of Approximating Basic k-Spanner.

[BibT_eX]

[DOI]

Ran Raz

ACM Trans. Algorithms, 2016

A Bounded-Risk Mechanism for the Kidney Exchange Game.

[BibT_eX]

[DOI]

Proceedings of the LATIN 2016: Theoretical Informatics, 2016

Bicovering: Covering Edges With Two Small Subsets of Vertices.

[BibT_eX]

[DOI]

Amey Bhangale

Proceedings of the 43rd International Colloquium on Automata, Languages, and Programming, 2016

LP-Relaxations for Tree Augmentation.

[BibT_eX]

[DOI]

Proceedings of the Approximation, 2016

The Densest k-Subhypergraph Problem.

[BibT_eX]

[DOI]

Proceedings of the Approximation, 2016

2015

A 1.75 LP approximation for the Tree Augmentation Problem.

[BibT_eX]

[DOI]

CoRR, 2015

Low-Risk Mechanisms for the Kidney Exchange Game.

[BibT_eX]

[DOI]

CoRR, 2015

Approximating Source Location and Star Survivable Network Problems.

[BibT_eX]

[DOI]

Proceedings of the Graph-Theoretic Concepts in Computer Science, 2015

Brief Announcement: New Mechanisms for Pairwise Kidney Exchange.

[BibT_eX]

[DOI]

Hossein Efsandiari

Proceedings of the Algorithmic Game Theory - 8th International Symposium, 2015

Approximation Algorithms for Connected Maximum Cut and Related Problems.

[BibT_eX]

[DOI]

Proceedings of the Algorithms - ESA 2015, 2015

Radio Aggregation Scheduling.

[BibT_eX]

[DOI]

Christian Konrad

Hoon Oh

Proceedings of the Algorithms for Sensor Systems, 2015

2014

On Set Expansion Problems and the Small Set Expansion Conjecture.

[BibT_eX]

[DOI]

Proceedings of the Graph-Theoretic Concepts in Computer Science, 2014

A Tight Algorithm for Strongly Connected Steiner Subgraph on Two Terminals with Demands (Extended Abstract).

[BibT_eX]

[DOI]

Rajesh Hemant Chitnis

Saeed Seddighin

Proceedings of the Parameterized and Exact Computation - 9th International Symposium, 2014

Improved Approximation Algorithm for Steiner k-Forest with Nearly Uniform Weights.

[BibT_eX]

[DOI]

Proceedings of the Approximation, 2014

2013

Corrigendum: Improved results for data migration and open shop scheduling.

[BibT_eX]

[DOI]

ACM Trans. Algorithms, 2013

On some network design problems with degree constraints.

[BibT_eX]

[DOI]

J. Comput. Syst. Sci., 2013

The Foundations of Fixed Parameter Inapproximability.

[BibT_eX]

[DOI]

CoRR, 2013

Edge covering with budget constrains.

[BibT_eX]

[DOI]

CoRR, 2013

On Fixed Cost k-Flow Problems.

[BibT_eX]

[DOI]

Proceedings of the Approximation and Online Algorithms - 11th International Workshop, 2013

Matroid Secretary for Regular and Decomposable Matroids.

[BibT_eX]

[DOI]

Proceedings of the Twenty-Fourth Annual ACM-SIAM Symposium on Discrete Algorithms, 2013

Fixed-Parameter and Approximation Algorithms: A New Look.

[BibT_eX]

[DOI]

Rajesh Hemant Chitnis

Proceedings of the Parameterized and Exact Computation - 8th International Symposium, 2013

Approximation Algorithms for Movement Repairmen.

[BibT_eX]

[DOI]

M. Reza Khani

Proceedings of the Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques, 2013

2012

Local Search Algorithms for the Red-Blue Median Problem.

[BibT_eX]

[DOI]

Algorithmica, 2012

Advantage of Overlapping Clusters for Minimizing Conductance.

[BibT_eX]

[DOI]

Vahab S. Mirrokni

Proceedings of the LATIN 2012: Theoretical Informatics, 2012

Label Cover Instances with Large Girth and the Hardness of Approximating Basic k-Spanner.

[BibT_eX]

[DOI]

Ran Raz

Proceedings of the Automata, Languages, and Programming - 39th International Colloquium, 2012

Steiner Forest Orientation Problems.

[BibT_eX]

[DOI]

Marek Cygan

Proceedings of the Algorithms - ESA 2012, 2012

2011

Sum edge coloring of multigraphs via configuration LP.

[BibT_eX]

[DOI]

Maxim Sviridenko

ACM Trans. Algorithms, 2011

A 1.5-approximation algorithm for augmenting edge-connectivity of a graph from 1 to 2.

[BibT_eX]

[DOI]

Inf. Process. Lett., 2011

Combinatorial Algorithms for Capacitated Network Design

[BibT_eX]

[DOI]

CoRR, 2011

On a local protocol for concurrent file transfers.

[BibT_eX]

[DOI]

Vahid Liaghat

Proceedings of the SPAA 2011: Proceedings of the 23rd Annual ACM Symposium on Parallelism in Algorithms and Architectures, 2011

Network-Design with Degree Constraints.

[BibT_eX]

[DOI]

Proceedings of the Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques, 2011

2010

Approximation Algorithms for Nonuniform Buy-at-Bulk Network Design.

[BibT_eX]

[DOI]

SIAM J. Comput., 2010

Prize-Collecting Steiner Network Problems.

[BibT_eX]

[DOI]

Proceedings of the Integer Programming and Combinatorial Optimization, 2010

Budgeted Red-Blue Median and Its Generalizations.

[BibT_eX]

[DOI]

Proceedings of the Algorithms, 2010

The Checkpoint Problem.

[BibT_eX]

[DOI]

Julián Mestre

Proceedings of the Approximation, 2010

2009

A 1.8 approximation algorithm for augmenting edge-connectivity of a graph from 1 to 2.

[BibT_eX]

[DOI]

ACM Trans. Algorithms, 2009

Approximating minimum-power edge-covers and 2, 3-connectivity.

[BibT_eX]

[DOI]

Discret. Appl. Math., 2009

Improved approximating algorithms for Directed Steiner Forest.

[BibT_eX]

[DOI]

Moran Feldman

Proceedings of the Twentieth Annual ACM-SIAM Symposium on Discrete Algorithms, 2009

Approximating Fault-Tolerant Group-Steiner Problems.

[BibT_eX]

[DOI]

Proceedings of the IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science, 2009

Approximating minimum cost connectivity problems.

[BibT_eX]

[DOI]

Proceedings of the Parameterized complexity and approximation algorithms, 13.12., 2009

Approximating Some Network Design Problems with Node Costs.

[BibT_eX]

[DOI]

Proceedings of the Approximation, 2009

2008

Improved bounds for scheduling conflicting jobs with minsum criteria.

[BibT_eX]

[DOI]

ACM Trans. Algorithms, 2008

A note on two source location problems.

[BibT_eX]

[DOI]

J. Discrete Algorithms, 2008

Approximating Minimum-Power Degree and Connectivity Problems.

[BibT_eX]

[DOI]

Proceedings of the LATIN 2008: Theoretical Informatics, 2008

Min Sum Edge Coloring in Multigraphs Via Configuration LP.

[BibT_eX]

[DOI]

Maxim Sviridenko

Proceedings of the Integer Programming and Combinatorial Optimization, 2008

Two-Stage Robust Network Design with Exponential Scenarios.

[BibT_eX]

[DOI]

Vahab S. Mirrokni

Proceedings of the Algorithms, 2008

Approximating Maximum Subgraphs without Short Cycles.

[BibT_eX]

[DOI]

Michael Langberg

Proceedings of the Approximation, 2008

2007

Approximating Minimum-Cost Connectivity Problems.

[BibT_eX]

[DOI]

Proceedings of the Handbook of Approximation Algorithms and Metaheuristics., 2007

An improved algorithm for radio broadcast.

[BibT_eX]

[DOI]

ACM Trans. Algorithms, 2007

An Improved Approximation of the Achromatic Number on Bipartite Graphs.

[BibT_eX]

[DOI]

Sunil M. Shende

SIAM J. Discret. Math., 2007

Improved approximation algorithms for directed Steiner forest.

[BibT_eX]

[DOI]

Moran Feldman

Electron. Colloquium Comput. Complex., 2007

A Lower Bound for Approximating Grundy Numbering.

[BibT_eX]

[DOI]

Discret. Math. Theor. Comput. Sci., 2007

Complete partitions of graphs.

[BibT_eX]

[DOI]

Sivaramakrishnan Sivasubramanian

Jaikumar Radhakrishnan

Comb., 2007

The minimum shift design problem.

[BibT_eX]

[DOI]

Ann. Oper. Res., 2007

Approximation algorithms for node-weighted buy-at-bulk network design.

[BibT_eX]

[DOI]

Proceedings of the Eighteenth Annual ACM-SIAM Symposium on Discrete Algorithms, 2007

2006

Sublogarithmic approximation for telephone multicast.

[BibT_eX]

[DOI]

J. Comput. Syst. Sci., 2006

Polylogarithmic Approximation Algorithm for Non-Uniform Multicommodity Buy-at-Bulk

[BibT_eX]

[DOI]

Electron. Colloquium Comput. Complex., 2006

Approximating Buy-at-Bulk k-Steiner trees

[BibT_eX]

[DOI]

Electron. Colloquium Comput. Complex., 2006

Approximating the Minimal Sensor Selection for Supervisory Control.

[BibT_eX]

[DOI]

Kurt Rohloff

Samir Khuller

Discret. Event Dyn. Syst., 2006

A greedy approximation algorithm for the group Steiner problem.

[BibT_eX]

[DOI]

Discret. Appl. Math., 2006

An Approximation Algorithm for the Directed Telephone Multicast Problem.

[BibT_eX]

[DOI]

Algorithmica, 2006

Tight Approximation Algorithm for Connectivity Augmentation Problems.

[BibT_eX]

[DOI]

Proceedings of the Automata, Languages and Programming, 33rd International Colloquium, 2006

Approximation Algorithms for Non-Uniform Buy-at-Bulk Network Design.

[BibT_eX]

[DOI]

Proceedings of the 47th Annual IEEE Symposium on Foundations of Computer Science, 2006

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

[BibT_eX]

[DOI]

Proceedings of the Approximation, 2006

2005

Polylogarithmic Additive Inapproximability of the Radio Broadcast Problem.

[BibT_eX]

[DOI]

SIAM J. Discret. Math., 2005

Approximating k-node Connected Subgraphs via Critical Graphs.

[BibT_eX]

[DOI]

SIAM J. Comput., 2005

Greedy approximation algorithms for directed multicuts.

[BibT_eX]

[DOI]

Yana Kortsarts

Networks, 2005

Asymmetric k-center is log* n-hard to approximate.

[BibT_eX]

[DOI]

J. ACM, 2005

Complete partitions of graphs.

[BibT_eX]

[DOI]

Sivaramakrishnan Sivasubramanian

Jaikumar Radhakrishnan

Proceedings of the Sixteenth Annual ACM-SIAM Symposium on Discrete Algorithms, 2005

Improved schedule for radio broadcast.

[BibT_eX]

[DOI]

Proceedings of the Sixteenth Annual ACM-SIAM Symposium on Discrete Algorithms, 2005

Power Optimization for Connectivity Problems.

[BibT_eX]

[DOI]

Vahab S. Mirrokni

Proceedings of the Integer Programming and Combinatorial Optimization, 2005

2004

Logarithmic inapproximability of the radio broadcast problem.

[BibT_eX]

[DOI]

J. Algorithms, 2004

Approximation Algorithm for Directed Multicuts.

[BibT_eX]

[DOI]

Yana Kortsarts

Proceedings of the Approximation and Online Algorithms, Second International Workshop, 2004

Improved Bounds for Sum Multicoloring and Scheduling Dependent Jobs with Minsum Criteria.

[BibT_eX]

[DOI]

Proceedings of the Approximation and Online Algorithms, Second International Workshop, 2004

Approximation algorithm for k-node connected subgraphs via critical graphs.

[BibT_eX]

[DOI]

Proceedings of the 36th Annual ACM Symposium on Theory of Computing, 2004

Asymmetric k-center is log* n-hard to approximate.

[BibT_eX]

[DOI]

Proceedings of the 36th Annual ACM Symposium on Theory of Computing, 2004

Multicoloring: Problems and Techniques.

[BibT_eX]

[DOI]

Proceedings of the Mathematical Foundations of Computer Science 2004, 2004

Improved Results for Data Migration and Open Shop Scheduling.

[BibT_eX]

[DOI]

Proceedings of the Automata, Languages and Programming: 31st International Colloquium, 2004

Polylogarithmic Inapproximability of the Radio Broadcast Problem.

[BibT_eX]

[DOI]

Proceedings of the Approximation, 2004

2003

Multicoloring trees.

[BibT_eX]

[DOI]

Inf. Comput., 2003

Tight lower bounds for the asymmetric k-center problem

[BibT_eX]

[DOI]

Eran Halperin

Robert Krauthgamer

Electron. Colloquium Comput. Complex., 2003

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

[BibT_eX]

[DOI]

Algorithmica, 2003

Integrality ratio for group Steiner trees and directed steiner trees.

[BibT_eX]

[DOI]

Proceedings of the Fourteenth Annual ACM-SIAM Symposium on Discrete Algorithms, 2003

Sublogarithmic approximation for telephone multicast: path out of jungle.

[BibT_eX]

[DOI]

Proceedings of the Fourteenth Annual ACM-SIAM Symposium on Discrete Algorithms, 2003

An Improved Approximation Algorithm for Vertex Cover with Hard Capacities.

[BibT_eX]

[DOI]

Proceedings of the Automata, Languages and Programming, 30th International Colloquium, 2003

Approximation Algorithm for Directed Telephone Multicast Problem.

[BibT_eX]

[DOI]

Proceedings of the Automata, Languages and Programming, 30th International Colloquium, 2003

Approximating the Achromatic Number Problem on Bipartite Graphs.

[BibT_eX]

[DOI]

Sunil M. Shende

Proceedings of the Algorithms, 2003

The Minimum Shift Design Problem: Theory and Practice.

[BibT_eX]

[DOI]

Proceedings of the Algorithms, 2003

2002

Approximating the Domatic Number.

[BibT_eX]

[DOI]

Uriel Feige

Aravind Srinivasan

SIAM J. Comput., 2002

Tools for Multicoloring with Applications to Planar Graphs and Partial k-Trees.

[BibT_eX]

[DOI]

J. Algorithms, 2002

On Network Design Problems: Fixed Cost Flows and the Covering Steiner Problem.

[BibT_eX]

[DOI]

Wolfgang Slany

Proceedings of the Algorithm Theory, 2002

Combinatorial logarithmic approximation algorithm for directed telephone broadcast problem.

[BibT_eX]

[DOI]

Proceedings of the Proceedings on 34th Annual ACM Symposium on Theory of Computing, 2002

An approximation algorithm for the group Steiner problem.

[BibT_eX]

[DOI]

Proceedings of the Thirteenth Annual ACM-SIAM Symposium on Discrete Algorithms, 2002

Hardness of Approximation for Vertex-Connectivity Network-Design Problems.

[BibT_eX]

[DOI]

Robert Krauthgamer

James R. Lee

Proceedings of the Approximation Algorithms for Combinatorial Optimization, 2002

2001

On the Hardness of Approximating Spanners.

[BibT_eX]

[DOI]

Algorithmica, 2001

The Dense k-Subgraph Problem.

[BibT_eX]

[DOI]

Uriel Feige

Algorithmica, 2001

On approximating the achromatic number.

[BibT_eX]

[DOI]

Robert Krauthgamer

Proceedings of the Twelfth Annual Symposium on Discrete Algorithms, 2001

Minimizing Average Completion of Dedicated Tasks and Interval Graphs.

[BibT_eX]

[DOI]

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.

[BibT_eX]

[DOI]

Proceedings of the Approximation, 2001

2000

Sum Multicoloring of Graphs.

[BibT_eX]

[DOI]

Ravit Salman

J. Algorithms, 2000

Tree Spanners for Subgraphs and Related Tree Covering Problems.

[BibT_eX]

[DOI]

Dagmar Handke

Proceedings of the Graph-Theoretic Concepts in Computer Science, 2000

Approximating the domatic number.

[BibT_eX]

[DOI]

Uriel Feige

Proceedings of the Thirty-Second Annual ACM Symposium on Theory of Computing, 2000

Approximating node connectivity problems via set covers.

[BibT_eX]

[DOI]

Proceedings of the Approximation Algorithms for Combinatorial Optimization, 2000

1999

A Matched Approximation Bound for the Sum of a Greedy Coloring.

[BibT_eX]

[DOI]

Inf. Process. Lett., 1999

Approximating the Weight of Shallow Steiner Trees.

[BibT_eX]

[DOI]

Discret. Appl. Math., 1999

Multicoloring Planar Graphs and Partial k-Trees.

[BibT_eX]

[DOI]

Proceedings of the Randomization, 1999

Sum Multi-coloring of Graphs.

[BibT_eX]

[DOI]

Ravit Salman

Proceedings of the Algorithms, 1999

Multi-coloring Trees.

[BibT_eX]

[DOI]

Proceedings of the Computing and Combinatorics, 5th Annual International Conference, 1999

1998

On the Hardness of Approximation Spanners.

[BibT_eX]

[DOI]

Proceedings of the Approximation Algorithms for Combinatorial Optimization, 1998

1997

Approximating Shallow-Light Trees (Extended Abstract).

[BibT_eX]

[DOI]

Proceedings of the Eighth Annual ACM-SIAM Symposium on Discrete Algorithms, 1997

The Minimum Color Sum of Bipartite Graphs.

[BibT_eX]

[DOI]

Proceedings of the Automata, Languages and Programming, 24th International Colloquium, 1997

1996

Generalized Submodular Cover Problems and Applications.

[BibT_eX]

Judit Bar-Ilan

Proceedings of the Fourth Israel Symposium on Theory of Computing and Systems, 1996

1994

Traffic-light scheduling on the grid.

[BibT_eX]

[DOI]

Discret. Appl. Math., 1994

Generating Low-Degree 2-Spanners.

[BibT_eX]

[DOI]

Proceedings of the Fifth Annual ACM-SIAM Symposium on Discrete Algorithms. 23-25 January 1994, 1994

1993

How to Allocate Network Centers.

[BibT_eX]

[DOI]

Judit Bar-Ilan

J. Algorithms, 1993

On Choosing a Dense Subgraph (Extended Abstract)

[BibT_eX]

[DOI]

Proceedings of the 34th Annual Symposium on Foundations of Computer Science, 1993

1992

Traffic-Light Scheduling on the Grid (Extended Abstract).

[BibT_eX]

[DOI]

Proceedings of the Distributed Algorithms, 6th International Workshop, 1992

Generating Sparse 2-spanners.

[BibT_eX]

[DOI]

Proceedings of the Algorithm Theory, 1992

Approximation Algorithms for Minimum Time Broadcast.

[BibT_eX]

[DOI]