GOALI: Region Partitioning

目标：区域划分

• 批准号: 0800151
• 负责人: Yinyu Ye
• 金额: $ 31.8万
• 依托单位: Stanford University
• 依托单位国家: 美国
• 项目类别: Standard Grant
• 财政年份: 2008
• 资助国家: 美国
• 起止时间: 2008-07-01 至 2012-06-30
• 项目状态: 已结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=0800151&HistoricalAwards=false
• 关键词: GOALI; Region; Partitioning

This grant funds the development of fast geometric algorithms for dividing a given region into pieces. These algorithms will be developed for a variety of situations where one seeks to partition a region, such as redistricting, drawing organ transplant regions (matches for an organ are first sought within the same region), drawing air traffic control regions (or dynamically adjusting them), and dividing a region among a set of vehicles in order to better surveil/survey the region or serve customers distributed in the region. In each of these applications, the algorithms will seek to satisfy and/or optimize different criteria. Redistricting has the criteria that each district contains the same population and optimizes goals such as competitiveness or compactness. On the other hand, the organ transplant regions should be drawn so that each contains a transplant center and optimizes a combination of efficiency (few organs go to waste) and fairness (people in different regions have roughly equal chances of receiving an organ). In air traffic control we seek to balance and minimize the work load of the air traffic control regions. The goal in the vehicle routing problems is to minimize the time until the region is completely surveyed or all the customers have been served. This grant also funds performance analyses of the developed algorithms in both theory and practice (the algorithms developed for the vehicle problems, for example, will not be optimal since these problems are generalizations of the traveling salesman problem and are thus NP hard).If successful, this research will lead to fairer, more compact legislative and congressional districts; more efficient and fair organ transplant regions; more efficient and load-balanced air traffic control regions; and improvements in logistics and vehicle routing. It will also extend the reach of optimization from algebraic and combinatorial problems to geometric ones. In addition, it will provide a framework and generalize a number of existing problems in computational geometry.

这项赠款资助开发快速几何算法，将给定区域分割成碎片。这些算法将被开发用于各种情况，其中人们试图划分区域，例如重新划分，绘制器官移植区域（首先在同一区域内寻找器官的匹配），绘制空中交通管制区域（或动态调整它们），以及在一组车辆中划分区域，以便更好地监视/调查该区域或为分布在该区域中的客户提供服务。 在这些应用中的每一个中，算法将寻求满足和/或优化不同的标准。 重划选区的标准是每个区包含相同的人口，并优化竞争力或紧凑性等目标。 另一方面，器官移植区域的划分应使每个区域都有一个移植中心，并优化效率（很少有器官被浪费）和公平（不同区域的人接受器官的机会大致相等）的组合。 在航空交通管制方面，我们力求平衡和尽量减少航空交通管制区的工作量。 车辆路径问题的目标是最大限度地减少直到区域被完全勘测或所有客户都被服务的时间。 该基金还资助了对所开发算法在理论和实践方面的性能分析（例如，为车辆问题开发的算法将不是最优的，因为这些问题是旅行推销员问题的推广，因此是NP困难的）。如果成功，这项研究将导致更公平，更紧凑的立法和国会选区;更有效和公平的器官移植区域;空中交通管制区域的效率更高，负荷更平衡;后勤和车辆路线得到改善。 它也将扩大范围的优化从代数和组合问题的几何。 此外，它将提供一个框架，并概括了一些现有的问题，在计算几何。