Award Citation:
Dr Amit Kumar has made outstanding contributions to the design of new models for online problems, and novel algorithms for problems in clustering, scheduling and network design.
Thesis and Guide details:
Details of CSIR Fellowship/ Associateship held, if any or from other sources/ agencies.
Significant foreign assignments:
(a) Significant contributions to science and/ or technology development by the nominee
based on the work done in India during most part of last 5 years:
Amit Kumar’s interests lie in theoretical computer science, with emphasis on designing efficient
algorithms for fundamental problems arising in resource allocation, network design, scheduling and clustering. These problems are often computationally hard, and one needs to design novel heuristics, which are not only efficient, but are provably close to the optimal solution.
Scheduling to minimize average response time of jobs in a heterogeneous processing environment is one of the most well-studied problems in scheduling theory. In the past, Amit has worked on developing new techniques based on linear and convex programming duality for designing and analyzing such algorithms.
In [5], the authors gave the first non-trivial results for the online problem of minimizing the maximum response time of jobs. In a recent breakthrough (cited in 16(g), as the result is new and unpublished), Amit and his co-authors resolved a long standing open problem in scheduling theory (often cited as one of the top 10 problems in theory of scheduling), called weighted flow-time on a single machine. This required finding connections with problems in network design, and using new algorithmic ideas based on dynamic programming.
Network design problems form another class of rich problems with a long history of research.
One of the most well-known problems is the so-called Steiner forest problem, where we are required to connect a set of pairs of terminals in a graph. Although efficient algorithms are known for this problem, they rely on linear programming techniques, and it has been an open problem to design (or analyze known) simple heuristics. This will not only lead to solving more general versions of this problem (e.g., stochastic versions), but hopefully would also lead to better understanding of problems involving higher graph connectivity. Amit, along with his co-authors, gave the first such result in [4], and has recently given local search based algorithms for this problem as well.
Another theme of his research has been designing new models for analyzing online algorithms. In online algorithms, the input arrives over time, and one is required to make decisions without knowing the future.
Traditionally, the theory of competitive analysis measures the performance of an online algorithm by comparing it with algorithms which know the future in advance (so-called off-line algorithms). This often leads to pessimistic results, where it is not clear what would be a good algorithm. He has worked on the model of online algorithms with recourse, where the online algorithm is allowed to slightly change some of the decisions taken in the past. In [3], it is shown that one can get dramatically good improvements on the performance of online algorithms for certain network design problems if it is allowed to make mild changes in the existing solution. These results were extended by Amit and his co-authors to the well known set cover problem [2], and to the online bipartite matching problem. These algorithms require carefully bounding the extent of changes made by an online algorithm in terms of dual solutions for certain linear programming relaxations of these problems. Another model of online algorithms is to allow it to reject a tiny fraction of requests.
(b) Impact of the contributions in the field concerned:
Basic research, his work involves understanding fundamental theoretical problems in his area of research
Places where work of last 5 years has been referred/ cited in Books, Reviews:
Names of the industries in which the technology (ies) has (have) been used :
The achievements already been recognised by Awards by any learned body:
The Awardee a fellow of the Indian National Science Academy/Indian Academy of Sciences/National
Academy of Sciences/Others:
FASC
The Awardee delivered invited lecture(s) in India/abroad and/or chaired any scientific
Internatiional Conference Symposium:
List of Awardee's 10 most significant publications.
List of Awardee's 5 most significant publications during the last 5 years
List of Awardee's 5 most significant publications from out of work done in India
during the last five years:
Complete list of publications in standard refereed journals:
Complete list of publications with foreign collaborators (indicating your status
as author):
List of papers published in Conferences /Symposia/ Seminars, etc:
List of the most outstanding Technical Reports/ Review Articles:
Statement regarding collaboration with scientists abroad:
Total number of patents granted in last five years.
Details of Books published: