A constant-ratio approximation algorithm for a class of hub-and-spoke network design problems and metric labeling problems: star metric case

Yuko Kuroki, Tomomi Matsui

Transportation networks frequently employ hub-and-spoke network architectures to route flows between many origin and destination pairs. Hub facilities work as switching points for…