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.

2017

2022