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 wellknown
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:
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: