BZPEER
More

Discover

About BZPEERSearchGraph

Research tools

HomeCollectionsResearchCollaborationPublish

Network

ExpertsCommunities

Opportunities

Listings

Account

Log inCreate account
Log inCreate account

The Approximation Ratio of the Greedy Algorithm for the Metric Traveling Salesman Problem

preprint2014arXivOpen access
Judith BrecklinghausStefan Hougardy
math.COData Structures and AlgorithmsDiscrete Mathematics
Read originalOpen PDFOpen graphSave paperReviewsDiscussion

Abstract

We prove that the approximation ratio of the greedy algorithm for the metric Traveling Salesman Problem is Θ(log⁡n)Θ(\log n). Moreover, we prove that the same result also holds for graphic, Euclidean, and rectilinear instances of the Traveling Salesman Problem. Finally we show that the approximation ratio of the Clarke-Wright savings heuristic for the metric Traveling Salesman Problem is Θ(log⁡n)Θ(\log n).

Connections

Open full explorer

Explore this paper’s authors, topics and related work.

Building this map preview

BZPEER is loading the nearby papers, people, topics and institutions for this page.

Reviews 0

Write a reviewWrite
Log in to review

No reviews yet.

Discussion 0

Add a commentWrite
Log in to comment

No comments yet.