Ph.D. and Master Theses
M.Eng Thesis (Computer Engineering, Kasetsart University, Thailand): Faster algorithms for optimal semi-matching problems. (originally written in Thai, journal version appears in ACM Trans. Algorithms). M.Math Thesis (Combinatorics and Optimization, University of Waterloo, Canada): Approximation algorithms for (S,T)-connectivity problems. Ph.D. Thesis (Computer Science, McGill University, Canada): Inapproximability of Combinatorial Problems in Subexponential-Time.
Publications
Survivable Network Design Revisited: Group-Connectivity Chao Liao, Qingyun Chen, Bundit Laekhanukit, Yuhao Zhang FOCS 2022 Almost Tight Approximation Hardness for Single-Source Directed k-Edge-Connectivity Chao Liao, Qingyun Chen, Bundit Laekhanukit, Yuhao Zhang ICALP 2022 On the Approximability of the Traveling Salesman Problem with Line Neighborhoods Antonios Antoniadis, Sándor Kisfaludi-Bak, Bundit Laekhanukit, Daniel Vaz SWAT 2022 Polynomial Integrality Gap of Flow LP for Directed Steiner Tree Shi Li, Bundit Laekhanukit SODA 2022 Vertex Sparsification for Edge Connectivity Parinya Chalermsook, Syamantak Das, Yunbum Kook, Bundit Laekhanukit, Yang P. Liu, Richard Peng, Mark Sellke, Daniel Vaz SODA 2021 On a Partition LP Relaxation for Min-Cost 2-Node Connected Spanning Subgraphs Logan Grout, Joseph Cheriyan, Bundit Laekhanukit Unpublished. On Approximating Degree-Bounded Network Design Problems Xiangyu Guo, Guy Kortsarz, Bundit Laekhanukit, Shi Li, Daniel Vaz, Jiayi Xian APPROX 2020 Journal version: Algorithmica 84(5): 1252-1278 (2022) Worst-case conditional hardness and fast algorithms with random inputs for non-dominated sorting Sorrachai Yingchareonthawornchai, Proteek Chandan Roy, Bundit Laekhanukit, Eric Torng, Kalyanmoy Deb GECCO 2020 Polylogarithmic Approximation Algorithm for k-Connected Directed Steiner Tree on Quasi-Bipartite Graphs Chun-Hsiang Chan, Bundit Laekhanukit, Hao-Ting Wei, Yuhao Zhang APPROX 2020 New Tools and Connections for Exponential-Time Approximation Nikhil Bansal, Parinya Chalermsook, Bundit Laekhanukit, Danupon Nanongkai, Jesper Nederlof Algorithmica Special Issue for IPEC'17 2019 O(log2 k / log log k)-approximation algorithm for directed Steiner tree: a tight quasi-polynomial-time algorithm Fabrizio Grandoni, Bundit Laekhanukit, Shi Li STOC 2019 Journal version: SIAM J. Comput. special issue for STOC 2019 Survivable Network Design for Group Connectivity in Low-Treewidth Graphs Parinya Chalermsook, Syamantak Das, Guy Even, Bundit Laekhanukit, Daniel Vaz APPROX 2018 On the Complexity of Closest Pair via Polar-Pair of Point-Sets Roee David, Karthik C.S., Bundit Laekhanukit SoCG 2018 Journal version: SIAM J. Discret. Math. 33(1): 509-527 (2019) On the parameterized complexity of approximating dominating set Karthik C.S., Bundit Laekhanukit, Pasin Manurangsi STOC 2018 Journal version: J. ACM 66(5): 33:1-33:38 (2019) From Gap-ETH to FPT-Inapproximability: Clique, Dominating Set, and More Parinya Chalermsook, Marek Cygan, Guy Kortsarz, Bundit Laekhanukit, Pasin Manurangsi, Danupon Nanongkai, Luca Trevisan FOCS 2017 Journal version: SIAM J. Comput. 49(4): 772-810 (2020) Surviving in directed graphs: a quasi-polynomial-time polylogarithmic approximation for two-connected directed Steiner tree Fabrizio Grandoni, Bundit Laekhanukit STOC 2017 Approximating Spanners and Directed Steiner Forest: Upper and Lower Bounds Eden Chlamtáč, Michael Dinitz, Guy Kortsarz, Bundit Laekhanukit SODA 2017 Journal version: ACM Trans. Algorithms 16(3): 33 (2014) Beyond Metric Embedding: Approximating Group Steiner Trees on Bounded Treewidth Graphs Parinya Chalermsook, Syamantak Das, Bundit Laekhanukit, Daniel Vaz SODA 2017 Approximating Directed Steiner Problems via Tree Embedding Bundit Laekhanukit ICALP 2016 On Survivable Set Connectivity Parinya Chalermsook, Fabrizio Grandoni, Bundit Laekhanukit SODA 2015 Pre-Reduction Graph Products: Hardnesses of Properly Learning DFAs and Approximating EDP on DAGs Parinya Chalermsook, Bundit Laekhanukit, Danupon Nanongkai FOCS 2014 Coloring Graph Powers: Graph Product Bounds and Hardness of Approximation Parinya Chalermsook, Bundit Laekhanukit, Danupon Nanongkai LATIN 2014 Parameters of Two-Prover-One-Round Game and The Hardness of Connectivity Problems Bundit Laekhanukit SODA 2014 Independent Set, Induced Matching, and Pricing: Connections and Tight (Subexponential Time) Approximation Hardnesses Parinya Chalermsook, Bundit Laekhanukit, Danupon Nanongkai FOCS 2013 Graph Products Revisited: Tight Approximation Hardness of Induced Matching, Poset Dimension and More Parinya Chalermsook, Bundit Laekhanukit, Danupon Nanongkai SODA 2013 A bad example for the iterative rounding method for mincost k-connected spanning subgraphs Ashkan Aazami, Joseph Cheriyan, Bundit Laekhanukit Discret. Optim. 2013 Approximation Algorithms for Minimum-Cost (S,T)-Connected Digraphs Joseph Cheriyan, Bundit Laekhanukit SIAM J. Discret. Math. 2013 Non-redistributive Second Welfare Theorems Bundit Laekhanukit, Guyslain Naves, Adrian Vetta WINE 2012 Routing Regardless of Network Stability Bundit Laekhanukit, Adrian Vetta, Gordon T. Wilfong ESA 2012 Journal version: Algorithmica 70(3): 561-593 (2014) (ESA special issue) A Rounding by Sampling Approach to the Minimum Size k-Arc Connected Subgraph Problem Bundit Laekhanukit, Shayan Oveis Gharan, Mohit Singh ICALP 2012 Approximating rooted Steiner networks Joseph Cheriyan, Bundit Laekhanukit, Guyslain Naves, Adrian Vetta SODA 2012 Journal version: ACM Transactions on Algorithms 11(2): 8 (2014) An Improved Approximation Algorithm for Minimum-Cost Subset k-Connectivity Bundit Laekhanukit ICALP 2011 Journal version: Algorithmica 72(3): 714-733 (2015) Improved Hardness of Approximation for Stackelberg Shortest-Path Pricing Patrick Briest, Parinya Chalermsook, Sanjeev Khanna, Bundit Laekhanukit, Danupon Nanongkai WINE 2010 Faster Algorithms for Semi-matching Problems Jittat Fakcharoenphol, Bundit Laekhanukit, Danupon Nanongkai ICALP 2010 Journal version: ACM Trans. Algorithms 10(3): 14 (2014) An O(log2 k)-approximation algorithm for the k-vertex connected spanning subgraph problem Jittat Fakcharoenphol, Bundit Laekhanukit STOC 2008 Journal version: SIAM J. Comput. 41-5: 1095-1109 (2012) Detecting and cleaning intruders in sensor network Jittat Fakcharoenphol, Bundit Laekhanukit, Danupon Nanongkai, Poonna Yospanya NCSEC 2004
Unpublished
Finding All Useless Arcs in Directed Planar Graphs J. Fakcharoenphol, B. Laekhanukit and P. Sukprasert Preprint.