Algorithms for Spatial Variations of Classic Optimization Problems with Healthcare ApplicationsWorrell, Clarence (2023) Algorithms for Spatial Variations of Classic Optimization Problems with Healthcare Applications. Doctoral Dissertation, University of Pittsburgh. (Unpublished)
AbstractOperating healthcare systems efficiently is critical for maximizing healthcare delivery to patients. Due to the inherent spatial structure in many healthcare systems, however, this requires solving challenging spatial optimization problems. In this work, we design solution algorithms that are implementation-friendly, scalable, and have theoretical performance guarantees for spatial variations of three classic optimization problems that arise in this context: machine assignment, facility location, and graph partitioning. In Chapter 2, we consider minimizing makespan across parallel machines that are located in different areas, a problem motivated by multi-hospital systems that share laboratory workload using courier services. This system introduces opportunity to reduce makespan by assigning jobs to lesser-loaded, but spatially distant, machines at the expense of transportation time penalties. We develop an implementation-friendly list-scheduling algorithm and show that it is a 2-approximation algorithm when the machines are identical. Computational experiments show that the algorithm often performs much better than its worst-case guarantee, even when the machines are not identical. In Chapter 3, we consider a variation of the k-center facility location problem in which facility agents can meet clients at intermediate locations (i.e., "meet-in-the-middle”) to deliver goods. This problem arises when designing vaccination campaigns for geographically dispersed populations with limited transportation resources. We show that the meet-in-the middle k-center problem reduces to the standard k-center problem under a certain notion of "distance.” We develop an approximation algorithm and a mixed integer linear program (MILP) that both leverage this reduction. Computational experiments show that we can solve the MILP 90% faster than a MILP formulation that does not leverage the reduction. In Chapter 4, we consider the problem of recovering the ground-truth communities of a vertex-attributed graph that are locally distinguishable in the sense that they exhibit stronger community structure in more local parts of the graph. The partitioning problem arises when labeling training data that contain responses generated from different latent sources, a major barrier to using machine learning in healthcare. We develop a community detection algorithm and establish conditions under which it almost exactly recovers ground-truth communities. Computational experiments demonstrate the advantages of our method over a benchmark spectral method. Share
Details
MetricsMonthly Views for the past 3 yearsPlum AnalyticsActions (login required)
|
![[feed]](/images/feed-icon-32x32.png){kind=icon}