Professorship Chalermsook Parinya

Search results

  • 2022

    Approximating k-Edge-Connected Spanning Subgraphs via a Near-Linear Time LP Solver

    Chalermsook, P., Huang, C. C., Nanongkai, D., Saranurak, T., Sukprasert, P. & Yingchareonthawornchai, S., 1 Jul 2022, 49th EATCS International Conference on Automata, Languages, and Programming, ICALP 2022. Bojanczyk, M., Merelli, E. & Woodruff, D. P. (eds.). Schloss Dagstuhl-Leibniz-Zentrum für Informatik, p. 1-20 20 p. 37. (Leibniz International Proceedings in Informatics, LIPIcs; vol. 229).

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

    Open Access
    File
    4 Downloads (Pure)
  • Clustering with Fair-Center Representation: Parameterized Approximation Algorithms and Heuristics

    Thejaswi, S., Gadekar, A., Ordozgoiti, B. & Osadnik, M., 14 Aug 2022, KDD 2022 - Proceedings of the 28th ACM SIGKDD Conference on Knowledge Discovery and Data Mining. ACM, p. 1749-1759 11 p.

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

    Open Access
  • Deterministic Small Vertex Connectivity in Almost Linear Time

    Saranurak, T. & Yingchareonthawornchai, S., 30 Oct 2022, Proceedings of 2022 IEEE 63rd Annual Symposium on Foundations of Computer Science (FOCS). IEEE, p. 789-800

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

    Open Access
    File
    6 Downloads (Pure)
  • Engineering Nearly Linear-Time Algorithms for Small Vertex Connectivity

    Franck, M. & Yingchareonthawornchai, S., 13 Dec 2022, In: ACM Journal of Experimental Algorithmics. 27, p. 1-29 29 p., 4.4.

    Research output: Contribution to journalArticleScientificpeer-review

    Open Access
    File
    5 Downloads (Pure)
  • 2021

    Coloring and maximum weight independent set of rectangles

    Chalermsook, P. & Walczak, B., 2021, ACM-SIAM Symposium on Discrete Algorithms, SODA 2021. Marx, D. (ed.). ACM, p. 860-868 9 p.

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

    Open Access
    8 Citations (Scopus)
  • Engineering Nearly Linear-Time Algorithms for Small Vertex Connectivity

    Franck, M. & Yingchareonthawornchai, S., 1 Jun 2021, 19th International Symposium on Experimental Algorithms, SEA 2021. Coudert, D. & Natale, E. (eds.). Schloss Dagstuhl-Leibniz-Zentrum für Informatik, p. 1:1-1:18 1. (Leibniz International Proceedings in Informatics (LIPIcs); vol. 190).

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

    Open Access
    File
    10 Downloads (Pure)
  • On Minimum Generalized Manhattan Connections

    Antoniadis, A., Capretto, M., Chalermsook, P., Damerius, C., Kling, P., Nölke, L., Obscura Acosta, N. & Spoerhase, J., 2021, Algorithms and Data Structures - 17th International Symposium, WADS 2021, Proceedings. Lubiw, A. & Salavatipour, M. (eds.). p. 85-100 16 p. (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); vol. 12808 LNCS).

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

    Open Access
  • Precision, recall, and sensitivity of monitoring partially synchronous distributed programs

    Nguyen, D., Yingchareonthawornchai, S., Tekken Valapil, V., Kulkarni, S. S. & Demirbas, M., Oct 2021, In: DISTRIBUTED COMPUTING. 34, 5, p. 319-348 30 p.

    Research output: Contribution to journalArticleScientificpeer-review

    Open Access
    File
    13 Downloads (Pure)
  • Vertex Connectivity in Poly-Logarithmic Max-Flows

    Li, J., Nanongkai, D., Panigrahi, D., Saranurak, T. & Yingchareonthawornchai, S., 15 Jun 2021, Proceedings of the 53rd Annual ACM SIGACT Symposium on Theory of Computing. Khuller, S. & Williams, V. V. (eds.). New York, NY, USA: ACM, p. 317–329 13 p. (STOC 2021).

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

    Open Access
    10 Citations (Scopus)
  • Vertex sparsification for edge connectivity

    Chalermsook, P., Das, S., Kook, Y., Laekhanukit, B., Liu, Y. P., Peng, R., Sellke, M. & Vaz, D., 2021, ACM-SIAM Symposium on Discrete Algorithms, SODA 2021. Marx, D. (ed.). ACM, p. 1206-1225 20 p. (Proceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms).

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

    Open Access
    8 Citations (Scopus)
  • 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
    18 Citations (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
    7 Citations (Scopus)
    171 Downloads (Pure)
  • How Many Zeros of a Random Sparse Polynomial Are Real?

    Jindal, G., Pandey, A., Shukla, H. & Zisopoulos, C., 20 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

    Open Access
    1 Citation (Scopus)
  • 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

    Open Access
    File
    9 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 für Informatik, 16 p. 28. (Leibniz International Proceedings in Informatics, LIPIcs; vol. 173).

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

    Open Access
    File
    41 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
    144 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 für Informatik, 21 p. 33. (Leibniz International Proceedings in Informatics, LIPIcs; vol. 176).

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

    Open Access
    File
    1 Citation (Scopus)
    23 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

    Open Access
  • 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
    1 Citation (Scopus)
    117 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
    105 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
    4 Citations (Scopus)
    48 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 für Informatik, 85. (Leibniz international proceedings in informatics; vol. 132).

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

    Open Access
    File
    24 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 für Informatik, 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
    10 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
    14 Citations (Scopus)
    199 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 für Informatik, 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
    4 Citations (Scopus)
    111 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)
    19 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 für Informatik, p. 1-26 (Leibniz International Proceedings in Informatics (LIPIcs)).

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

    Open Access
    File
    36 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
    8 Citations (Scopus)
    113 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). Schloss Dagstuhl-Leibniz-Zentrum für Informatik, 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
    70 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
    3 Citations (Scopus)
    149 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 für Informatik, 8. (Leibniz International Proceedings in Informatics; vol. 116).

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

    Open Access
    File
    4 Citations (Scopus)
    45 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

    6 Citations (Scopus)
  • Co-Bipartite Neighborhood Edge Elimination Orderings

    Jiamjitrak, W. & van Leeuwen, E. J., 1 Aug 2017, In: ELECTRONIC NOTES IN DISCRETE MATHEMATICS. 61, p. 655-661 7 p.

    Research output: Contribution to journalArticleScientificpeer-review

  • 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

    5 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

    55 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

    4 Citations (Scopus)
  • On proportional allocation in hedonic games

    Hoefer, M. & Jiamjitrak, W., 2017, Algorithmic Game Theory - 10th International Symposium, SAGT 2017, Proceedings. p. 307-319 13 p. (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); vol. 10504 LNCS).

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

    6 Citations (Scopus)