If you have any trouble downloading the files (or the files were not there), please feel free to e-mail me!

34. A Tight Extremal Bound on the Lovász Cactus Number in Planar Graphs

P. Chalermsook, A. Schmid, S. Uniyal

STACS 2019

33. Multi-finger Binary Search Trees

P. Chalermsook, M. Goswami, L. Kozma, K. Mehlhorn, T. Saranurak

ISAAC 2018

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

P. Chalermsook, G. Even, S. Das, B. Laekhanukit, D. Vaz


31. New Tools and Connections for Exponential Time Approximation

N.Bansal, P.Chalermsook, B. Laekhanukit, D. Nanongkai, J. Nederlof

Algorithmica, 2018

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

29. Finding Triangles for Maximum Planar Subgraphs

P. Chalermsook, A. Schmid


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

Journal version (special issues): Mathematical Programming (2018). Full version will be posted soon.

26. New Integrality Gap Results for the Firefighters Problem on Trees.

P. Chalermsook and D. Vaz

WAOA 2016

[full version]

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


20. How to Tame Rectangles: Solving Independent Set and Coloring of Rectangles via Shrinking

A. Adamaszek, P. Chalermsook, and A. Wiese


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


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

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

(With B. Laekhanukit and D. Nanongkai)

FOCS 2013

11. Clustering with Center Constraints.

(With S. Venkatasubramanian)


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)


6. Coloring and Maximum Independent Set of Rectangles


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)


1. A Deterministic Near Linear-time Algorithm for Finding Minimum Cuts in Planar Graphs

(with J. Fakcharoenphol and D. Nanongkai)

SODA 2004 (short paper)