CAREER: Understanding and advancing network design in planar domains

计算难解性是指缺少可证明有效的算法来解决问题。考虑旅行推销员问题(TSP)：访问一组城市的顺序将使旅行距离最小化。如果只考虑有效的算法来解决这个问题，那么悲观地说，一个人只能保证一个最多比最短行程长40%的解。人们应该问一问，他们的情况是否真的那么糟糕--通常情况并非如此。事实上，TSP的许多工业实例都是地理上的，并由欧几里得距离或平面图距离很好地表示。对于这些情况，有高效的算法可以找到非常接近最优的路线。在实践中，启发式算法在解决即使是大型实例方面也做得非常好。该奖项下的研究将解决该技术的两个限制：输入域既不像平面图那样完美，问题定义也不像TSP那样清晰。PI将为更广泛类别的低维领域和问题约束设计高效和准确的算法。这将极大地促进对这些低维指标的理论理解。PI将与能源和交通系统的从业者合作，以确保她的算法的实用性，并促进受这些算法启发的实用启发式算法的设计。PI将涉及高中、本科生和研究生的教育和培训。对于高中生，PI将开发适合普通公众的关于基本算法设计和图论概念的视频讲座。本科生将通过暑期研究体验接触到这项研究的图论方面。这项工作还将为高级算法课程中的主动学习解决问题课程设计课程材料，并为特定领域的算法设计研究生课程编写课堂讲稿。

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.