Approximating the asymmetric profitable tour
type: Item
instance of: scholarly article
title: Approximating the asymmetric profitable tour
zbMATH Open document ID: 1269.90094
DOI: 10.1504/IJMOR.2012.046689
author: Viet Hung Nguyen
author: Thi Thu Thuy Nguyen
published in: International Journal of Mathematics in Operational Research
publication date: 2012-11-16T00:00:00Z
review text: Summary: We study the version of the asymmetric prize collecting travelling salesman problem, where the objective is to find a directed tour that visits a subset of vertices such that the length of the tour plus the sum of penalties associated with vertices not in the tour is as small as possible. In [\textit{M. Dell'Amico} et al., Int. Trans. Oper. Res. 2, No. 3, 297--308 (1995; Zbl 0860.90121)], the authors defined it as the profitable tour problem (PTP). We present an \((1 + \lceil \log(n)\rceil )\)-approximation algorithm for the asymmetric PTP, where \(n\) denotes the number of vertices. The algorithm is based on a heuristic for the asymmetric travelling salesman problem by \textit{A. M. Frieze} et al. [Networks 12, 23--39 (1982; Zbl 0478.90070)], as well as a method to round fractional solutions of a linear programming relaxation to integers (feasible solution for the original problem), represents a directed version of the algorithm for the symmetric PTP by \textit{D. Bienstock} et al. [Math. Program. 59, No. 3 (A), 413--420 (1993; Zbl 0793.90089)].
Mathematics Subject Classification ID: 90C27
Mathematics Subject Classification ID: 90C59
zbMATH DE Number: 6108305
zbMATH Keywords: asymmetric profitable tour
zbMATH Keywords: asymmetric prize collecting travelling salesman
zbMATH Keywords: Held-Karp relaxation
zbMATH Keywords: discrete optimisation
zbMATH Keywords: operations research
MaRDI profile type: MaRDI publication profile
full work available at URL: ijmor.2012.046689
OpenAlex ID: W1999401924
description: scientific article; zbMATH DE number 6108305