Dinesh P. Mehta: Research Page
Dinesh P. Mehta
Research Overview

My Research Approach

My research area is in applied algorithms and data structures. An ideal paper consists of formulating an algorithmic problem based on the needs in an application area, developing theory to better characterize the problem, and then exploiting the theory to develop an efficient algorithm. When the problem is inherently intractable, as a lot of real-world problems are, classical algorithmic theory only takes you so far. In these cases, my research involves developing techniques that do well in practice. Sometimes, these solutions find their basis, not in classical algorithmics, but in techniques such as simulated annealing and genetic algorithms or linear/integer programming that arise in other disciplines.

Software that implements the algorithms is then developed and evaluated by running experiments on benchmarks. The performance of the algorithm is judged on run-time and on the quality of the solution it obtains. Thus, my research usually makes both a theoretical and an experimental contribution. My plan is to continue with research along these lines, with specific applications depending on collaboration possibilities. Some of the application areas I have studied relatively recently or am currently studying are listed below.

Cheminformatics.

My initial work in this area was with John Crabtree, who received his PhD in 2007 and is now Professor at the University of North Alabama and more recently with Tina Kouri who received her PhD in 2012 and joined the faculty at the University of South Florida. This work is an interdisciplinary collaboration with Professor Dean in the Department of Chemical and Biological Engineering.

The overall goal of this research is to automate the analysis of large mechanisms that describe the operation of industrial chemical processes. At the heart of this is Automated Reaction Mapping (ARM), a difficult problem rooted in graph-isomorphism (graphs arise in this context because they can be used to model molecular structures). In his dissertation, John developed algorithms for ARM that were published in the ACM Journal of Experimental Algorithms. The algorithms were incorporated into a proof-of-concept software system that also includes a rule-based component to classify chemical reactions. A description of the system appeared in the Journal of Chemical Information and Modeling, a journal of the American Chemical Society. In her dissertation, Tina has developed order-of-magnitude faster solutions for ARM making our algorithms suitable for larger mechanisms (this was presented at the Symposium of Experimental Algorithms) and applied and refined our classifications of reactions to well-established mechanisms based on user feedback from chemical engineers. Our goal is to ultimately create a tool that chemical engineers actually use. Our reaction classification work has appeared in the International Journal of Chemical Kinetics. I am presently considering additional problems arising in cheminformatics with doctoral students JK Slyby and Dheivya Thiagarajan.

Computational Materials.

My work in this area is with Keith Hellman (a PhD candidate in our department), whom I am co-advising with Professor Ciobanu in Mechanical Engineering. Professor Ciobanu has successfully used genetic algorithms in the past to obtain a number of optimal nano-structure configurations. We are seeking to expand the scope and applicability of his optimization techniques by dramatically improving the run-time of the GA code - Keith plans to use a combination of improved system design, parallel computing, and machine learning to enable the GA algorithm to converge faster.

Cyber-Enabled Efficient Management of Structures.

I am a member of an interdisciplinary team that also includes Electrical and Mechanical Engineers that was awarded a $1.4M NSF Cyber-Physical Systems (CPS) grant. The purpose is to use and combine a number of techniques arising in different disciplines to optimize energy usage in buildings given environmental conditions and human activity patterns. I have worked with Daniel Pascua (who received his Masters thesis degree in 2013) and Prof. Szymczak on algorithms and software to deduce human activity patterns in a building from sensor data.

Operations Research with Engineering (ORWE).

I am part of a core group of faculty on campus that is promoting a multi-disciplinary approach to solving optimization problems that arise in Science and Engineering. To this end, we have recently established an interdisciplinary PhD program in ORWE.

Mobile computing.

My work in this area is with Sahar Idwan, who received her PhD in 2005. Sahar's work is on the pursuer-evader problem. This problem enjoyed a resurgence because it was posed as a challenge problem by the DARPA NEST (Network Embedded Software Technology) program. The objective of this research was for the pursuer to capture the evader in minimum time using a minimum number of updates in a road network. Sahar's research involved developing lower bounds and approximation algorithms for the problem, developing probabilistic graph-based algorithms and employing hierarchical graphs to improve computation time. Algorithms were developed using LEDA and were run on several benchmarks including a roadmap of the Denver metropolitan area. This resulted in one journal and three conference publications. Sahar is currently an Associate Professor at Hashemite University in Jordan.

VLSI Floorplanning.

Floorplanning is the placement of large circuit components on a chip to optimize various criteria and is an integral step in the design of modern chips. Most of my more recent work in this area is joint with Yan Feng, who received his PhD in 2004. Yan's research resulted in two publications in IEEE Transactions on CAD and was presented at three conferences. Our contribution was to formulate the floorplanning problem (which has been around for several decades) in a manner that is more suitable to industry (our formulation was developed in collaboration with scientists at Intel) and then solve our version of the problem using a combination of graph- theoretic, geometric and iterative techniques. Our algorithms were implemented and run on established benchmarks. Yan is now at Cadence after a stint at U. Minnesota as a post-doctoral researcher with Prof Sapatnekar.


Send comments & questions to dmehta@mines.edu Disclaimer
Last Modified: July 30, 2014