Improved Approximation Algorithms for (1,2)-TSP and Max-TSP Using Path Covers in the Semi-Streaming Model
Fuente:
arXiv
Guardado en:
| Autores principales: | , , |
|---|---|
| Formato: | Preprint |
| Publicado: |
2025
|
| Materias: | |
| Acceso en línea: | |
| Etiquetas: |
Agregar Etiqueta
Sin Etiquetas, Sea el primero en etiquetar este registro!
|
| _version_ | 1866909469436280832 |
|---|---|
| author | Alipour, Sharareh Farokhnejad, Ermiya Mömke, Tobias |
| author_facet | Alipour, Sharareh Farokhnejad, Ermiya Mömke, Tobias |
| contents | We investigate semi-streaming algorithms for the Traveling Salesman Problem (TSP). Specifically, we focus on a variant known as the $(1,2)$-TSP, where the distances between any two vertices are either one or two. Our primary emphasis is on the closely related Maximum Path Cover Problem, which aims to find a collection of vertex-disjoint paths that cover the maximum number of edges in a graph. We propose an algorithm that, for any $ε> 0$, achieves a $(\frac{2}{3}-ε)$-approximation of the maximum path cover size for an $n$-vertex graph, using $\text{poly}(\frac{1}ε)$ passes. This result improves upon the previous $\frac{1}{2}$-approximation by Behnezhad et al. [ICALP 2024] in the semi-streaming model. Building on this result, we design a semi-streaming algorithm that constructs a tour for an instance of $(1,2)$-TSP with an approximation factor of $(\frac{4}{3} + ε)$, improving upon the previous $\frac{3}{2}$-approximation actor algorithm by Behnezhad et al. [ICALP 2024] (Although it is not explicitly stated in the paper that their algorithm works in the semi-streaming model, it is easy to verify). Furthermore, we extend our approach to develop an approximation algorithm for the Maximum TSP (Max-TSP), where the goal is to find a Hamiltonian cycle with the maximum possible weight in a given weighted graph $G$. Our algorithm provides a $(\frac{7}{12} - ε)$-approximation for Max-TSP in $\text{poly}(\frac{1}ε)$ passes, improving on the previously known $(\frac{1}{2}-ε)$-approximation obtained via maximum weight matching in the semi-streaming model. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2501_04813 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | Improved Approximation Algorithms for (1,2)-TSP and Max-TSP Using Path Covers in the Semi-Streaming Model Alipour, Sharareh Farokhnejad, Ermiya Mömke, Tobias Data Structures and Algorithms We investigate semi-streaming algorithms for the Traveling Salesman Problem (TSP). Specifically, we focus on a variant known as the $(1,2)$-TSP, where the distances between any two vertices are either one or two. Our primary emphasis is on the closely related Maximum Path Cover Problem, which aims to find a collection of vertex-disjoint paths that cover the maximum number of edges in a graph. We propose an algorithm that, for any $ε> 0$, achieves a $(\frac{2}{3}-ε)$-approximation of the maximum path cover size for an $n$-vertex graph, using $\text{poly}(\frac{1}ε)$ passes. This result improves upon the previous $\frac{1}{2}$-approximation by Behnezhad et al. [ICALP 2024] in the semi-streaming model. Building on this result, we design a semi-streaming algorithm that constructs a tour for an instance of $(1,2)$-TSP with an approximation factor of $(\frac{4}{3} + ε)$, improving upon the previous $\frac{3}{2}$-approximation actor algorithm by Behnezhad et al. [ICALP 2024] (Although it is not explicitly stated in the paper that their algorithm works in the semi-streaming model, it is easy to verify). Furthermore, we extend our approach to develop an approximation algorithm for the Maximum TSP (Max-TSP), where the goal is to find a Hamiltonian cycle with the maximum possible weight in a given weighted graph $G$. Our algorithm provides a $(\frac{7}{12} - ε)$-approximation for Max-TSP in $\text{poly}(\frac{1}ε)$ passes, improving on the previously known $(\frac{1}{2}-ε)$-approximation obtained via maximum weight matching in the semi-streaming model. |
| title | Improved Approximation Algorithms for (1,2)-TSP and Max-TSP Using Path Covers in the Semi-Streaming Model |
| topic | Data Structures and Algorithms |
| url | https://arxiv.org/abs/2501.04813 |