Algorithms and Complexity
in Combinatorial Optimization

(1977-1997)

Impact: Academic

Chandru’s doctoral dissertation work was in the computational complexity of combinatorial optimization. Theoretical computer scientists and logicians had developed a hierarchy of computation and the focus in the late 70s was on positioning practical engineering design problems on combinatorial and discrete structures in this hierarchical framework. This approach led to many interesting fundamental problems in “algorithmics” i.e., efficient algorithm design and proofs of intractability of problem classes. The breakthroughs in problems like Karmarkar’s linear programming method and resolution of various graph conjectures kept researchers in this field busy through the 80s and early 90s. Chandru’s work in this area remained strongly academic and intellectual. He became a recognized authority and was invited to write handbook chapters and review papers of the field. A recipient of the Presidents medal of INFORMS (2006) (The Institute for Operations Research and the Management Sciences) and the MC Puri Memorial Award of ORSI (Operations Research Society of India) in 2012, Chandru is the President elect of ORSI for the term 2017-19.

·        V. Chandru and  M.R.Rao, Linear Programming, Chapter 31 in  Handbook of Algorithms and Theory of Computing, edited by M.J.Atallah, CRC Press 1999, 31-1 to 31-37.

·        V. Chandru and B.S. Kochar, "Exploring special structures using a variant of Karmarkar's algorithm," Research Memorandum No. 86-10, Purdue University (1986).

·        V.Chandru and M.R.Rao, Combinatorial Optimization: An Integer Programming Perspective,  ACM Computing Surveys, March 1996, pp 55-58

·        V.Chandru, Variable Elimination in Linear Constraints, The Computer Journal No. 5, August 1993, 463-472.