An explicit lower bound for TSP with distances one and two
type: Item
instance of: scholarly article
title: An explicit lower bound for TSP with distances one and two
zbMATH Open document ID: 1045.68066
author: Lars Engebretsen
published in: Algorithmica
publication date: 2003-08-19T00:00:00Z
Mathematics Subject Classification ID: 68Q25
Mathematics Subject Classification ID: 68Q17
Mathematics Subject Classification ID: 90C35
zbMATH DE Number: 1967762
zbMATH Keywords: traveling salesman problem
zbMATH Keywords: approximability
zbMATH Keywords: gadget reductions
zbMATH Keywords: lower bounds
MaRDI profile type: Publication
full work available at URL: s00453-002-1001-6
OpenAlex ID: W2914372558
DOI: 10.1007/S00453-002-1001-6
Recommended article: Improved Approximation Lower Bounds for TSP with Distances One and Two
Recommended article: Fundamentals of Computation Theory
Recommended article: Improved Lower Bounds for the Universal and a priori TSP
Recommended article: TSP with bounded metrics
Recommended article: Lower Bounds for Insertion Methods for TSP
Recommended article: A Lower Bound for Adjacencies on the Traveling Salesman Polytope
Recommended article: New Approximation Algorithms for (1,2)-TSP
Recommended article: Q4501548
Recommended article: A (slightly) improved approximation algorithm for metric TSP
Recommended article: A lower bound for the shortest path problem
description: scientific article; zbMATH DE number 1967762