Research Interests
Key words: Combinatorial Optimization, Approximation Algorithms, Graph and Network Algorithms, Algorithmic Game Theory, Efficient Implementations
My research broadly focuses on the design of efficient algorithms for problems arising in the area of combinatorial optimization. I am particularly interested in NP-hard optimization problems for whom exact polynomial-time algorithms are unlikely to exist. For such problems, I develop approximation algorithms, i.e., fast algorithms that compute near-optimal solutions to given instances of NP-hard optimization problems.
One example of my current research is my work on connections between algorithmic game theory and combinatorial optimization. Here, I have recently developed a new collusion resistant and truth-revealing cost-sharing mechanism for a game-theoretic version of the Steiner forest problem. Surprisingly, this result has repercussions for the original classical problem: the game-theoretic approach yields new LP relaxations for Steiner trees and forests which are strictly stronger than some prominent classical formulations. Exploiting the strength of these new formulations and extending the approach to other network design problems is subject of my current research.