Investigators on Indian Side: Naveen Garg, Sandeep Sen, Amit Kumar, Amitabha Bagchi, Ragesh Jaiswal

Investigators on German Side: Kurt Mehlhorn, Nicole Megow, Julian Mestre, , Khaled Elbassioni, Chien-Chung Huang, Vicenzo Bonifaci, Rob Van Stee

Broad area of research:

The focus of this research group is to design efficient algorithms for NP-hard problems that yield solutions which are provably close to the optimum. The particular problems that we will focus on, as part of IMPECS, are problems arising in scheduling and network design. A typical scenario in scheduling is as follows: jobs arrive over time and a scheduler has to decide which particular machine to schedule a job on so as to improve the overall responsiveness of the system. We consider many different settings - the machines could be heterogeneous, the responsiveness of the system could be measured by the average waiting time or the maximum waiting time, there could be policies preventing scheduling jobs on certain machines etc. For all such settings we design algorithms which are competitive against the best algorithms which knew the future arrival of jobs.

In network design the group will work on problems involving multicommodity flows – multiple commodities have to traverse a network with capacity constraints – and prize collecting versions of various connectivity problems.