Bundit Laekhanukit

79 papers A* 18A 1B 2Journal 47Unranked 11
YearRankTypeTitle / Venue / Authors
2025 J jnl
Polynomial Integrality Gap of Flow LP for Directed Steiner Tree.
ACM Trans. Algorithms
Shi Li, Bundit Laekhanukit
2025 — conf
Simple Combinatorial Construction of the
SOSA
Yijia Chen, Yi Feng, Bundit Laekhanukit, Yanlin Liu
2023 J jnl
On a partition LP relaxation for min-cost 2-node connected spanning subgraphs.
Oper. Res. Lett.
Logan Grout, Joseph Cheriyan, Bundit Laekhanukit
2023 J jnl
Simple Combinatorial Construction of the k
CoRR
Yijia Chen, Yi Feng, Bundit Laekhanukit, Yanlin Liu
2022 A* conf
Almost Tight Approximation Hardness for Single-Source Directed k-Edge-Connectivity.
ICALP
Chao Liao, Qingyun Chen, Bundit Laekhanukit, Yuhao Zhang
2022 J jnl
Almost Tight Approximation Hardness for Single-Source Directed k-Edge-Connectivity.
CoRR
Chao Liao, Qingyun Chen, Bundit Laekhanukit, Yuhao Zhang
2022 B ed.
Approximation and Online Algorithms - 20th International Workshop, WAOA 2022, Potsdam, Germany, September 8-9, 2022, Proceedings
WAOA
Parinya Chalermsook, Bundit Laekhanukit
2022 J jnl
On Approximating Degree-Bounded Network Design Problems.
Algorithmica
Xiangyu Guo, Guy Kortsarz, Bundit Laekhanukit, Shi Li, Daniel Vaz, Jiayi Xian
2022 — conf
On the Approximability of the Traveling Salesman Problem with Line Neighborhoods.
SWAT
Antonios Antoniadis, Sándor Kisfaludi-Bak, Bundit Laekhanukit, Daniel Vaz
2022 A* conf
Polynomial Integrality Gap of Flow LP for Directed Steiner Tree.
SODA
Shi Li, Bundit Laekhanukit
2022 A* conf
Survivable Network Design Revisited: Group-Connectivity.
FOCS
Qingyun Chen, Bundit Laekhanukit, Chao Liao, Yuhao Zhang
2022 J jnl
Survivable Network Design Revisited: Group-Connectivity.
CoRR
Qingyun Chen, Bundit Laekhanukit, Chao Liao, Yuhao Zhang
2021 J jnl
On a Partition LP Relaxation for Min-Cost 2-Node Connected Spanning Subgraphs.
CoRR
Logan Grout, Joseph Cheriyan, Bundit Laekhanukit
2021 J jnl
Polynomial Integrality Gap of Flow LP for Directed Steiner Tree.
CoRR
Shi Li, Bundit Laekhanukit
2021 A* conf
Vertex Sparsification for Edge Connectivity.
SODA
Parinya Chalermsook, Syamantak Das, Yunbum Kook, Bundit Laekhanukit, Yang P. Liu, Richard Peng, Mark Sellke, Daniel Vaz
2020 J jnl
Approximating Spanners and Directed Steiner Forest: Upper and Lower Bounds.
ACM Trans. Algorithms
Eden Chlamtác, Michael Dinitz, Guy Kortsarz, Bundit Laekhanukit
2020 J jnl
From Gap-Exponential Time Hypothesis to Fixed Parameter Tractable Inapproximability: Clique, Dominating Set, and More.
SIAM J. Comput.
Parinya Chalermsook, Marek Cygan, Guy Kortsarz, Bundit Laekhanukit, Pasin Manurangsi, Danupon Nanongkai, Luca Trevisan
2020 — conf
On Approximating Degree-Bounded Network Design Problems.
APPROX-RANDOM
Xiangyu Guo, Guy Kortsarz, Bundit Laekhanukit, Shi Li, Daniel Vaz, Jiayi Xian
2020 J jnl
On the Approximability of the Traveling Salesman Problem with Line Neighborhoods.
CoRR
Antonios Antoniadis, Sándor Kisfaludi-Bak, Bundit Laekhanukit, Daniel Vaz
2020 — conf
Polylogarithmic Approximation Algorithm for k-Connected Directed Steiner Tree on Quasi-Bipartite Graphs.
APPROX-RANDOM
Chun-Hsiang Chan, Bundit Laekhanukit, Hao-Ting Wei, Yuhao Zhang
2020 J jnl
Vertex Sparsification for Edge Connectivity.
CoRR
Parinya Chalermsook, Syamantak Das, Bundit Laekhanukit, Yunbum Kook, Yang P. Liu, Richard Peng, Mark Sellke, Daniel Vaz
2020 — conf
Worst-case conditional hardness and fast algorithms with random inputs for non-dominated sorting.
GECCO Companion
Sorrachai Yingchareonthawornchai, Proteek Chandan Roy, Bundit Laekhanukit, Eric Torng, Kalyanmoy Deb
2019 J jnl
$O(\log^2{k}/\log\log{k})$-Approximation Algorithm for Directed Steiner Tree: A Tight Quasi-Polynomial Time Algorithm.
SIAM J. Comput.
Fabrizio Grandoni, Bundit Laekhanukit, Shi Li
2019 J jnl
Mimicking Networks Parameterized by Connectivity.
CoRR
Parinya Chalermsook, Syamantak Das, Bundit Laekhanukit, Daniel Vaz
2019 J jnl
New Tools and Connections for Exponential-Time Approximation.
Algorithmica
Nikhil Bansal, Parinya Chalermsook, Bundit Laekhanukit, Danupon Nanongkai, Jesper Nederlof
2019 J jnl
On the Complexity of Closest Pair via Polar-Pair of Point-Sets.
SIAM J. Discret. Math.
Roee David, Karthik C. S., Bundit Laekhanukit
2019 J jnl
On the Parameterized Complexity of Approximating Dominating Set.
J. ACM
Karthik C. S., Bundit Laekhanukit, Pasin Manurangsi
2019 J jnl
Polylogarithmic Approximation Algorithm for k-Connected Directed Steiner Tree on Quasi-Bipartite Graphs.
CoRR
Chun-Hsiang Chan, Bundit Laekhanukit, Hao-Ting Wei, Yuhao Zhang
2019 J jnl
Tight Approximation for Variants of Directed Steiner Tree via State-Tree Decomposition and Linear Programming Rounding.
CoRR
Xiangyu Guo, Bundit Laekhanukit, Shi Li, Jiayi Xian
2018 J jnl
O(log
CoRR
Fabrizio Grandoni, Bundit Laekhanukit, Shi Li
2018 J jnl
On subexponential running times for approximating directed Steiner tree and related problems.
CoRR
Marek Cygan, Guy Kortsarz, Bundit Laekhanukit
2018 A* conf
On the Complexity of Closest Pair via Polar-Pair of Point-Sets.
SoCG
Roee David, Karthik C. S., Bundit Laekhanukit
2018 A* conf
On the parameterized complexity of approximating dominating set.
STOC
Karthik C. S., Bundit Laekhanukit, Pasin Manurangsi
2018 — conf
Survivable Network Design for Group Connectivity in Low-Treewidth Graphs.
APPROX-RANDOM
Parinya Chalermsook, Syamantak Das, Guy Even, Bundit Laekhanukit, Daniel Vaz
2018 J jnl
Survivable Network Design for Group Connectivity in Low-Treewidth Graphs.
CoRR
Parinya Chalermsook, Syamantak Das, Guy Even, Bundit Laekhanukit, Daniel Vaz
2017 A* conf
Approximating Spanners and Directed Steiner Forest: Upper and Lower Bounds.
SODA
Eden Chlamtác, Michael Dinitz, Guy Kortsarz, Bundit Laekhanukit
2017 A* conf
Beyond Metric Embedding: Approximating Group Steiner Trees on Bounded Treewidth Graphs.
SODA
Parinya Chalermsook, Syamantak Das, Bundit Laekhanukit, Daniel Vaz
2017 J jnl
Finding All Useless Arcs in Directed Planar Graphs.
CoRR
Jittat Fakcharoenphol, Bundit Laekhanukit, Pattara Sukprasert
2017 A* conf
From Gap-ETH to FPT-Inapproximability: Clique, Dominating Set, and More.
FOCS
Parinya Chalermsook, Marek Cygan, Guy Kortsarz, Bundit Laekhanukit, Pasin Manurangsi, Danupon Nanongkai, Luca Trevisan
2017 J jnl
From Gap-ETH to FPT-Inapproximability: Clique, Dominating Set, and More.
CoRR
Parinya Chalermsook, Marek Cygan, Guy Kortsarz, Bundit Laekhanukit, Pasin Manurangsi, Danupon Nanongkai, Luca Trevisan
2017 J jnl
New Tools and Connections for Exponential-time Approximation.
CoRR
Nikhil Bansal, Parinya Chalermsook, Bundit Laekhanukit, Danupon Nanongkai, Jesper Nederlof
2017 J jnl
On the Parameterized Complexity of Approximating Dominating Set.
CoRR
Karthik C. S., Bundit Laekhanukit, Pasin Manurangsi
2017 J jnl
On the Parameterized Complexity of Approximating Dominating Set.
Electron. Colloquium Comput. Complex.
Karthik C. S., Bundit Laekhanukit, Pasin Manurangsi
2017 A* conf
Surviving in directed graphs: a quasi-polynomial-time polylogarithmic approximation for two-connected directed Steiner tree.
STOC
Fabrizio Grandoni, Bundit Laekhanukit
2016 A* conf
Approximating Directed Steiner Problems via Tree Embedding.
ICALP
Bundit Laekhanukit
2016 J jnl
Approximating Spanners and Directed Steiner Forest: Upper and Lower Bounds.
CoRR
Eden Chlamtác, Michael Dinitz, Guy Kortsarz, Bundit Laekhanukit
2016 J jnl
Surviving in Directed Graphs: A Polylogarithmic Approximation for Two-Connected Directed Steiner Tree.
CoRR
Fabrizio Grandoni, Bundit Laekhanukit
2016 J jnl
The Curse of Medium Dimension for Geometric Problems in Almost Every Norm.
CoRR
Roee David, Karthik C. S., Bundit Laekhanukit
2015 J jnl
An Improved Approximation Algorithm for the Minimum Cost Subset k-Connected Subgraph Problem.
Algorithmica
Bundit Laekhanukit
2015 A* conf
On Survivable Set Connectivity.
SODA
Parinya Chalermsook, Fabrizio Grandoni, Bundit Laekhanukit
2015 J jnl
Tree Embedding and Directed Steiner Problems.
CoRR
Bundit Laekhanukit
2014 J jnl
Approximating Rooted Steiner Networks.
ACM Trans. Algorithms
Joseph Cheriyan, Bundit Laekhanukit, Guyslain Naves, Adrian Vetta
2014 B conf
Coloring Graph Powers: Graph Product Bounds and Hardness of Approximation.
LATIN
Parinya Chalermsook, Bundit Laekhanukit, Danupon Nanongkai
2014 J jnl
Faster Algorithms for Semi-Matching Problems.
ACM Trans. Algorithms
Jittat Fakcharoenphol, Bundit Laekhanukit, Danupon Nanongkai
2014 A* conf
Parameters of Two-Prover-One-Round Game and The Hardness of Connectivity Problems.
SODA
Bundit Laekhanukit
2014 J jnl
Pre-Reduction Graph Products: Hardnesses of Properly Learning DFAs and Approximating EDP on DAGs.
CoRR
Parinya Chalermsook, Bundit Laekhanukit, Danupon Nanongkai
2014 A* conf
Pre-reduction Graph Products: Hardnesses of Properly Learning DFAs and Approximating EDP on DAGs.
FOCS
Parinya Chalermsook, Bundit Laekhanukit, Danupon Nanongkai
2014 J jnl
Routing Regardless of Network Stability.
Algorithmica
Bundit Laekhanukit, Adrian Vetta, Gordon T. Wilfong
2013 J jnl
A bad example for the iterative rounding method for mincost k-connected spanning subgraphs.
Discret. Optim.
Ashkan Aazami, Joseph Cheriyan, Bundit Laekhanukit
2013 J jnl
Approximation Algorithms for Minimum-Cost $k\hbox{-}(S, T)$ Connected Digraphs.
SIAM J. Discret. Math.
Joseph Cheriyan, Bundit Laekhanukit
2013 A* conf
Graph Products Revisited: Tight Approximation Hardness of Induced Matching, Poset Dimension and More.
SODA
Parinya Chalermsook, Bundit Laekhanukit, Danupon Nanongkai
2013 A* conf
Independent Set, Induced Matching, and Pricing: Connections and Tight (Subexponential Time) Approximation Hardnesses.
FOCS
Parinya Chalermsook, Bundit Laekhanukit, Danupon Nanongkai
2013 J jnl
Independent Set, Induced Matching, and Pricing: Connections and Tight (Subexponential Time) Approximation Hardnesses.
CoRR
Parinya Chalermsook, Bundit Laekhanukit, Danupon Nanongkai
2012 J jnl
A Rounding by Sampling Approach to the Minimum Size k-Arc Connected Subgraph Problem
CoRR
Bundit Laekhanukit, Shayan Oveis Gharan, Mohit Singh
2012 — conf
A Rounding by Sampling Approach to the Minimum Size k-Arc Connected Subgraph Problem.
ICALP (1)
Bundit Laekhanukit, Shayan Oveis Gharan, Mohit Singh
2012 J jnl
An O(log
SIAM J. Comput.
Jittat Fakcharoenphol, Bundit Laekhanukit
2012 A* conf
Approximating rooted Steiner networks.
SODA
Joseph Cheriyan, Bundit Laekhanukit, Guyslain Naves, Adrian Vetta
2012 J jnl
Graph Products Revisited: Tight Approximation Hardness of Induced Matching, Poset Dimension and More
CoRR
Parinya Chalermsook, Bundit Laekhanukit, Danupon Nanongkai
2012 — conf
Non-redistributive Second Welfare Theorems.
WINE
Bundit Laekhanukit, Guyslain Naves, Adrian Vetta
2012 J jnl
Parameters of Two-Prover-One-Round Game and The Hardness of Connectivity Problems
CoRR
Bundit Laekhanukit
2012 J jnl
Routing Regardless of Network Stability
CoRR
Bundit Laekhanukit, Adrian Vetta, Gordon T. Wilfong
2012 A conf
Routing Regardless of Network Stability.
ESA
Bundit Laekhanukit, Adrian Vetta, Gordon T. Wilfong
2011 — conf
An Improved Approximation Algorithm for Minimum-Cost Subset
ICALP (1)
Bundit Laekhanukit
2011 J jnl
An improved approximation algorithm for the minimum-cost subset k-connected subgraph problem
CoRR
Bundit Laekhanukit
2010 J jnl
Faster Algorithms for Semi-Matching Problems
CoRR
Jittat Fakcharoenphol, Bundit Laekhanukit, Danupon Nanongkai
2010 — conf
Faster Algorithms for Semi-matching Problems (Extended Abstract).
ICALP (1)
Jittat Fakcharoenphol, Bundit Laekhanukit, Danupon Nanongkai
2010 — conf
Improved Hardness of Approximation for Stackelberg Shortest-Path Pricing.
WINE
Patrick Briest, Parinya Chalermsook, Sanjeev Khanna, Bundit Laekhanukit, Danupon Nanongkai
2009 J jnl
Stackelberg Pricing is Hard to Approximate within 2-ε
CoRR
Parinya Chalermsook, Bundit Laekhanukit, Danupon Nanongkai
2008 A* conf
An o(log
STOC
Jittat Fakcharoenphol, Bundit Laekhanukit