Introduction
Expanding healthcare access in developing nations like Ethiopia requires navigating complex trade-offs between maximizing population coverage and ensuring regional equity. This paper introduces the Health Access Resource Planner (HARP), a decision-support tool designed to assist the Ethiopian Ministry of Health in the strategic placement of health facilities. By framing facility placement as a novel optimization problem, the authors provide a principled framework to manage limited annual budgets and strict fairness requirements.
Problem Formulation: Budget Uncertainty and Equity
Ethiopia aims to achieve Universal Health Coverage by upgrading thousands of basic health posts to "comprehensive" status. However, planners face two primary challenges:
- Online Budgeting: Funding arrives in annual, uncertain increments, complicating long-term infrastructure planning.
- Proportional Distribution: To maintain social equity, upgrades must be distributed fairly across diverse districts (proportionality), rather than solely clustering in high-density urban centers.
The authors formalize this as Maximizing a non-decreasing submodular function under Online Partition and Global Proportional constraints (MOPGP).
Methodology
The HARP framework utilizes submodular optimization to model the "diminishing returns" of healthcare coverage—where adding a facility near an existing one provides less marginal benefit than placing it in an unserved region.
The core algorithmic contributions include:
- Learning-Augmented Single-Step Planning: This algorithm integrates "advice" (e.g., human expert recommendations) with a greedy refinement process. It ensures the final selection is at least as effective as the advice while maintaining provable performance guarantees.
- Multistep Planning under Uncertainty: This approach manages multi-year horizons by enforcing "type feasibility." It ensures that every annual allocation moves toward long-term proportionality targets, providing robustness against future budget fluctuations.
Data and Evaluation
The tool was evaluated using high-resolution spatial datasets, including WorldPop for 1km-grid population forecasts (2026–2030) and the Global Friction Surface to estimate walking travel times based on terrain. Evaluation focused on four Ethiopian regions: Afar, Benishangul Gumuz, Somali, and Sidama.
Key Insights
- The Low Price of Fairness: Enforcing proportionality (ensuring each district receives its fair share) results in minimal loss of overall population coverage. Efficiency remains high even with strict equity constraints.
- Human-AI Collaboration: The learning-augmented approach treats human expertise as a valuable input to be refined rather than replaced. This synergy leads to outcomes superior to those achieved by either experts or algorithms in isolation.
- Robustness through Type Feasibility: By maintaining proportional balance at every step, the system remains resilient to sudden budget cuts or changes in funding availability.
Results
In retrospective analyses across 25 districts, the learning-augmented selection consistently outperformed both original expert-curated plans and standard greedy baselines.
Empirical tests confirmed that the MultistepPlanning algorithm achieves a $1/2$-approximation ratio relative to the offline optimum, even under significant budget uncertainty.
Limitations and Future Directions
While HARP provides a robust framework, it currently assumes facilities remain fully operational indefinitely, without accounting for staffing or supply chain issues. Future work could incorporate facility capacity constraints and more direct health outcome metrics. Additionally, extending the provable performance guarantees of the learning-augmented algorithm to the full multi-year horizon remains an open theoretical challenge.
Summary updated