Research Interests

I am interested in theoretical computer science with the main emphasis on approximation algorithms and hardness of approximation. Recently, I have also been working on the dynamic optimality conjecture for Binary Search Trees (BST).  

Program committee members: 
  • The 24th European Symposium on Algorithms (ESA 2016)
  • The 36th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2016)
  • The 8th International Conference on Fun with Algorithms (FUN 2016)
  • The 18th International Workshop on Approximation Algorithms for Combinatorial Optimization Problems (APPROX 2015)

Research Papers 

  1. Pattern Avoiding Access in Binary Search Trees.
    P. Chalermsook, M. Goswami, K. Mehlhorn, T. Saranurak. 
    FOCS 2015, to appear 

  2. On guillotine cutting sequences 
    F. Abed, P. Chalermsook, J. Correa, A. Karrenbauer, P. Perez-Lantero, J. Soto, A. Wiese 
    APPROX 2015, to appear.

  3. How to Tame Rectangles: Solving Independent Set and Coloring of Rectangles via Shrinking 
    A. Adamaszek, P. Chalermsook, and A. Wiese 
    APPROX 2015, to appear.

  4. On Survivable Set Connectivity
    P. Chalermsook, F. Grandoni, B. Laekhanukit. 
    SODA 2015

  5. Social Network Monetization via Sponsored Viral Marketing 
    P. Chalermsook, A. Lall, A. Das Sarma, D. Nanongkai

  6. Greedy Is an Almost Optimal Deque
  7. P. Chalermsook, M. Goswami, K. Mehlhorn, L. Kozma and T. Saranurak
    WADS 2015

  8. Pre-Reduction Graph Products: Hardnesses of Properly Learning DFAs and Approximating EDP on DAGs 
    (with B. Laekhanukit and D. Nanongkai) 
    FOCS 2014

  9. Nearly Tight Approximability Results for Minimum Biclique Cover and Partition
    (With S. Heydrich, E. Holm, and A. Karrenbauer) 
    ESA 2014 

  10. New Approximability Results for the Robust k-median Problem 
    (With S. Bhattachaya, K. Mehlhorn, and Adrian Neumann) 
    SWAT 2014 

  11. 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

  13. Clustering with Center Constraints
    (With S. Venkatasubramanian) 
    FSTTCS 2013

  14. Graph Products Revisited: Tight Approximation Hardness of Induced Matching, Poset Dimension, and More. [Full version]
    (With B. Laekhanukit and D. Nanongkai) 
    SODA 2013 

  15. 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.   

  16. Approximation Algorithms and Hardness of Integral Concurrent Flow [Full version]
    (With J. Chuzhoy, A. Ene, and S. Li) 
    STOC 2012

  17. Improved Hardness Results for Profit Maximization Pricing Problems with Unlimited Supply [Full version]
    (With J. Chuzhoy, S. Kannan, and S. Khanna) 
    APPROX 2012

  18. Coloring and Maximum Independent Set of Rectangles
    APPROX 2011

  19. Improved Hardness of Approximation for Stackelberg Shortest-path Pricing 
    (With P. Briest, S. Khanna, B. Laekhanukit, and D. Nanongkai)
    WINE 2010  (short paper) 

  20. Resource Minimization for Fire Containment
    (With J. Chuzhoy) 
    SODA 2010

  21. Maximum Independent Set of Rectangles
    (With J. Chuzhoy)
    SODA 2009 

  22. Simple Distributed Algorithms for Approximating Minimum Steiner Trees
    (with J. Fakcharoenphol)
    COCOON 2005

  23. A Deterministic Near Linear-time Algorithm for Finding Minimum Cuts in Planar Graphs 
    (with J. Fakcharoenphol and D. Nanongkai
    SODA 2004 (short paper)


  1. My scribe note for approximation workshop at Princeton 


  1. Maximum Independent Set of Rectangles 
    School of Computing, U of Utah, UT. October 2012
    IDSIA, Lugano, Switzerland. March 2012
    Theory seminar, Kasetsart University. December 2010 
    UIUC Theory seminar, Champaign, IL. March 2010
    INFORMS, San Diego, CA. October 2009 
    SODA, New York, NY. January 2009 

  2. Approximation Algorithms and Hardness of Integral Concurrent Flow  
    Max-Planck Institute for Informatics, Germany. February 2013
    STOC, NYC, New York. May 2012

    Tokyo DMTCS Seminar, University of Tokyo, Japan. January 2012 
    Kyoto University, Japan. January 2012

  3. Graph Products Revisited 
    Max-Planck Institute for Informatics, Germany. September 2013
    CS Department, U of Chicago, IL. October 2012.
    EPFL, Lausanne, Switzerland. November 2012.  

  4. Independent Set, Induced Matching, and Pricing
    IDSIA, Switzerland. November 2013
    FOCS 2013, Berkeley, CA. October 2013
    University of Utah, UT. September 2013
    Max-Planck Institute for Informatics, Germany. 
    August 2013

  5. Resource Minimization for Fire Containment 
    Max Planck institute for informatics, Saarbrucken, Germany. July 2010 
    U of Chicago theory seminar, Chicago, IL. February 2010 
    SODA, Austin, TX. January 2010

  6. Improved Hardness Results for Profit-Maximization Pricing Problems with Unlimited Supply
    APPROX, Cambridge, MA. August 2012

  7. Coloring and Maximum Independent Set of Rectangles
    APPROX, Princeton, NJ. August 2011

Parinya Chalermsook,
Jun 25, 2015, 11:49 PM
Parinya Chalermsook,
Apr 24, 2012, 5:16 PM
Parinya Chalermsook,
May 19, 2012, 9:24 PM
Parinya Chalermsook,
Oct 10, 2013, 8:14 AM
Parinya Chalermsook,
Apr 18, 2012, 12:46 AM
Parinya Chalermsook,
Oct 21, 2013, 2:25 PM
Parinya Chalermsook,
Aug 2, 2011, 7:59 PM
Parinya Chalermsook,
Oct 4, 2012, 7:15 AM
Parinya Chalermsook,
Dec 31, 2011, 2:08 PM
Parinya Chalermsook,
Jun 20, 2012, 3:08 AM
Parinya Chalermsook,
Jun 16, 2012, 6:33 AM
Parinya Chalermsook,
Jun 28, 2015, 6:28 AM
Parinya Chalermsook,
Apr 17, 2011, 2:53 PM