PUBLICATIONS
50. The Group Access Bounds for Binary Search Trees
P. Chalermsook, M. Gupta, W. Jiamjitrak, A. Pareek, S. Yingchareonthawornchai
ICALP 2024
We propose a new family of bounds (that generalizes the classical access lemma) for binary search trees. This allows us to "unify" many strong BST bounds that have appeared in the literature under the same framework.
[PDF]
49. Parameterized Approximation for Robust Clustering in Geometric Spaces
F. Abbassi, S. Banerjee, J. Byrka, P. Chalermsook, A. Gadekar, K. Khodamoradi, D. Marx, R. Sharma, J. Spoerhase
ICALP 2024
We show that robust clustering (aka socially fair clustering) becomes more tractable in Euclidean spaces, in contrast to the general metric spaces. In particular, while the Gap-ETH hardness is (3-o(1)) for general metrics, our algorithms can break a factor of 3 in high-dimensional Euclidean spaces. In sub-logarithmic dimension, we present an approximation scheme.
[PDF]
48. Sorting Pattern-Avoiding Permutations via 0-1 Matrices Forbidding Product Patterns
P. Chalermsook, S. Pettie, S. Yingchareonthawornchai
SODA 2024
Improved upper bounds for sorting sequences avoiding a given permutation. The bounds are proved by tight analysis of the density of 0-1 matrices that forbid a certain product pattern.
[PDF]
47. Approximating Sparsest Cuts in Low-Treewidth Graphs via Combinatorial Diameter
P. Chalermsook, M. Kaul, M. Mnich, J. Spoerhase, S. Uniyal, D. Vaz
ACM Transaction on Algorithms (TALG) 2024
We define the notion of combinatorial diameter of a tree decomposition and show that a natural LP rounding gives approximation ratio and running time depending on this diameter.
[PDF]
46. Independent Set in k-Claw-Free Graphs: Conditional Chi-Boundedness and The Power of LP/SDP Relaxations
P. Chalermsook, A. Gadekar, K. Khodamoradi, J. Spoerhase
WAOA 2023
45. Polynomial-time Approximation of Independent Set Parameterized by Treewidth
P. Chalermsook, F. Fomin, T. Hamm, T. Korhonen, J. Nederlof, L. Orgo
ESA 2023
We consider the maximum independent set problem and show that any approximation algorithm with a ``non-trivial'' approximation ratio (as a function of the number of vertices of the input graph G) can be turned into an algorithm achieving almost the same ratio, albeit as a function of the treewidth of G.
[PDF]
44. Parameterized Approximation Schemes for Clustering with General Norm Objectives
F. Abbassi, S. Banerjee, J. Byrka, P. Chalermsook, A. Gadekar, K. Khodamoradi, D. Marx, R. Sharma, J. Spoerhase
FOCS 2023
We give a clean and simple approximation scheme for clustering problems. Our algorithm (despite being oblivious to the input structures and objective functions) handles almost all known clustering objectives as well as multiple metric spaces.
[PDF]
43. Improved Pattern-Avoidance Bounds for Greedy BSTs via Matrix Decomposition
P. Chalermsook, M. Gupta, W. Jiamjitrak, N. Obscura Acosta, A. Pareek, S. Yingchareonthawornchai
SODA 2023
Forbidden submatrix theory (more generally extremal combinatorics techniques) has been used as a potential by-pass for the design of potential function (for which we lack systematic understanding). This paper shows how to better harness the power of extremal combinatorics in analyzing binary search trees by a careful decomposition of execution logs of BSTs.
[PDF]
42. Approximating k-Edge Connected Spanning Subgraphs via a Near-Linear Time LP Solver
P. Chalermsook, C. Huang, D. Nanongkai, T. Saranurak, P. Sukprasert, S. Yingchareonthawornchai
ICALP 2022
A near-linear-time LP solver for the standard covering LP for k-ECSS is presented. This leads to a fast algorithm for (2+epsilon)-approximating k-ECSS in time O(m+(kn)^1.5). The previous best 2-approximation in time O(mnk) was presented in 1990 by Khuller & Vishkin.
[PDF]
41. On Minimum Generalized Manhattan Connections
A. Antoniadis, M. Capretto, P. Chalermsook, C. Damerius, P. Kling, L. Nölke, N. Obscura Acosta and J. Spoerhase
WADS 2021
We introduced a new combinatorial problem that connects three distinct areas: data structures, geometry, and approximation algorithms. Our problem generalizes the minimum cost binary search trees, is a node-weighted variant of Manhattan Network, and is a special case of node-weighted Steiner forests.
[PDF]
40. Coloring and Maximum Weight Independent Set of Rectangles
P. Chalermsook and B. Walczak
SODA 2021
Invited to TALG Special Issues
We show that any rectangle graphs are O(q log q) colorable where q = maximum clique size. This is the first asymptotic improvement over the six-decade-old bound by Asplund and Grunbaum in 1960.
[PDF]
39. Vertex Sparsification for Edge Connectivity
P. Chalermsook, S. Das, B. Laekhanukit, Y. Kook, YP Liu, R. Peng, M. Sellke, D. Vaz
SODA 2021
We initiated the study of parameterized variants of mimicking networks (roughly, a graph that preserves all cut structures among the designated "terminals"). We presented two applications.
[PDF]
38. New Binary Search Tree Bounds via Geometric Inversions
P. Chalermsook, W. Jiamjitrak
ESA 2020
We proposed a new potential function based on counting inversions in binary search trees. We use our potential function to derive old and new bounds.
[PDF]
37. Pinning Down the Strong Wilber 1 Bound for Binary Search Trees
P. Chalermsook, J. Chuzhoy, T. Saranurak
APPROX 2020
Theory of Computing (Toc) 2023 (special issues)
We present geometric approximation algorithms and lower bounds for finding a minimum cost binary search tree. Our main results (i) confirm the gap of O(log log n) between the Wilber's alternation bound and OPT, and (ii) present the first sub-exponential time constant approximation for the problem.
[PDF]
36. On Finding Balanced Bicliques via Matchings
P.Chalermsook, W. Jiamjitrak, L. Orgo
WG 2020
The first approximation algorithm for balanced bicliques with approximation guarantee beyond "enumeration".
35. Multi-transversal for Triangles and the Tuza conjecture
P. Chalermsook, S. Khuller, P. Sukprasert, S. Uniyal
SODA 2020
The Tuza conjecture postulates that the duality ratio between transversal size and triangle packing is at most 2 in any graph. We show an algorithmic proof of a relaxed statement. The duality ratio is bounded by a local-search type argument.
[PDF]
34. A Tight Extremal Bound on the Lovasz Cactus Number in Planar Graphs
P. Chalermsook, A. Schmid, S. Uniyal
STACS 2019
We show that any plane graph contains a cactus subgraph that captures 1/6 fraction of the triangular faces. An immediate application is a 4/9 approximation algorithm for finding the maximum planar subgraph .
[PDF]
33. New Tools and Connections for Exponential-Time Approximation
N.Bansal, P.Chalermsook, B. Laekhanukit, D. Nanongkai, J. Nederlof
Algorithmica, 2019
We consider some central NP-hard optimization problems (independent set, vertex cover, coloring) in the exponential-time approximation setting. We show the first sets of algorithms that perform better than the brute-force results and discuss the connections with PCP parameters.
[PDF]
32. Multi-finger Binary Search Trees
P. Chalermsook, M. Goswami, L. Kozma, K. Mehlhorn, T. Saranurak
ISAAC 2018
We show how to simulate the binary search trees (BST) with multiple finger in the standard BST model with a near-optmal loss. We also illustrate the power and limitations of the multi-finger model.
[PDF]
31. Survivable Network Design for Group Connectivity in Low-Treewidth Graphs
P. Chalermsook, G. Even, S. Das, B. Laekhanukit, D. Vaz
APPROX 2018
We give algorithms for various survivable network design problems in the low-treewidth setting.
[PDF]
30. From Gap-ETH to FPT Inapproximability: Cliques, Dominating Set, and More.
P. Chalermsook, M. Cygan, G. Kortsarz, B. Laekhanukit, P. Manurangsi, D. Nanongkai, L. Trevisan.
FOCS 2017 &
SIAM JOURNAL ON COMPUTING (2020)
Invited to Highlight of Algorithms (HALG) 2018
We illustrate the use of Gap Exponential-Time Hypothesis (Gap-ETH) in proving parameterized inapproximability.
[PDF]
29. Finding Triangles for Maximum Planar Subgraphs
P. Chalermsook, A. Schmid
WALCOM 2017
28. Beyond Metric Embedding: Approximating Group Steiner Trees on Bounded Treewidth Graphs
P. Chalermsook, S. Das, B. Laekhanukit, D.Vaz
SODA 2017
27. Submodular Unsplitable Flow on Trees
A. Adamaszek, P. Chalermsook, A. Ene, A. Wiese
IPCO 2016 &
MATHEMATICAL PROGRAMMING (special issues, 2018) .
26. New Integrality Gap Results for the Firefighters Problem on Trees.
P. Chalermsook and D. Vaz
WAOA 2016
25. A Note on Fractional Coloring and the Integrality gap of LP for Maximum Weight Independent Set.
P. Chalermsook and D. Vaz
CTW 2016
24. Pattern Avoiding Access in Binary Search Trees.
P. Chalermsook, M. Goswami, L. Kozma, K. Mehlhorn, T. Saranurak.
FOCS 2015
23. Self-adjusting Binary Search Trees: What makes them ticks?
P. Chalermsook, M. Goswami, L. Kozma, K. Mehlhorn, T. Saranurak.
ESA 2015
22. Two Lower Bounds for Shortest Double-Base Number Systems
P. Chalermsook, H. Imai, and V. Suppakitpaisarn
IEICE Transactions on Fundamentals of Electronics, Communications and Computer Sciences, Vol. E98-A, No. 6, pages 1310-1312, 2015
21. On guillotine cutting sequences
F. Abed, P. Chalermsook, J. Correa, A. Karrenbauer, P. Perez-Lantero, J. Soto, A. Wiese
APPROX 2015
20. How to Tame Rectangles: Solving Independent Set and Coloring of Rectangles via Shrinking
A. Adamaszek, P. Chalermsook, and A. Wiese
APPROX 2015
19. On Survivable Set Connectivity.
P. Chalermsook, F. Grandoni, B. Laekhanukit.
SODA 2015
18. Social Network Monetization via Sponsored Viral Marketing
P. Chalermsook, A. Lall, A. Das Sarma, D. Nanongkai
SIGMETRICS 2015
17. Greedy Is an Almost Optimal Deque
P. Chalermsook, M. Goswami, L. Kozma, K. Mehlhorn, and T. Saranurak
WADS 2015
16. Pre-Reduction Graph Products: Hardnesses of Properly Learning DFAs and Approximating EDP on DAGs
(with B. Laekhanukit and D. Nanongkai)
FOCS 2014
15. Nearly Tight Approximability Results for Minimum Biclique Cover and Partition
(With S. Heydrich, E. Holm, and A. Karrenbauer)
ESA 2014
[bug alert] It was pointed out to us, thanks Denis, that our hardness results on biclique partition contain a serious flaw. Therefore, the approximability of this very nice problem remains open. The hardness of biclique cover in the paper is correct.
14. New Approximability Results for the Robust k-median Problem
(With S. Bhattachaya, K. Mehlhorn, and Adrian Neumann)
SWAT 2014
13. Coloring Graph Powers: Graph Product Bounds and Hardness of Approximation
(with B. Laekhanukit and D. Nanongkai)
LATIN 2014
(With B. Laekhanukit and D. Nanongkai)
FOCS 2013
11. Clustering with Center Constraints.
(With S. Venkatasubramanian)
FSTTCS 2013
10. Graph Products Revisited: Tight Approximation Hardness of Induced Matching, Poset Dimension, and More. [Full version]
(With B. Laekhanukit and D. Nanongkai)
SODA 2013
9. Graph Pricing Problem on Bounded Treewidth, Bounded Genus, and k-partite graphs
(With S. Kintali, R. Lipton, and D. Nanongkai)
Chicago Journal of Theoretical Computer Science, 2013.
8. Approximation Algorithms and Hardness of Integral Concurrent Flow [Full version]
(With J. Chuzhoy, A. Ene, and S. Li)
STOC 2012
7. Improved Hardness Results for Profit Maximization Pricing Problems with Unlimited Supply [Full version]
(With J. Chuzhoy, S. Kannan, and S. Khanna)
APPROX 2012
6. Coloring and Maximum Independent Set of Rectangles
APPROX 2011
5. Improved Hardness of Approximation for Stackelberg Shortest-path Pricing
(With P. Briest, S. Khanna, B. Laekhanukit, and D. Nanongkai)
WINE 2010 (short paper)
4. Resource Minimization for Fire Containment
(With J. Chuzhoy)
SODA 2010
3. Maximum Independent Set of Rectangles
(With J. Chuzhoy)
SODA 2009
2. Simple Distributed Algorithms for Approximating Minimum Steiner Trees
(with J. Fakcharoenphol)
COCOON 2005
1. A Deterministic Near Linear-time Algorithm for Finding Minimum Cuts in Planar Graphs
(with J. Fakcharoenphol and D. Nanongkai)
SODA 2004 (short paper)