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.