Computational Complexity and Approximation Theory for Healthcare Facility Redesign Problems in Resource-Constrained Economies

Healthcare facility network redesign in resource-constrained economies such as Nigeria involves combinatorial optimization problems of significant computational complexity, requiring simultaneous decisions on facility openings, closures, capacity expansions, and patient referral pattern modifications across multi-tier networks under budget constraints and equity requirements. This dissertation advances the computational complexity and approximation theory of healthcare facility redesign problems, motivated by the unique characteristics of sub-Saharan African healthcare systems. Original complexity-theoretic results are established for several variants of the healthcare facility redesign problem, including proofs of NP-hardness for previously unresolved problem classes combining capacity expansion and equity constraints. Approximation algorithm design exploiting the problem's geometric and submodular structure yields original constant-factor approximation guarantees for key problem variants, representing theoretical advances beyond existing approximation results in the facility location literature. An original branch-and-price algorithm incorporating specialized pricing subproblem solutions and cutting plane strategies is developed for exact solution of moderately-sized instances. The theoretical results are instantiated through application to healthcare system redesign in Katsina, Zamfara, and Kebbi States, using population, disease burden, and infrastructure data. Three strategic redesign scenarios corresponding to different budget envelopes generate actionable investment recommendations for the Northwest zonal health planning body. The dissertation makes original contributions to combinatorial optimization theory, approximation algorithms, and the operations research of healthcare systems in low-income contexts, advancing both theoretical knowledge and practical decision support. Keywords: computational complexity, approximation algorithms, healthcare redesign, facility location, resource-constrained