FIXED RATIO POLYNOMIAL TIME APPROXIMATION ALGORITHM FOR THE PRIZE-COLLECTING ASYMMETRIC TRAVELING SALESMAN PROBLEM (Q6081704): Difference between revisions

Revision as of 01:58, 3 August 2024

scientific article; zbMATH DE number 7746234

Language	Label	Description	Also known as
English	FIXED RATIO POLYNOMIAL TIME APPROXIMATION ALGORITHM FOR THE PRIZE-COLLECTING ASYMMETRIC TRAVELING SALESMAN PROBLEM	scientific article; zbMATH DE number 7746234

Statements

instance of

scholarly article

0 references

title

FIXED RATIO POLYNOMIAL TIME APPROXIMATION ALGORITHM FOR THE PRIZE-COLLECTING ASYMMETRIC TRAVELING SALESMAN PROBLEM (English)

0 references

0 references

0 references

0 references

Ural Mathematical Journal

0 references

publication date

5 October 2023

0 references

full work available at URL

http://mathnet.ru/eng/umj194

0 references

zbMATH Keywords

prize-collecting traveling salesman problem

0 references

triangle inequality

0 references

approximation algorithm

0 references

fixed approximation ratio

0 references

MaRDI profile type

MaRDI publication profile

0 references

cites work

Improved Approximation Algorithms for Prize-Collecting Steiner Tree and TSP

0 references

The prize collecting traveling salesman problem

0 references

The Traveling Salesman Problem: Low-Dimensionality Implies a Polynomial Time Approximation Scheme

0 references

Q5365098

0 references

A branch-and-cut algorithm for the undirected prize collecting traveling salesman problem

0 references

A note on the prize collecting traveling salesman problem

0 references

Q5009572

0 references

Reducing Curse of Dimensionality

0 references

Optimization for drone and drone-truck combined operations: a review of the state of the art and future directions

0 references

A Branch-and-Cut and MIP-based heuristics for the Prize-Collecting Travelling Salesman Problem

0 references

On Prize‐collecting Tours and the Asymmetric Travelling Salesman Problem

0 references

Q4205235

0 references

A General Approximation Technique for Constrained Forest Problems

0 references

The traveling salesman problem and its variations.

0 references

Some remarks on Arc‐connectivity, vertex splitting, and orientation in graphs and digraphs

0 references

Efficient approximation of the metric CVRP in spaces of fixed doubling dimension

0 references

Precedence constrained generalized traveling salesman problem: polyhedral study, formulations, and branch-and-cut algorithm

0 references

A unified matheuristic for solving multi-constrained traveling salesman problems with profits

0 references

On some connectivity properties of Eulerian graphs

0 references

Q2861509

0 references

The Euclidean traveling salesman problem is NP-complete

0 references

P-Complete Approximation Problems

0 references

A constant-factor approximation algorithm for the asymmetric traveling salesman problem

0 references

An improved approximation algorithm for ATSP

0 references

Identifiers

DOI

10.15826/umj.2023.1.012

0 references

Mathematics Subject Classification ID

0 references

0 references

0 references

0 references

Sitelinks

Mathematics(1 entry)

mardi Publication:6081704

@@ Property / cites work @@
+Improved Approximation Algorithms for Prize-Collecting Steiner Tree and TSP
+Normal rank
@@ Property / cites work @@
+The prize collecting traveling salesman problem
@@ Property / cites work: The prize collecting traveling salesman problem / rank @@
+Normal rank
@@ Property / cites work @@
+The Traveling Salesman Problem: Low-Dimensionality Implies a Polynomial Time Approximation Scheme
+Normal rank
@@ Property / cites work @@
+Q5365098
@@ Property / cites work: Q5365098 / rank @@
+Normal rank
@@ Property / cites work @@
+A branch-and-cut algorithm for the undirected prize collecting traveling salesman problem
+Normal rank
@@ Property / cites work @@
+A note on the prize collecting traveling salesman problem
+Normal rank
@@ Property / cites work @@
+Q5009572
@@ Property / cites work: Q5009572 / rank @@
+Normal rank
@@ Property / cites work @@
+Reducing Curse of Dimensionality
@@ Property / cites work: Reducing Curse of Dimensionality / rank @@
+Normal rank
@@ Property / cites work @@
+Optimization for drone and drone-truck combined operations: a review of the state of the art and future directions
+Normal rank
@@ Property / cites work @@
+A Branch-and-Cut and MIP-based heuristics for the Prize-Collecting Travelling Salesman Problem
+Normal rank
@@ Property / cites work @@
+On Prize‐collecting Tours and the Asymmetric Travelling Salesman Problem
+Normal rank
@@ Property / cites work @@
+Q4205235
@@ Property / cites work: Q4205235 / rank @@
+Normal rank
@@ Property / cites work @@
+A General Approximation Technique for Constrained Forest Problems
+Normal rank
@@ Property / cites work @@
+The traveling salesman problem and its variations.
+Normal rank
@@ Property / cites work @@
+Some remarks on Arc‐connectivity, vertex splitting, and orientation in graphs and digraphs
+Normal rank
@@ Property / cites work @@
+Efficient approximation of the metric CVRP in spaces of fixed doubling dimension
+Normal rank
@@ Property / cites work @@
+Precedence constrained generalized traveling salesman problem: polyhedral study, formulations, and branch-and-cut algorithm
+Normal rank
@@ Property / cites work @@
+A unified matheuristic for solving multi-constrained traveling salesman problems with profits
+Normal rank
@@ Property / cites work @@
+On some connectivity properties of Eulerian graphs
+Normal rank
@@ Property / cites work @@
+Q2861509
@@ Property / cites work: Q2861509 / rank @@
+Normal rank
@@ Property / cites work @@
+The Euclidean traveling salesman problem is NP-complete
+Normal rank
@@ Property / cites work @@
+P-Complete Approximation Problems
@@ Property / cites work: P-Complete Approximation Problems / rank @@
+Normal rank
@@ Property / cites work @@
+A constant-factor approximation algorithm for the asymmetric traveling salesman problem
+Normal rank
@@ Property / cites work @@
+An improved approximation algorithm for ATSP
@@ Property / cites work: An improved approximation algorithm for ATSP / rank @@
+Normal rank