Professorship Chalermsook Parinya

Search results

  • 2020

    A Simple Primal-Dual Approximation Algorithm for 2-Edge-Connected Spanning Subgraphs

    Beyer, S., Chimani, M. & Spoerhase, J., 1 Jan 2020, Computing and Combinatorics - 26th International Conference, COCOON 2020, Proceedings. Kim, D., Uma, R. N., Cai, Z. & Lee, D. H. (eds.). p. 347-359 13 p. (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); vol. 12273 LNCS).

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

    Open Access
  • Computing and testing small connectivity in near-linear time and queries via fast local cut algorithms

    Forster, S., Nanongkai, D., Yang, L., Saranurak, T. & Yingchareonthawornchai, S., 1 Jan 2020, 31st Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2020. Chawla, S. (ed.). ACM, p. 2046-2065 20 p.

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

    Open Access
    1 Citation (Scopus)
  • 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
    81 Downloads (Pure)
  • How Many Zeros of a Random Sparse Polynomial Are Real?

    Jindal, G., Pandey, A., Shukla, H. & Zisopoulos, C., 21 Jul 2020, ISSAC 2020 - Proceedings of the 45th International Symposium on Symbolic and Algebraic Computation. Mantzaflaris, A. (ed.). ACM, p. 273-280 8 p.

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

  • Improved learning of k-parities

    Bhattacharyya, A., Gadekar, A. & Rajgopal, N., 6 Nov 2020, In: Theoretical Computer Science. 840, p. 249-256 8 p.

    Research output: Contribution to journalArticleScientificpeer-review

  • 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
    6 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
    40 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
    6 Downloads (Pure)
  • PTAS for Steiner Tree on Map Graphs

    Byrka, J., Lewandowski, M., Meesum, S. M., Spoerhase, J. & Uniyal, S., 2020, LATIN 2020: Theoretical Informatics - 14th Latin American Symposium 2021, Proceedings. Kohayakawa, Y. & Miyazawa, F. K. (eds.). p. 3-14 12 p. (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); vol. 12118 LNCS).

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

  • Worst-case conditional hardness and fast algorithms with random inputs for non-dominated sorting

    Yingchareonthawornchai, S., Roy, P. C., Laekhanukit, B., Torng, E. & Deb, K., 8 Jul 2020, GECCO 2020 Companion - Proceedings of the 2020 Genetic and Evolutionary Computation Conference Companion. ACM, p. 185-186 2 p.

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

    Open Access
    File
    71 Downloads (Pure)
  • 2019

    A deterministic PTAS for the algebraic rank of bounded degree polynomials

    Bhargava, V., Bläser, M., Jindal, G. & Pandey, A., 1 Jan 2019, Proceedings of the Thirtieth Annual ACM-SIAM Symposium on Discrete Algorithms. p. 647-661 15 p.

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

    Open Access
    File
    121 Downloads (Pure)
  • An optimal O(nm) algorithm for enumerating all walks common to all closed edge-covering walks of a graph

    Cairo, M., Medvedev, P., Acosta, N. O., Rizzi, R. & Tomescu, A. I., 1 Jul 2019, In: ACM Transactions on Algorithms. 15, 4, p. 1-17 48.

    Research output: Contribution to journalArticleScientificpeer-review

    Open Access
    File
    1 Citation (Scopus)
    49 Downloads (Pure)
  • A tight approximation for submodular maximization with mixed packing and covering constraints

    Mizrachi, E., Schwartz, R., Spoerhase, J. & Uniyal, S., 1 Jul 2019, 46th International Colloquium on Automata, Languages, and Programming (ICALP 2019). Chatzigiannakis, I., Baier, C., Leonardi, S. & Flocchini, P. (eds.). Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing, 85. (Leibniz international proceedings in informatics; vol. 132).

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

    Open Access
    File
    13 Downloads (Pure)
  • 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)
  • Breaking quadratic time for small vertex connectivity and an approximation scheme

    Nanongkai, D., Saranurak, T. & Yingchareonthawornchai, S., 23 Jun 2019, STOC 2019 - Proceedings of the 51st Annual ACM SIGACT Symposium on Theory of Computing. Charikar, M. & Cohen, E. (eds.). ACM, p. 241-252 12 p. (Proceedings of the Annual ACM Symposium on Theory of Computing).

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

    Open Access
    File
    3 Citations (Scopus)
    98 Downloads (Pure)
  • On the complexity of Compact Set r-Packing

    Gadekar, A., 24 Nov 2019, (Submitted).

    Research output: Working paperScientific

  • On the complexity of symmetric polynomials

    Bläser, M. & Jindal, G., 1 Jan 2019, 10th Innovations in Theoretical Computer Science, ITCS 2019. Blum, A. (ed.). Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing, p. 1-14 47. (Leibniz International Proceedings in Informatics, LIPIcs; vol. 124).

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

    Open Access
    File
    1 Citation (Scopus)
    69 Downloads (Pure)
  • Zip Trees

    Jiamjitrak, W., 2019, (Accepted/In press) In: ACM Transactions on Algorithms.

    Research output: Contribution to journalReview Articlepeer-review

  • 2018

    Approximating node-weighted k-MST on planar graphs

    Byrka, J., Lewandowski, M. & Spoerhase, J., 1 Jan 2018, Approximation and Online Algorithms - 16th International Workshop, WAOA 2018, Revised Selected Papers. Epstein, L. & Erlebach, T. (eds.). p. 87-101 15 p. (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); vol. 11312 LNCS).

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

  • Approximation schemes for geometric coverage problems

    Chaplick, S., De, M., Ravsky, A. & Spoerhase, J., 1 Aug 2018, In: Leibniz international proceedings in informatics. 112, p. 1-15

    Research output: Contribution to journalConference articleScientificpeer-review

    Open Access
    File
    2 Citations (Scopus)
    14 Downloads (Pure)
  • Improved learning of k-parities

    Bhattacharyya, A., Gadekar, A. & Rajgopal, N., 1 Jan 2018, Computing and Combinatorics - 24th International Conference, COCOON 2018, Proceedings. p. 542-553 12 p. (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); vol. 10976 LNCS).

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

    1 Citation (Scopus)
  • 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)
  • Stabbing Rectangles by Line Segments - How Decomposition Reduces the Shallow-Cell Complexity

    Chan, T. M., Dijk, T. C. V., Fleszar, K., Spoerhase, J. & Wolff, A., 2018, 29th International Symposium on Algorithms and Computation (ISAAC 2018). p. 1-13 62. (Leibniz International Proceedings in Informatics (LIPIcs); vol. 123).

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

    Open Access
    File
    3 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)