CAREER: AF: Algorithms for Facility Location Problems with Uncertainty

设施选址是现实世界中的基本问题，它涉及在某些优化标准下确定设施的最佳位置以“满足”需求。在这个大数据时代，由于数据采集设备误差、测量不准确、采样故障、数据集成误差等因素，采集到的需求数据中不确定性的重要性变得更加明显。由于传感器监测基础设施的广泛部署和技术的日益普及，这一点尤其正确。本项目旨在研究一组面对不确定需求数据的设施选址优化问题，目的是探索新的思路和技术，开发有效的算法来解决不确定数据下的这些优化问题。该研究将结合来自不同领域的各种方法，如离散数学、图论、组合优化、概率论、运筹学、计算几何、数据结构等。该项目将吸引本科生和硕士生参与算法的开发和实施，以提高他们从事理论计算机科学研究的吞吐量，包括继续攻读博士学位。本项目的研究成果将整合到数据结构和算法的几门课程中，这将使具有不同背景的本科生和研究生受益。在这个项目中，将研究三个主题：第一个主题是容错设施位置，以提供对设施故障的保障；第二个主题是彩色设施位置，以定位多种类型的设施；第三个主题是邻近连接的设施位置，以解决智能设施位置问题。具体而言，将在包括各种图网络和平面在内的设施定位场景中探索几种基本极小和极小优化模型的容错广义版本、色广义版本和邻近连通广义版本，以及其他变体。将开发更有效的或已知的算法来解决这些具有确定和不确定数据输入的优化模型。本研究将通过开发有效的算法方法来解决这些不确定数据的基本优化问题，并提高对不确定数据计算的理解，从而促进理论计算机科学算法领域的知识和理解。该奖项反映了美国国家科学基金会的法定使命，并通过使用基金会的知识价值和更广泛的影响审查标准进行评估，被认为值得支持。

Facility locations are fundamental problems in the real world that are concerned with determining the best locations of facilities to "serve" demands under some optimization criteria. In this age of big data, the significance of uncertainty within the gathered demand data becomes more evident due to factors such as data acquisition device error, measurement inaccuracies, sampling fault, data integration error, etc. This is especially true due to the wide deployment of sensor monitoring infrastructures and increasing prevalence of technologies. This project aims to study a set of facility location optimization problems in face of uncertain demand data, and the goal is to explore new ideas and techniques to develop efficient algorithms to solve these optimization problems on uncertain data. The research will incorporate a variety of methodologies from diverse areas such as discrete math, graph theory, combinatorial optimization, probability theory, operations research, computational geometry, data structures, etc. This project will engage undergraduate and masters students in the development and implementation of algorithms to increase the throughput of them who pursue careers in theoretical computer science research, including continuing on to Ph.D. programs. The research results produced from this project will be integrated into several courses on data structures and algorithms, which will benefit both undergraduate and graduate students with diverse backgrounds. In this project, three topics will be investigated: The first topic is faulty-tolerant facility locations to provide a safeguard against failures of facilities; the second topic is chromatic facility locations to situate multiple types of facilities; the third topic is proximity connected facility locations to address intelligent facility location problems. Specifically, the faulty-tolerant generalized versions, the chromatic generalized versions, and the proximity connected generalized versions of several fundamental minimax and minisum optimization models, as well as other variations will be explored in facility location scenarios including various graph networks and the plane. More efficient or first-known algorithms will be developed to solve these optimization models with certain and uncertain data inputs. This research will advance knowledge and understanding within the field of Algorithms in theoretical computer science by developing efficient algorithmic approaches for solving these fundamental optimization problems on uncertain data and improving the understanding of the computation on uncertain data.This award reflects NSF's statutory mission and has been deemed worthy of support through evaluation using the Foundation's intellectual merit and broader impacts review criteria.