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

Approximating activation edge-cover and facility location problems.

[BibT_eX]

[DOI]

Eli Shalom

Theor. Comput. Sci., 2022

The minimum degree Group Steiner problem.

[BibT_eX]

[DOI]

Discret. Appl. Math., 2022

On Approximating Degree-Bounded Network Design Problems.

[BibT_eX]

[DOI]

Algorithmica, 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

Approximation algorithms for connected maximum cut and related problems.

[BibT_eX]

[DOI]

Theor. Comput. Sci., 2020

Radio aggregation scheduling.

[BibT_eX]

[DOI]

Christian Konrad

Hoon Oh

Theor. Comput. Sci., 2020

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

[BibT_eX]

[DOI]

ACM Trans. Algorithms, 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

2019

Improved approximation algorithms for minimum power covering problems.

[BibT_eX]

[DOI]

Gruia Calinescu

Theor. Comput. Sci., 2019

2018

The Densest k-Subhypergraph Problem.

[BibT_eX]

[DOI]

SIAM J. Discret. Math., 2018

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

[BibT_eX]

[DOI]

Manish Purohit

Kanthi K. Sarpatwar

Inf. Process. Lett., 2018

LP-relaxations for tree augmentation.

[BibT_eX]

[DOI]

Discret. Appl. Math., 2018

A bounded-risk mechanism for the kidney exchange game.

[BibT_eX]

[DOI]

Discret. Appl. Math., 2018

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

[BibT_eX]

[DOI]

Marek Cygan

Bundit Laekhanukit

CoRR, 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

Approximating source location and star survivable network problems.

[BibT_eX]

[DOI]

Theor. Comput. Sci., 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

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

Approximation Algorithms for Movement Repairmen.

[BibT_eX]

[DOI]

Mohammad Reza Khani

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

On Fixed Cost k-Flow Problems.

[BibT_eX]

[DOI]

Theory Comput. Syst., 2016

Bicovering: Covering edges with two small subsets of vertices.

[BibT_eX]

[DOI]

Electron. Colloquium Comput. Complex., 2016

2015

On set expansion problems and the small set expansion conjecture.

[BibT_eX]

[DOI]

Discret. Appl. Math., 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

Brief Announcement: New Mechanisms for Pairwise Kidney Exchange.

[BibT_eX]

[DOI]

Hossein Efsandiari

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

2014

Matroid Secretary for Regular and Decomposable Matroids.

[BibT_eX]

[DOI]

SIAM J. Comput., 2014

On a Local Protocol for Concurrent File Transfers.

[BibT_eX]

[DOI]

Vahid Liaghat

Theory Comput. Syst., 2014

On the Advantage of Overlapping Clusters for Minimizing Conductance.

[BibT_eX]

[DOI]

Vahab S. Mirrokni

Algorithmica, 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

Steiner Forest Orientation Problems.

[BibT_eX]

[DOI]

Marek Cygan

SIAM J. Discret. Math., 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

Two-stage Robust Network Design with Exponential Scenarios.

[BibT_eX]

[DOI]

Vahab S. Mirrokni

Algorithmica, 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

2012

Approximating fault-tolerant group-Steiner problems.

[BibT_eX]

[DOI]

Theor. Comput. Sci., 2012

The checkpoint problem.

[BibT_eX]

[DOI]

Julián Mestre

Theor. Comput. Sci., 2012

Prize-collecting steiner network problems.

[BibT_eX]

[DOI]

ACM Trans. Algorithms, 2012

Improved approximation algorithms for Directed Steiner Forest.

[BibT_eX]

[DOI]

Moran Feldman

J. Comput. Syst. Sci., 2012

Local Search Algorithms for the Red-Blue Median Problem.

[BibT_eX]

[DOI]

Algorithmica, 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

2011

Approximating some network design problems with node costs.

[BibT_eX]

[DOI]

Theor. Comput. Sci., 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

Approximating Minimum-Power Degree and Connectivity Problems.

[BibT_eX]

[DOI]

Algorithmica, 2011

Network-Design with Degree Constraints.

[BibT_eX]

[DOI]

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

2010

Approximating Maximum Subgraphs without Short Cycles.

[BibT_eX]

[DOI]

Michael Langberg

SIAM J. Discret. Math., 2010

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

[BibT_eX]

[DOI]

SIAM J. Comput., 2010

Budgeted Red-Blue Median and Its Generalizations.

[BibT_eX]

[DOI]

Proceedings of the Algorithms, 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

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

[BibT_eX]

[DOI]

Algorithmica, 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 minimum cost connectivity problems.

[BibT_eX]

[DOI]

Proceedings of the Parameterized complexity and approximation algorithms, 13.12., 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

Tight approximation algorithm for connectivity augmentation problems.

[BibT_eX]

[DOI]

J. Comput. Syst. Sci., 2008

Min Sum Edge Coloring in Multigraphs Via Configuration LP.

[BibT_eX]

[DOI]

Maxim Sviridenko

Proceedings of the Integer Programming and Combinatorial Optimization, 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

Integrality Ratio for Group Steiner Trees and Directed Steiner Trees.

[BibT_eX]

[DOI]

SIAM J. Comput., 2007

Power optimization for connectivity problems.

[BibT_eX]

[DOI]

Vahab S. Mirrokni

Math. Program., 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

Improved results for data migration and open shop scheduling.

[BibT_eX]

[DOI]

ACM Trans. Algorithms, 2006

An improved approximation algorithm for vertex cover with hard capacities.

[BibT_eX]

[DOI]

J. Comput. Syst. Sci., 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

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 (FOCS 2006), 2006

2005

On network design problems: fixed cost flows and the covering steiner problem.

[BibT_eX]

[DOI]

Wolfgang Slany

ACM Trans. Algorithms, 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

A Combinatorial Logarithmic Approximation Algorithm for the Directed Telephone Broadcast Problem.

[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

2004

Hardness of Approximation for Vertex-Connectivity Network Design Problems.

[BibT_eX]

[DOI]

Robert Krauthgamer

James R. Lee

SIAM J. Comput., 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

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

Approximating Node Connectivity Problems via Set Covers.

[BibT_eX]

[DOI]

Algorithmica, 2003

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

[BibT_eX]

[DOI]

Algorithmica, 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

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

An approximation algorithm for the group Steiner problem.

[BibT_eX]

[DOI]

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

2001

Generalized submodular cover problems and applications.

[BibT_eX]

[DOI]

Judit Bar-Ilan

Theor. Comput. Sci., 2001

On Approximating the Achromatic Number.

[BibT_eX]

[DOI]

Robert Krauthgamer

SIAM J. Discret. Math., 2001

On the Hardness of Approximating Spanners.

[BibT_eX]

[DOI]

Algorithmica, 2001

The Dense k-Subgraph Problem.

[BibT_eX]

[DOI]

Uriel Feige

Algorithmica, 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

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

Generating Low-Degree 2-Spanners.

[BibT_eX]

[DOI]

SIAM J. Comput., 1998

Minimum Color Sum of Bipartite Graphs.

[BibT_eX]

[DOI]

J. Algorithms, 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

1995

Approximation Algorithms for Minimum-Time Broadcast.

[BibT_eX]

[DOI]

SIAM J. Discret. Math., 1995

1994

Generating Sparse 2-Spanners.

[BibT_eX]

[DOI]

J. Algorithms, 1994

Traffic-light scheduling on the grid.

[BibT_eX]

[DOI]

Discret. Appl. Math., 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]