Bi-Criteria Optimization, Geometric Location & Related Problems

本项目研究了计算和其他相关领域中出现的优化问题。特别强调双准则优化问题和几何问题。在通信网络中，具有重要实际意义的两个重要标准是通信延迟和总成本。在路径规划布线中，总长度和弯道数是两个重要的准则。研究了两个准则同时存在或按词典顺序排列的最优化问题。其中要研究的是一组点位的加权最远邻Voronoi图的构造，这是一类新的几何问题，称为有能力路径问题，其中障碍物具有容量，并且避免这些障碍物的路径成本是路径长度和路径所经过障碍物容量的函数。以及有多个源-目的地对的路由问题，这些路径不交叉，但它们的总长度要最小化。本研究的目标是应用几何技术来解决这些新的优化问题，并确定可以（或不能）从几何特性中受益的问题。

Optimization problems that arise in computational and other related areas are investigated in this project. Special emphasis is placed on bi-criteria optimization problems and geometric problems. In a communication network, the two important criteria that are of great practical implications are the communication delay and total cost. In path planning routing, the two important criteria are the total length and the number of bends. Optimization problems concerning two criteria either simultaneously or in lexicographical order are studied. Among those to be studied are weighted farthest neighbor Voronoi diagram construction for a set of point sites, a new class of geometric problems, called the capacitated path problem, in which the obstacles have capacities and the cost of a path avoiding these obstacles is a function of the length of the path and the capacities of the obstacles visited by the path, and routing problems with multiple source-destination pairs such that these paths do not cross and yet their total length is to be minimized. The goals of this research are to apply geometric techniques to tackle these new classes of optimization problems, and to identify problems that can (or cannot) benefit from the geometric properties.