Combinatorics of Graph Packing and Online Binary Search Trees

Project Details


Real-world optimization problems pose a number of challenges to algorithmic research. For instance, (i) many important problems are believed to be intractable (i.e. NP-hard) and (ii) with the growth of data size, modern applications often require a decision making under incomplete and dynamically changing input data. After several decades of research, some of the most basic problems in these domains have remained poorly understood. Existing algorithmic techniques either have reached their limitation or are inherently tailored to very restrictive special cases. This project attempts to untangle this state of the art and seeks new interplay across multiple areas of algorithms, such as approximation algorithms, online algorithms, FPT algorithms, exponential time algorithms, and data structures. We focus on long-standing open problems that capture the challenges presented in multiple algorithmic areas, such as dynamic optimality conjecture and parameterized cliques.
Short titleChalermsook Parinya AT-palkka
Effective start/end date01/09/201731/08/2022
  • 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
    1 Citation (Scopus)