CAREER: AF: Algorithms for Facility Location Problems with Uncertainty

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

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.