Our lab designs and analyzes algorithms for complex real-world problems, building on theoretical computer science and discrete mathematics. Beyond finding a single optimal solution, we study the structure of solution spaces to develop frameworks that adapt to uncertainty and change. We also investigate how structural requirements on solutions affect computational complexity.

 

- Structural Analysis of Solution Spaces in Combinatorial Reconfiguration
By defining adjacency relations between solutions, the solution space of combinatorial problems can be viewed as a graph. We analyze properties such as connectivity and diameter of these graphs, and explore the boundary between computational intractability and efficient estimation.

 

- Solution Diversity and Robustness
Real-world decision-making demands multiple high-quality alternatives with distinct properties (diversity) and solutions resilient to changes in assumptions (robustness). We formalize these concepts mathematically and design efficient algorithms to find such solutions.