AF: Medium: Collaborative Research: Solutions to Planar Optimization Problems

本研究的目的是开发新的算法和算法技术来解决平面网络上的基本优化问题。网络中的许多优化问题被认为是计算困难的；有些甚至很难近似求解。然而，当输入网络被限制为平面时，即当它可以在平面上绘制时，问题通常会变得容易一些，这样就不会有任何边相互交叉。这种平面优化问题的实例出现在几个应用领域，包括路线图中的物流和路线规划，图像处理和计算机视觉，以及VLSI芯片设计。研究人员计划开发算法，通过利用输入网络的平面性来实现更快的运行时间或更好的近似。此外，为了解决在发现一些基础真理时使用优化的问题，研究人员将开发算法，不仅适用于传统的最坏情况输入模型，也适用于存在异常好的种植解决方案的模型；对于这种模型，研究人员希望找到能够产生更准确答案的算法。这项研究可能会发现新的计算技术，其适用性将超越平面网络。在最近的过去，一旦一种技术在平面网络的背景下被开发和理解，它就被推广到更广泛的网络家族。此外，本研究产生的新算法和技术可能使人们能够快速计算出不同应用领域中出现的问题的更好解决方案。例如，这一领域的研究已经对计算机视觉社区产生了影响。进一步的研究有可能是有用的，例如，在网络的设计，路线图的路线规划，图像的处理。

The aim of this research is to develop new algorithms and algorithmictechniques for solving fundamental optimization problems on planarnetworks. Many optimization problems in networks are consideredcomputationally difficult; some are even difficult to solveapproximately. However, problems often become easier when the inputnetwork is restricted to be planar, i.e. when it can be drawn on theplane so that no edges cross each other. Such planar instances ofoptimization problems arise in several application areas, includinglogistics and route planning in road maps, image processing andcomputer vision, and VLSI chip design.The investigators plan to develop algorithms that achieve fasterrunning times or better approximations by exploiting the planarity ofthe input networks. In addition, in order to address the use ofoptimization in the discovery of some ground truth, the investigatorswill develop algorithms not just for the traditional worst-case inputmodel but also for models in which there is an unusually good plantedsolution; for a model of this kind, the investigators expect to findalgorithms that produce even more accurate answers.The research will likely uncover new computational techniques whoseapplicability goes beyond planar networks. In the recent past, once atechnique has been developed and understood in the context of planarnetworks, it has been generalized to apply to broader families ofnetworks.In addition, new algorithms and techniques resulting from thisresearch might enable people to quickly compute better solutions toproblems arising in diverse application areas. For example, researchin this area has already had an impact in the computer visioncommunity. Further research has the potential to be useful, forexample, in the design of networks, the planning of routes in roadmaps, the processing of images.