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

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

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.