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

AF：中：协作研究：平面优化问题的解决方案

• 批准号: 0964037
• 负责人: Philip Klein
• 金额: $ 62.5万
• 依托单位: Brown University
• 依托单位国家: 美国
• 项目类别: Standard Grant
• 财政年份: 2010
• 资助国家: 美国
• 起止时间: 2010-08-01 至 2015-06-30
• 项目状态: 已结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=0964037&HistoricalAwards=false
• 关键词: AF; Medium; Collaborative; Research; Solutions

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.

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