Scheduling problems are among the most widely studied class of problems in Computer Science. These problems have applications is several areas, e.g., in large-scale communication networks. There is strong evidence that most kinds of scheduling problems cannot be optimally solved in a reasonable amount of time. However, the question of finding approximately optimal solutions for many kinds of scheduling problems is unresolved. The goal of this research is to develop new techniques to determine which scheduling problems can be solved approximately optimally in a reasonable amount of computing time, and to develop efficient algorithms for the positive examples.
Dr. Gandhi has an excellent record of preparing undergraduates for this kind of research, as well as guiding them in it. This project continues his program of helping students at Rutgers Camden to discover their own potential by working very closely with them -- working on research problems with them, mentoring them, and encouraging their interest in discrete mathematics and algorithms.
We worked on various research problems in the area of coloring, scheduling, and broadcasting. Most of the problems that we worked on are intractable and hence we worked towards obtaining near-optimal solutions to these problems. As an example consider the problem of broadcasting in sensor networks. The objective is to minimize the time at which all nodes receive the message that is broadcast by the source. When a node broadcasts a message all its neighbors can hear the message. The constraint is that for a node to receive a message it must be broadcast by exactly one of its neighbors at any time. For this problem we obtained a solution that is more closer to the optimal than the then best known algorithm. We also worked very closely with students at Rutgers-Camden as well as students from high schools. Until 2009, hardly any students from Rutgers-Camden had gone to graduate school. In the past three years, six students have gone to pursue graduate studies at some of nation's top graduate programs. Inspired by their success several other students at Rutgers-Camden are interested in pursuing gradate studies. We have also been working very closely with high school students - teaching them advanced topics in computer science and involving them in research. During the summer the high school students participate in the Summer Program in Theoretical Computer Science that was started at Rutgers-Camden is now being held at Princeton university with support from the Intractabilty Center. The program runs for seven weeks and students spend seven hours each weekday working on various college level topics in Discrete Mathematics and Algorithms. Some students read research papers and present them. The website for the program is at: http://rajivgandhics.wordpress.com . During the school year we meet with them twice a month on Saturdays to continue studying topics in Theoretical Computer Science.
