Publications

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

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, to appear  

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

26. New Integrality Gap Results for the Firefighters Problem on Trees. 
P. Chalermsook and D. Vaz
WAOA 2016
[full version
P. Chalermsook and D. Vaz
CTW 2016

24. Pattern Avoiding Access in Binary Search Trees.
P. Chalermsook, M. GoswamiL. Kozma, K. Mehlhorn, T. Saranurak. 
P. Chalermsook, M. GoswamiL. 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

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)
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)

Comments