Exploiting Planarity in Optimization Algorithms

在优化算法中利用平面性

• 批准号: 0635089
• 负责人: Philip Klein
• 金额: $ 30万
• 依托单位: Brown University
• 依托单位国家: 美国
• 项目类别: Continuing Grant
• 财政年份: 2006
• 资助国家: 美国
• 起止时间: 2006-10-01 至 2010-09-30
• 项目状态: 已结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=0635089&HistoricalAwards=false
• 关键词: Exploiting; Planarity; Optimization; Algorithms

Planar graphs are graphs that can be drawn on the plane with no crossings. Such graphs naturally arise in application areas such as image processing, logistics in road maps, and VLSI. In addressing fundamental optimization problems on graphs, if the input graphs can assumed to be planar, algorithms can be used that are faster and/or more accurate than algorithms that do not require this assumption.This research involves the design and analysis of such planarity-exploiting algorithms for fundamental optimization problems. Advances in this area could lead to improvements in methods for solving problems in road maps such as routing, network design, and facility location, and for solving problems in image processing such as segmentation and tracking.The research consists of two thrusts. The first aims to discover polynomial-time approximation schemes for NP-hard graph problems such as Steiner tree, multiterminal cut, metric labeling, and uncapacitatedfacility location. The approach is to find edge deletions and contractions that approximately preserve the objective while reducing the tree-width of the graph to a small number, then solving the problem optimally in the low-tree-width graph, then lifting the solution to the original graph. The second thrust aims to discover simple and efficient algorithms for some fundamental polynomial-time problems such as flow problems. The approach involves specifying a pivot rule for which the number of iterations of network simplex is small. The algorithm "sweeps" through the graph, analogous to the way a sweep-line algorithm solves a problem in the plane.

平面图是可以在平面上画出的没有交叉的图。 这样的图自然出现在应用领域，如图像处理，道路图中的物流，和超大规模集成电路。在解决图的基本优化问题时，如果输入图可以被假设为平面的，则可以使用比不需要此假设的算法更快和/或更精确的算法。在这一领域的进步可能会导致改进的方法来解决问题的道路地图，如路由，网络设计，设施的位置，并解决问题的图像处理，如分割和tracking.The研究包括两个推力。 第一个目的是发现多项式时间近似计划的NP-硬图问题，如斯坦纳树，多端切割，度量标签，和uncapacitatedfacility位置。该方法是找到边删除和收缩，近似保持目标，同时减少树宽度的图到一个很小的数字，然后最优地解决问题的低树宽度图，然后提升解决方案的原始图。 第二个推力的目的是发现一些基本的多项式时间问题，如流动问题的简单和有效的算法。 该方法涉及到指定一个枢轴规则，网络单纯形的迭代次数是小的。 该算法“扫描”整个图形，类似于扫描线算法解决平面问题的方式。