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.
Effective start/end date01/09/202031/08/2022

Collaborative partners


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.