Jun WU will defend his doctoral thesis on Friday, October 17, 2025: “Design constant-ratio approximation algorithms for several variants of the multiple Hamiltonian path problem”

The Hamiltonian Path Problem (HPP), which seeks a minimum-length Hamiltonian path traversing each vertex exactly once, is an NP-hard combinatorial optimization problem fundamental to various applications, such as school bus route planning and data collection in wireless sensor networks. The Multiple Hamiltonian Path Problem (MHPP) generalizes HPP to multiple vehicles, finding k paths covering all vertices exactly once on a metric graph while minimizing the total path length. Due to its complexity, designing effective constant-ratio approximation algorithms for the MHPP and its variants remains challenging, leaving several research gaps: 1) approximation algorithms with constant ratios are underexplored; 2) the MHPP with neighborhoods and a handling time per customer under a min-max objective remains unexplored; 3) few studies investigate the MHPP with vehicle capacity and split delivery. To address these gaps, this thesis studies three categories of MHPP variants and develops new/improved constant-ratio approximation algorithms for them.

Firstly, two classical MHPP variants are investigated. The first is without prefixed start and end points for a path, referred to as MHPP-NE, while the second is the single-depot MHPP (MHPP-SD), in which all paths start at a common depot. We design the first polynomial-time 3/2-approximation algorithm for the MHPP-NE valid for any k >= 1. For the MHPP-SD, we extend the Christofides heuristic to achieve a tight approximation ratio of 2-1/(2+k) for any k >= 1.

Secondly, we study the min-max Path Cover Problem with Neighborhoods (min-max PCPN) in the plane, a variant of the MHPP that incorporates a min-max objective, handling time, and service regions (each customer can be served within a given radius around its location). The goal is to minimize the maximum cost among k paths. We explore several variants with different customer types (homogeneous vs. heterogeneous) and depot configurations (single vs. multiple). To tackle these problems, we introduce the generalized Steiner minimum tree with neighborhoods as a subproblem and develop a constant-ratio approximation algorithm with a ratio less than one-third of the best-known. It then serves for designing new/improved polynomial-time constant-ratio algorithms for min-max PCPN variants. We further extend to solve the min-max tree cover problems with neighborhoods.

Thirdly, we investigate the Split Delivery Path Routing Problem (SDPRP), generalizing the MHPP with vehicle capacity constraints and allowing split deliveries. We focus on three specific SDPRP variants: i) multiple split delivery path routing problem without depots and terminals (MSDPRP), where each of k vehicles can start from and end at any customer; ii) m-depot location and split delivery path routing problem ($m$-DL-SDPRP), where each vehicle must be assigned to one of $m$ candidate depots; iii) m-depot and m-terminal SDPRP (m-DT-SDPRP), where each vehicle starts and ends at a prefixed depot and terminal, respectively. For these, we develop new parameterized constant-ratio approximation algorithms.