Photo of Parinya Chalermsook

Parinya Chalermsook

    • Aalto SCI Computer Science Konemiehentie 2

    20042020

    Research activity per year

    If you made any changes in Pure these will be visible here soon.

    Search results

    • 2020

      From gap-exponential time hypothesis to fixed parameter tractable inapproximability: Clique, dominating set, and more

      Chalermsook, P., Cygan, M., Kortsarz, G., Laekhanukit, B., Manurangsi, P., Nanongkai, D. & Trevisan, L., 2020, In: SIAM JOURNAL ON COMPUTING. 49, 4, p. 772-810 39 p.

      Research output: Contribution to journalArticleScientificpeer-review

      Open Access
      File
      82 Downloads (Pure)
    • Multi-transversals for Triangles and the Tuza's Conjecture

      Chalermsook, P., Khuller, S., Sukprasert, P. & Uniyal, S., 2020, PROCEEDINGS OF THE THIRTY-FIRST ANNUAL ACM-SIAM SYMPOSIUM ON DISCRETE ALGORITHMS (SODA'20). p. 1955-1974 20 p.

      Research output: Chapter in Book/Report/Conference proceedingConference contributionScientificpeer-review

      Open Access
    • New binary search tree bounds via geometric inversions

      Chalermsook, P. & Jiamjitrak, W. P., 1 Aug 2020, 28th Annual European Symposium on Algorithms, ESA 2020. Grandoni, F., Herman, G. & Sanders, P. (eds.). Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing, 16 p. 28. (Leibniz International Proceedings in Informatics, LIPIcs; vol. 173).

      Research output: Chapter in Book/Report/Conference proceedingConference contributionScientificpeer-review

      Open Access
      File
      7 Downloads (Pure)
    • On Finding Balanced Bicliques via Matchings

      Chalermsook, P., Jiamjitrak, W. P. & Orgo, L., 2020, Graph-Theoretic Concepts in Computer Science - 46th International Workshop, WG 2020, Revised Selected Papers. Adler, I. & Müller, H. (eds.). p. 238-247 10 p. (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); vol. 12301 LNCS).

      Research output: Chapter in Book/Report/Conference proceedingConference contributionScientificpeer-review

      Open Access
      File
      41 Downloads (Pure)
    • Pinning down the strong wilber 1 bound for binary search trees

      Chalermsook, P., Chuzhoy, J. & Saranurak, T., 1 Aug 2020, Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques, APPROX/RANDOM 2020. Byrka, J. & Meka, R. (eds.). Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing, 21 p. 33. (Leibniz International Proceedings in Informatics, LIPIcs; vol. 176).

      Research output: Chapter in Book/Report/Conference proceedingConference contributionScientificpeer-review

      Open Access
      File
      8 Downloads (Pure)
    • 2019

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

      Chalermsook, P., Schmid, A. & Uniyal, S., 2019, 36th International Symposium on Theoretical Aspects of Computer Science (STACS 2019). Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing, p. 1-14 14 p. 19. (Leibniz international proceedings in informatics; vol. 126).

      Research output: Chapter in Book/Report/Conference proceedingConference contributionScientificpeer-review

      Open Access
      File
      4 Downloads (Pure)
    • 2018

      Multi-finger binary search trees

      Chalermsook, P., Goswami, M., Kozma, L., Mehlhorn, K. & Saranurak, T., 2018, 29th International Symposium on Algorithms and Computation (ISAAC 2018). Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing, p. 1-26 (Leibniz International Proceedings in Informatics (LIPIcs)).

      Research output: Chapter in Book/Report/Conference proceedingConference contributionScientificpeer-review

      Open Access
      File
      27 Downloads (Pure)
    • New Tools and Connections for Exponential-Time Approximation

      Bansal, N., Chalermsook, P., Laekhanukit, B., Nanongkai, D. & Nederlof, J., 2018, In: Algorithmica.

      Research output: Contribution to journalArticleScientificpeer-review

      Open Access
      File
      4 Citations (Scopus)
      121 Downloads (Pure)
    • Submodular unsplittable flow on trees

      Adamaszek, A., Chalermsook, P., Ene, A. & Wiese, A., Nov 2018, In: Mathematical Programming. 172, 1-2, p. 565–589

      Research output: Contribution to journalArticleScientificpeer-review

      Open Access
      File
      1 Citation (Scopus)
      166 Downloads (Pure)
    • Survivable network design for group connectivity in low-treewidth graphs

      Chalermsook, P., Das, S., Even, G., Laekhanukit, B. & Vaz, D., 1 Aug 2018, Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques - 21st International Workshop, APPROX 2018, and 22nd International Workshop, RANDOM 2018. Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing, 8. (Leibniz International Proceedings in Informatics; vol. 116).

      Research output: Chapter in Book/Report/Conference proceedingConference contributionScientificpeer-review

      Open Access
      File
      22 Downloads (Pure)
    • 2017

      Beyond metric embedding: Approximating group steiner trees on bounded treewidth graphs

      Chalermsook, P., Das, S., Laekhanukit, B. & Vaz, D., 2017, 28th Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2017. ACM, p. 737-751 15 p.

      Research output: Chapter in Book/Report/Conference proceedingConference contributionScientificpeer-review

      3 Citations (Scopus)
    • Finding triangles for maximum planar subgraphs

      Chalermsook, P. & Schmid, A., 2017, WALCOM: Algorithms and Computation - 11th International Conference and Workshops, WALCOM 2017, Proceedings. p. 373-384 12 p. (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); vol. 10167 LNCS).

      Research output: Chapter in Book/Report/Conference proceedingConference contributionScientificpeer-review

      4 Citations (Scopus)
    • From Gap-ETH to FPT-Inapproximability: Clique, Dominating Set, and More

      Chalermsook, P., Cygan, M., Kortsarz, G., Laekhanukit, B., Manurangsi, P., Nanongkai, D. & Trevisan, L., 2017, 58th IEEE Annual Symposium on Foundations of Computer Science, FOCS 2017, Berkeley, CA, USA, October 15-17, 2017. p. 743-754 12 p. (Annual Symposium on Foundations of Computer Science).

      Research output: Chapter in Book/Report/Conference proceedingConference contributionScientificpeer-review

      37 Citations (Scopus)
    • New integrality gap results for the firefighters problem on trees

      Chalermsook, P. & Vaz, D., 2017, Approximation and Online Algorithms - 14th International Workshop, WAOA 2016, Revised Selected Papers. Vol. 10138 LNCS. p. 65-77 13 p. (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); vol. 10138 LNCS).

      Research output: Chapter in Book/Report/Conference proceedingConference contributionScientificpeer-review

      3 Citations (Scopus)
    • 2016

      Submodular unsplittable flow on trees

      Adamaszek, A., Chalermsook, P., Ene, A. & Wiese, A., 2016, Integer Programming and Combinatorial Optimization - 18th International Conference, IPCO 2016, Proceedings. Springer Verlag, p. 337-349 13 p. (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); vol. 9682).

      Research output: Chapter in Book/Report/Conference proceedingConference contributionScientificpeer-review

      5 Citations (Scopus)
    • 2015

      Greedy is an almost optimal deque

      Chalermsook, P., Goswami, M., Kozma, L., Mehlhorn, K. & Saranurak, T., 2015, Algorithms and Data Structures - 14th International Symposium, WADS 2015, Proceedings. Springer Verlag, Vol. 9214. p. 152-165 14 p. (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); vol. 9214).

      Research output: Chapter in Book/Report/Conference proceedingConference contributionScientificpeer-review

      1 Citation (Scopus)
    • How to tame rectangles: Solving independent set and coloring of rectangles via shrinking

      Adamaszek, A., Chalermsook, P. & Wiese, A., 1 Aug 2015, Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques - 18th International Workshop, APPROX 2015, and 19th International Workshop, RANDOM 2015. Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing, Vol. 40. p. 43-60 18 p.

      Research output: Chapter in Book/Report/Conference proceedingConference contributionScientificpeer-review

      5 Citations (Scopus)
    • On guillotine cutting sequences

      Abed, F., Chalermsook, P., Correa, J., Karrenbauer, A., Pérez-Lantero, P., Soto, J. A. & Wiese, A., 1 Aug 2015, Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques - 18th International Workshop, APPROX 2015, and 19th International Workshop, RANDOM 2015. Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing, Vol. 40. p. 1-19 19 p.

      Research output: Chapter in Book/Report/Conference proceedingConference contributionScientificpeer-review

      1 Citation (Scopus)
    • On survivable set connectivity

      Chalermsook, P., Grandoni, F. & Laekhanukit, B., 2015, Proceedings of the 26th Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2015. January ed. ACM, Vol. 2015-January. p. 25-36 12 p.

      Research output: Chapter in Book/Report/Conference proceedingConference contributionScientificpeer-review

      5 Citations (Scopus)
    • Pattern-Avoiding Access in Binary Search Trees

      Chalermsook, P., Goswami, M., Kozma, L., Mehlhorn, K. & Saranurak, T., 11 Dec 2015, Proceedings - 2015 IEEE 56th Annual Symposium on Foundations of Computer Science, FOCS 2015. Vol. 2015-December. p. 410-423 14 p. 7354406

      Research output: Chapter in Book/Report/Conference proceedingConference contributionScientificpeer-review

      13 Citations (Scopus)
    • Self-adjusting binary search trees: What makes them tick?

      Chalermsook, P., Goswami, M., Kozma, L., Mehlhorn, K. & Saranurak, T., 2015, Algorithms – ESA 2015 - 23rd Annual European Symposium, Proceedings. Springer Verlag, Vol. 9294. p. 300-312 13 p. (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); vol. 9294).

      Research output: Chapter in Book/Report/Conference proceedingConference contributionScientificpeer-review

      6 Citations (Scopus)
    • Two lower bounds for shortest double-base number system

      Chalermsook, P., Imai, H. & Suppakitpaisarn, V., 1 Jun 2015, In: IEICE TRANSACTIONS ON FUNDAMENTALS OF ELECTRONICS COMMUNICATIONS AND COMPUTER SCIENCES. E98A, 6, p. 1310-1312 3 p.

      Research output: Contribution to journalArticleScientificpeer-review

      3 Citations (Scopus)
    • 2014

      Coloring graph powers: Graph product bounds and hardness of approximation

      Chalermsook, P., Laekhanukit, B. & Nanongkai, D., 2014, LATIN 2014: Theoretical Informatics - 11th Latin American Symposium, Proceedings. Springer Verlag, Vol. 8392 LNCS. p. 409-420 12 p. (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); vol. 8392 LNCS).

      Research output: Chapter in Book/Report/Conference proceedingConference contributionScientificpeer-review

      4 Citations (Scopus)
    • Nearly tight approximability results for minimum biclique cover and partition

      Chalermsook, P., Heydrich, S., Holm, E. & Karrenbauer, A., 2014, Algorithms, ESA 2014 - 22nd Annual European Symposium, Proceedings. Springer Verlag, Vol. 8737 LNCS. p. 235-246 12 p. (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); vol. 8737 LNCS).

      Research output: Chapter in Book/Report/Conference proceedingConference contributionScientificpeer-review

      10 Citations (Scopus)
    • New approximability results for the robust k-median problem

      Bhattacharya, S., Chalermsook, P., Mehlhorn, K. & Neumann, A., 2014, Algorithm Theory, SWAT 2014 - 14th Scandinavian Symposium and Workshops, Proceedings. Springer Verlag, Vol. 8503 LNCS. p. 50-61 12 p. (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); vol. 8503 LNCS).

      Research output: Chapter in Book/Report/Conference proceedingConference contributionScientificpeer-review

      1 Citation (Scopus)
    • Pre-reduction graph products: Hardnesses of properly learning DFAs and approximating EDP on DAGs

      Chalermsook, P., Laekhanukit, B. & Nanongkai, D., 7 Dec 2014, Proceedings - Annual IEEE Symposium on Foundations of Computer Science, FOCS. p. 444-453 10 p. 6979029

      Research output: Chapter in Book/Report/Conference proceedingConference contributionScientificpeer-review

      4 Citations (Scopus)
    • 2013

      Clustering with center constraints

      Chalermsook, P. & Venkatasubramanian, S., 1 Dec 2013, Leibniz International Proceedings in Informatics, LIPIcs. Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing, Vol. 24. p. 401-412 12 p.

      Research output: Chapter in Book/Report/Conference proceedingConference contributionScientificpeer-review

    • Graph products revisited: Tight approximation hardness of induced matching, poset dimension and more

      Chalermsook, P., Laekhanukit, B. & Nanongkai, D., 2013, Proceedings of the 24th Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2013. p. 1557-1576 20 p.

      Research output: Chapter in Book/Report/Conference proceedingConference contributionScientificpeer-review

      34 Citations (Scopus)
    • Independent set, induced matching, and pricing: Connections and tight (subexponential time) approximation hardnesses

      Chalermsook, P., Laekhanukit, B. & Nanongkai, D., 2013, Proceedings - 2013 IEEE 54th Annual Symposium on Foundations of Computer Science, FOCS 2013. p. 370-379 10 p. 6686173

      Research output: Chapter in Book/Report/Conference proceedingConference contributionScientificpeer-review

      37 Citations (Scopus)
    • 2012

      Approximation algorithms and hardness of integral concurrent flow

      Chalermsook, P., Chuzhoy, J., Ene, A. & Li, S., 2012, STOC '12 - Proceedings of the 2012 ACM Symposium on Theory of Computing. p. 689-708 20 p.

      Research output: Chapter in Book/Report/Conference proceedingConference contributionScientificpeer-review

      5 Citations (Scopus)
    • Improved hardness results for profit maximization pricing problems with unlimited supply

      Chalermsook, P., Chuzhoy, J., Kannan, S. & Khanna, S., 2012, Approximation, Randomization, and Combinatorial Optimization: Algorithms and Techniques - 15th International Workshop, APPROX 2012, and 16th International Workshop, RANDOM 2012, Proceedings. Vol. 7408 LNCS. p. 73-84 12 p. (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); vol. 7408 LNCS).

      Research output: Chapter in Book/Report/Conference proceedingConference contributionScientificpeer-review

      32 Citations (Scopus)
    • 2011

      Coloring and maximum independent set of rectangles

      Chalermsook, P., 2011, Approximation, Randomization, and Combinatorial Optimization: Algorithms and Techniques - 14th International Workshop, APPROX 2011 and 15th International Workshop, RANDOM 2011, Proceedings. Vol. 6845 LNCS. p. 123-134 12 p. (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); vol. 6845 LNCS).

      Research output: Chapter in Book/Report/Conference proceedingConference contributionScientificpeer-review

      10 Citations (Scopus)
    • 2010

      Improved hardness of approximation for Stackelberg shortest-path pricing

      Briest, P., Chalermsook, P., Khanna, S., Laekhanukit, B. & Nanongkai, D., 2010, Internet and Network Economics - 6th International Workshop, WINE 2010, Proceedings. Vol. 6484 LNCS. p. 444-454 11 p. (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); vol. 6484 LNCS).

      Research output: Chapter in Book/Report/Conference proceedingConference contributionScientificpeer-review

      12 Citations (Scopus)
    • Resource minimization for fire containment

      Chalermsook, P. & Chuzhoy, J., 2010, Proceedings of the 21st Annual ACM-SIAM Symposium on Discrete Algorithms. p. 1334-1349 16 p.

      Research output: Chapter in Book/Report/Conference proceedingConference contributionScientificpeer-review

      18 Citations (Scopus)
    • 2009

      Maximum independent set of rectangles

      Chalermsook, P. & Chuzhoy, J., 2009, Proceedings of the 20th Annual ACM-SIAM Symposium on Discrete Algorithms. p. 892-901 10 p.

      Research output: Chapter in Book/Report/Conference proceedingConference contributionScientificpeer-review

      72 Citations (Scopus)
    • 2005

      Simple distributed algorithms for approximating minimum steiner trees

      Chalermsook, P. & Fakcharoenphol, J., 2005, In: Lecture Notes in Computer Science. 3595, p. 380-389 10 p.

      Research output: Contribution to journalArticleScientificpeer-review

      15 Citations (Scopus)
    • 2004

      A deterministic near-linear time algorithm for finding minimum cuts in planar graphs

      Chalermsook, P., Fakcharoenphol, J. & Nanongkai, D., 2004, Proceedings of the Fifteenth Annual ACM-SIAM Symposium on Discrete Algorithms. Vol. 15. p. 821-822 2 p.

      Research output: Chapter in Book/Report/Conference proceedingConference contributionScientificpeer-review

      23 Citations (Scopus)
    Your message has successfully been sent.
    Your message was not sent due to an error.