Bi-Criteria Optimization, Geometric Location & Related Problems

点击翻译按钮获取中文摘要

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.