Approximability of the multiple stack TSP
S Toulouse - Electronic Notes in Discrete Mathematics, 2010 - Elsevier
STSP seeks a pair of pickup and delivery tours in two distinct networks, where the two tours
are related by LIFO contraints. We address here the problem approximability. We notably
establish that asymmetric MaxSTSP and MinSTSP12 are APX, and propose a heuristic that
yields to a 1/2, 3/4 and 3/2 standard approximation for respectively MaxSTSP, MaxSTSP12
and MinSTSP12.
are related by LIFO contraints. We address here the problem approximability. We notably
establish that asymmetric MaxSTSP and MinSTSP12 are APX, and propose a heuristic that
yields to a 1/2, 3/4 and 3/2 standard approximation for respectively MaxSTSP, MaxSTSP12
and MinSTSP12.