Approximation algorithms for multi-criteria traveling salesman problems
From MaRDI portal
Publication:1017906
DOI10.1007/11970125_24zbMATH Open1161.90019arXivcs/0606040OpenAlexW1902458947MaRDI QIDQ1017906FDOQ1017906
Publication date: 13 May 2009
Published in: Algorithmica, Approximation and Online Algorithms (Search for Journal in Brave)
Abstract: In multi-criteria optimization problems, several objective functions have to be optimized. Since the different objective functions are usually in conflict with each other, one cannot consider only one particular solution as the optimal solution. Instead, the aim is to compute a so-called Pareto curve of solutions. Since Pareto curves cannot be computed efficiently in general, we have to be content with approximations to them. We design a deterministic polynomial-time algorithm for multi-criteria g-metric STSP that computes (min{1 +g, 2g^2/(2g^2 -2g +1)} + eps)-approximate Pareto curves for all 1/2<=g<=1. In particular, we obtain a (2+eps)-approximation for multi-criteria metric STSP. We also present two randomized approximation algorithms for multi-criteria g-metric STSP that achieve approximation ratios of (2g^3 +2g^2)/(3g^2 -2g +1) + eps and (1 +g)/(1 +3g -4g^2) + eps, respectively. Moreover, we present randomized approximation algorithms for multi-criteria g-metric ATSP (ratio 1/2 + g^3/(1 -3g^2) + eps) for g < 1/sqrt(3)), STSP with weights 1 and 2 (ratio 4/3) and ATSP with weights 1 and 2 (ratio 3/2). To do this, we design randomized approximation schemes for multi-criteria cycle cover and graph factor problems.
Full work available at URL: https://arxiv.org/abs/cs/0606040
Recommendations
- Approximation algorithms for multi-criteria traveling salesman problems
- Approximation algorithms for the traveling salesman problem
- On approximating multi-criteria TSP
- scientific article
- On approximating multicriteria \textsc{TSP}
- Approximation schemes for the generalized traveling salesman problem
- An approximation algorithm for the maximum traveling salesman problem
- An approximation algorithm for the maximum traveling salesman problem
- Approximating Multi-criteria Max-TSP
- The traveling salesman problem. Approximate algorithms
Multi-objective and goal programming (90C29) Programming involving graphs or networks (90C35) Approximation methods and heuristics in mathematical programming (90C59) Randomized algorithms (68W20) Approximation algorithms (68W25)
Cites Work
- Title not available (Why is that?)
- Matching theory
- Multicriteria Optimization
- The traveling salesman problem and its variations
- An Analysis of Several Heuristics for the Traveling Salesman Problem
- Title not available (Why is that?)
- Title not available (Why is that?)
- A survey and annotated bibliography of multiobjective combinatorial optimization
- Title not available (Why is that?)
- 8/7-approximation algorithm for (1,2)-TSP
- Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques
- Matching is as easy as matrix inversion
- Title not available (Why is that?)
- A Short Proof of the Factor Theorem for Finite Graphs
- The complexity of restricted spanning tree problems
- Approximating the Pareto curve with local search for the bicriteria TSP(1,2) problem
- Approximation algorithms for asymmetric TSP by decomposing directed regular multigraphs
- An improved approximation algorithm for the asymmetric TSP with strengthened triangle inequality
- On the relationship between ATSP and the cycle cover problem
- Exact arborescences, matchings and cycles
- Fundamentals of Computation Theory
Cited In (12)
- Generation of the exact Pareto set in multi-objective traveling salesman and set covering problems
- Approximation algorithms for multi-criteria traveling salesman problems
- Multi-criteria TSP: Min and Max combined
- Approximation Methods for Multiobjective Optimization Problems: A Survey
- Novel concave hull-based heuristic algorithm for TSP
- Fundamentals of Computation Theory
- Advancing local search approximations for multiobjective combinatorial optimization problems
- Deterministic Algorithms for Multi-criteria TSP
- Approximating the Pareto curve with local search for the bicriteria TSP(1,2) problem
- A unified matheuristic for solving multi-constrained traveling salesman problems with profits
- Approximating Multi-criteria Max-TSP
- Deterministic algorithms for multi-criteria max-TSP
This page was built for publication: Approximation algorithms for multi-criteria traveling salesman problems
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1017906)
