Bundit Laekhanukit

Oper. Res. Lett., May, 2023

Simple Combinatorial Construction of the ko(1)-Lower Bound for Approximating the Parameterized k-Clique.

[BibT_eX]

[DOI]

CoRR, 2023

2022

On Approximating Degree-Bounded Network Design Problems.

[BibT_eX]

[DOI]

Algorithmica, 2022

On the Approximability of the Traveling Salesman Problem with Line Neighborhoods.

[BibT_eX]

[DOI]

Proceedings of the 18th Scandinavian Symposium and Workshops on Algorithm Theory, 2022

Polynomial Integrality Gap of Flow LP for Directed Steiner Tree.

[BibT_eX]

[DOI]

Shi Li

Sorrachai Yingchareonthawornchai

Proceedings of the 2022 ACM-SIAM Symposium on Discrete Algorithms, 2022

Almost Tight Approximation Hardness for Single-Source Directed k-Edge-Connectivity.

[BibT_eX]

[DOI]

Proceedings of the 49th International Colloquium on Automata, Languages, and Programming, 2022

Survivable Network Design Revisited: Group-Connectivity.

[BibT_eX]

[DOI]

Proceedings of the 63rd IEEE Annual Symposium on Foundations of Computer Science, 2022

2021

Vertex Sparsification for Edge Connectivity.

[BibT_eX]

[DOI]

Proceedings of the 2021 ACM-SIAM Symposium on Discrete Algorithms, 2021

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

Worst-case conditional hardness and fast algorithms with random inputs for non-dominated sorting.

[BibT_eX]

[DOI]

Proceedings of the GECCO '20: Genetic and Evolutionary Computation Conference, 2020

Polylogarithmic Approximation Algorithm for k-Connected Directed Steiner Tree on Quasi-Bipartite Graphs.

[BibT_eX]

[DOI]

Proceedings of the Approximation, 2020

2019

On the Complexity of Closest Pair via Polar-Pair of Point-Sets.

[BibT_eX]

[DOI]

Roee David

Karthik C. S.

SIAM J. Discret. Math., 2019

On the Parameterized Complexity of Approximating Dominating Set.

[BibT_eX]

[DOI]

Karthik C. S.

Pasin Manurangsi

J. ACM, 2019

Mimicking Networks Parameterized by Connectivity.

[BibT_eX]

[DOI]

CoRR, 2019

Tight Approximation for Variants of Directed Steiner Tree via State-Tree Decomposition and Linear Programming Rounding.

[BibT_eX]

[DOI]

CoRR, 2019

New Tools and Connections for Exponential-Time Approximation.

[BibT_eX]

[DOI]

Algorithmica, 2019

O(log2 k / log log k)-approximation algorithm for directed Steiner tree: a tight quasi-polynomial-time algorithm.

[BibT_eX]

[DOI]

Shi Li

Proceedings of the 51st Annual ACM SIGACT Symposium on Theory of Computing, 2019

2018

O(log2k/log log k)-Approximation Algorithm for Directed Steiner Tree: A Tight Quasi-Polynomial-Time Algorithm.

[BibT_eX]

[DOI]

Shi Li

CoRR, 2018

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

[BibT_eX]

[DOI]

Marek Cygan

Guy Kortsarz

CoRR, 2018

Survivable Network Design for Group Connectivity in Low-Treewidth Graphs.

[BibT_eX]

[DOI]

Proceedings of the Approximation, 2018

2017

Finding All Useless Arcs in Directed Planar Graphs.

[BibT_eX]

[DOI]

Pattara Sukprasert

CoRR, 2017

Surviving in directed graphs: a quasi-polynomial-time polylogarithmic approximation for two-connected directed Steiner tree.

[BibT_eX]

[DOI]

Proceedings of the 49th Annual ACM SIGACT Symposium on Theory of Computing, 2017

Beyond Metric Embedding: Approximating Group Steiner Trees on Bounded Treewidth Graphs.

[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

Surviving in Directed Graphs: A Polylogarithmic Approximation for Two-Connected Directed Steiner Tree.

[BibT_eX]

[DOI]

CoRR, 2016

The Curse of Medium Dimension for Geometric Problems in Almost Every Norm.

[BibT_eX]

[DOI]

Roee David

Karthik C. S.

CoRR, 2016

Approximating Directed Steiner Problems via Tree Embedding.

[BibT_eX]

[DOI]

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

2015

Tree Embedding and Directed Steiner Problems.

[BibT_eX]

[DOI]

CoRR, 2015

An Improved Approximation Algorithm for the Minimum Cost Subset k-Connected Subgraph Problem.

[BibT_eX]

[DOI]

Algorithmica, 2015

On Survivable Set Connectivity.

[BibT_eX]

[DOI]

Proceedings of the Twenty-Sixth Annual ACM-SIAM Symposium on Discrete Algorithms, 2015

2014

Faster Algorithms for Semi-Matching Problems.

[BibT_eX]

[DOI]

ACM Trans. Algorithms, 2014

Approximating Rooted Steiner Networks.

[BibT_eX]

[DOI]

ACM Trans. Algorithms, 2014

Routing Regardless of Network Stability.

[BibT_eX]

[DOI]

Adrian Vetta

Gordon T. Wilfong

Algorithmica, 2014

Parameters of Two-Prover-One-Round Game and The Hardness of Connectivity Problems.

[BibT_eX]

[DOI]

Proceedings of the Twenty-Fifth Annual ACM-SIAM Symposium on Discrete Algorithms, 2014

Coloring Graph Powers: Graph Product Bounds and Hardness of Approximation.

[BibT_eX]

[DOI]

Proceedings of the LATIN 2014: Theoretical Informatics - 11th Latin American Symposium, Montevideo, Uruguay, March 31, 2014

Pre-reduction Graph Products: Hardnesses of Properly Learning DFAs and Approximating EDP on DAGs.

[BibT_eX]

[DOI]

Proceedings of the 55th IEEE Annual Symposium on Foundations of Computer Science, 2014

2013

Approximation Algorithms for Minimum-Cost $k\hbox{-}(S, T)$ Connected Digraphs.

[BibT_eX]

[DOI]

Joseph Cheriyan

SIAM J. Discret. Math., 2013

A bad example for the iterative rounding method for mincost k-connected spanning subgraphs.

[BibT_eX]

[DOI]

Ashkan Aazami

Joseph Cheriyan

Discret. Optim., 2013

Graph Products Revisited: Tight Approximation Hardness of Induced Matching, Poset Dimension and More.

[BibT_eX]

[DOI]

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

Independent Set, Induced Matching, and Pricing: Connections and Tight (Subexponential Time) Approximation Hardnesses.

[BibT_eX]

[DOI]

Proceedings of the 54th Annual IEEE Symposium on Foundations of Computer Science, 2013

2012

An O(log2k)-Approximation Algorithm for the k-Vertex Connected Spanning Subgraph Problem.

[BibT_eX]

[DOI]

SIAM J. Comput., 2012

Non-redistributive Second Welfare Theorems.

[BibT_eX]

[DOI]

Guyslain Naves

Adrian Vetta

Proceedings of the Internet and Network Economics - 8th International Workshop, 2012

A Rounding by Sampling Approach to the Minimum Size k-Arc Connected Subgraph Problem.

[BibT_eX]

[DOI]

Shayan Oveis Gharan

Mohit Singh

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

2011

An Improved Approximation Algorithm for Minimum-Cost Subset k-Connectivity - (Extended Abstract).

[BibT_eX]

[DOI]

Proceedings of the Automata, Languages and Programming - 38th International Colloquium, 2011

2010

Improved Hardness of Approximation for Stackelberg Shortest-Path Pricing.

[BibT_eX]

[DOI]

Proceedings of the Internet and Network Economics - 6th International Workshop, 2010

Faster Algorithms for Semi-matching Problems (Extended Abstract).

[BibT_eX]

[DOI]

Proceedings of the Automata, Languages and Programming, 37th International Colloquium, 2010

2009

Stackelberg Pricing is Hard to Approximate within 2-ε

[BibT_eX]

[DOI]

CoRR, 2009

2008

An o(log2 k)-approximation algorithm for the k-vertex connected spanning subgraph problem.

[BibT_eX]

[DOI]