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-kulut
Effective start/end date01/09/201731/08/2020


Explore the research topics touched on by this project. These labels are generated based on the underlying awards/grants. Together they form a unique fingerprint.
  • 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
    5 Citations (Scopus)