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:
Naveen Garg’s contributions are primarily in the design and analysis of approximation algorithms for NP-hard combinatorial optimization problems arising in network design, scheduling, routing, facility location etc. His earlier contributions include extending the celebrated Max-flow min-cut theorem of Ford and Fulkerson to multicommodity flows and developing the primal dual framework to obtain fast approximate solutions for packing and covering linear programs. Over the last few years Naveen has been working on problems arising in “Scheduling” and “Facility Location”, two areas which are important both to the Computer Science and Operations Research communities.
Naveen has been instrumental in introducing tools from linear optimization to the design of online algorithms for job-scheduling problems. [1], now a landmark result in this area, shows how “dual-fitting” - a technique used extensively in the design of Approximation Algorithms - can be adapted to analyze and improve upon algorithms for minimizing weighted flow time. The approach developed in this paper has been extended to a host of other scheduling problems using a variety of stronger formulations such as convex programs, Fenchel duality etc. In [2], Naveen and his coauthors identified a limitation of their approach in [1], and [3] proposes a new model – of rejecting a small fraction of jobs – to analyze the behavior of online algorithms. [3] once again uses techniques from linear optimization to design and analyze the first algorithms for maximum weighted flow time and other related problems. Researchers in the scheduling community continue to build on techniques from [1] and [3] to analyze algorithms for problems which were hitherto considered hopeless; the latest of these is a result on minimizing flow-time when jobs cannot be pre-empted.
On the other hand, facility location problems, especially those involving hard capacity constraints are not amenable to efficient solutions using linear optimization techniques. For over 50 years the method of choice for solving these problems has been “Local Search”, which although easy to describe, tends to be notoriously hard to analyze. In [4] Naveen and his coauthors provide the first tight bound for facility location problems with uniform capacities when the local search step involves the obvious add, delete, swap operations. [5] considers the setting of non-uniform capacities and obtains tight bounds for a similar natural set of local search operations. Both results significantly extend existing analysis techniques for facility location problems and rely on delicate and careful accounting of local search operations.
A common thread that emerges in both these lines of work that Naveen has pursued is the emphasis on analyzing simple, natural, easily implementable algorithms. In facility location this analysis is done through careful book-keeping while for scheduling problems it is achieved using mathematical programming techniques.
(b) Impact of the contributions in the field concerned:
Naveen’s research is theoretical in nature and his contributions would therefore classify as “basic”.
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: