arXiv Open Access 2010

Approximability of the Multiple Stack TSP

Sophie Toulouse

Lihat Sumber

Abstrak

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 Max2STSP, Max2STSP12 and Min2STSP12.

Topik & Kata Kunci

cs.CC cs.RO

Penulis (1)

Sophie Toulouse

Format Sitasi

APA MLA BibTeX

Toulouse, S. (2010). Approximability of the Multiple Stack TSP. https://arxiv.org/abs/1009.5030

Akses Cepat

Lihat di Sumber

Informasi Jurnal

Tahun Terbit: 2010
Bahasa: en
Sumber Database: arXiv
Akses: Open Access ✓