All work
SSRN preprint
01.5Case Plates
Road Restoration
Reopening the fewest roads after a disaster.
- Year
- May 2025
- Role
- Corresponding author
- Stack
- Python and QGIS
- < 2
- approximation ratio on all 30 random graphs
- 12
- Istanbul benchmark instances, all within the bound
- 3.10
- worst Greedy ratio, against KMB’s guaranteed 2
Decisions
- 01A crew’s real costBlocked roads cost first, open roads second, as they do for a restoration crew.
- 02The bound holdsVerified the 2-approximation still holds under the modified cost.
- 03Quality over speedKMB takes 8 to 12 seconds where Greedy takes under one, for a guaranteed bound.
Technical notes
- Context
- Post-disaster road access gates relief, evacuation and repair. The task is selecting the minimum set of blocked roads to reopen so critical sites reconnect: an NP-hard Steiner tree problem.
- Role
- Corresponding author, with Gerlie Campion, Kathleen Grace Gultiano and Junar Landicho, Department of Computer Science, USTP-CDO.
- Timeline
- 3–4 months.
- Approach
- KMB modified to minimise a lexicographic cost: blocked road first, unblocked road second, matching the real cost to a restoration crew. The core work was verifying that the 2-approximation bound holds under this modification.
- Outcome
- The bound holds. Across 30 random graphs every ratio stayed under 2 and most were exactly 1 (optimal), with a standard deviation near 0.03. All twelve Istanbul benchmark instances from Akbari et al. and both Cagayan de Oro networks stayed within the bound.
- Performance
- KMB runs 8–12 seconds per Istanbul instance against under one second for Greedy, in exchange for a guaranteed bound. Greedy reached ratios of 3.10 and 2.76, and Thresholding runtime ranged from 1.34 to 30.41 seconds. KMB fits restoration planning, where solution quality outweighs latency.
Full stack
- Python
- QGIS
- Graph algorithms
- Steiner trees
