CAREER: Understanding and advancing network design in planar domains

计算难解性是指缺乏可证明的有效算法来解决问题。考虑一下旅行销售人员问题（TSP）：以最小的旅行距离顺序访问一组城市。如果我们只考虑有效的算法来解决这个问题，那么，悲观地说，我们只能保证解决方案最多比最短行程长40%。人们应该问他们的情况是否真的那么糟糕，因为通常情况并非如此。事实上，TSP的许多工业实例都是地理上的，可以很好地用欧几里得距离或平面距离来表示。对于这些实例，有一些有效的算法可以找到非常接近最优的行程。在实践中，启发式方法在解决大型实例方面做得很好。该奖项下的研究将解决艺术起步的两个限制：输入域既不像平面图那样完美，问题定义也不像TSP那样清晰。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.