Computational intractability is the absence of provably efficient algorithms to solve a problem. Consider the traveling salesperson problem (TSP): visit a set of cities in an order that will minimize the distance traveled. If one considers only efficient algorithms to solve this problem, then, pessimistically, one can only guarantee a solution that is at most 40% longer than the shortest tour. One should ask whether their instance is really that bad, as often it is not. In fact, many industrial instances of TSP are geographical and are well represented by Euclidean or planar-graph distances. For these instances there are efficient algorithms that will find a tour that is very close to optimal. In practice, heuristics do very well in solving even large instances.
The research under this award will address two limitations of the start-of-the-art: neither the input domain is as perfect as a planar graph, nor the problem definition is as clean as TSP. The PI will design efficient and accurate algorithms for a broader class of low-dimensional domains and problem constraints. This will greatly advance the theoretical understanding of these low-dimensional metrics. The PI will work with practitioners in energy and transportation systems in order to ensure the practicality of her algorithms and promote the design of practical heuristics inspired by these algorithms.
The PI will involve the education and training of high school, undergraduate and graduate students. With high-school students, the PI will develop video lectures on basic algorithmic-design and graph-theoretic concepts suitable to the general public. Undergraduate students will be exposed to graph-theoretic aspects of this research through summer research experiences. The effort will also design course materials for active-learning problem-solving sessions in advanced algorithms classes and develop lecture notes for a graduate course on domain-specific algorithm design.
