𝔖 Bobbio Scriptorium
✦   LIBER   ✦

A 78-approximation algorithm for metric Max TSP

✍ Scribed by Refael Hassin; Shlomi Rubinstein

Publisher
Elsevier Science
Year
2002
Tongue
English
Weight
66 KB
Volume
81
Category
Article
ISSN
0020-0190

No coin nor oath required. For personal study only.

✦ Synopsis

We present a randomized approximation algorithm for the metric version of undirected Max TSP. Its expected performance guarantee approaches 7 8 as n β†’ ∞, where n is the number of vertices in the graph.

πŸ“œ SIMILAR VOLUMES

A Randomized Approximation Scheme for Me
A Randomized Approximation Scheme for Metric MAX-CUT
✍ W. Fernandez de la Vega; Claire Kenyon πŸ“‚ Article πŸ“… 2001 πŸ› Elsevier Science 🌐 English βš– 113 KB

Metric MAX-CUT is the problem of dividing a set of points in metric space into two parts so as to maximize the sum of the distances between points belonging to distinct parts. We show that metric MAX-CUT is NP-complete but has a polynomial time randomized approximation scheme.

Approximation algorithms for the Euclide
Approximation algorithms for the Euclidean bipartite TSP
✍ Andreas Baltz; Anand Srivastav πŸ“‚ Article πŸ“… 2005 πŸ› Elsevier Science 🌐 English βš– 214 KB

We study approximation results for the Euclidean bipartite traveling salesman problem (TSP). We present the first worstcase examples, proving that the approximation guarantees of two known polynomial-time algorithms are tight. Moreover, we propose a new algorithm which displays a superior average ca

Improved Approximation Algorithms for MA
Improved Approximation Algorithms for MAX SAT
✍ Takao Asano; David P. Williamson πŸ“‚ Article πŸ“… 2002 πŸ› Elsevier Science 🌐 English βš– 215 KB

MAX SAT (the maximum s~tisfiability problem) is stated as follows: given a set of clauses with weights, find a truth assignment that maximizes the sum of the weights of the satisfied clauses. In this paper, we consider approxima~ tion algorithms for MAX SAT proposed by Goemans and Williamson and pze

Approximation Algorithms for Min–Max Tre
Approximation Algorithms for Min–Max Tree Partition
✍ Nili Guttmann-Beck; Refael Hassin πŸ“‚ Article πŸ“… 1997 πŸ› Elsevier Science 🌐 English βš– 298 KB

We consider the problem of partitioning the node set of a graph into p equal sized subsets. The objective is to minimize the maximum length, over these subsets, of a minimum spanning tree. We show that no polynomial algorithm with bounded Ε½ 2 . error ratio can be given for the problem unless P s NP.

On Approximation Algorithms for Hierarch
On Approximation Algorithms for Hierarchical MAX-SAT
✍ Sameet Agarwal; Anne Condon πŸ“‚ Article πŸ“… 1998 πŸ› Elsevier Science 🌐 English βš– 232 KB

We prove upper and lower bounds on performance guarantees of approximation Ε½ . algorithms for the hierarchical MAX-SAT H-MAX-SAT problem. This problem is representative of a broad class of PSPACE-hard problems involving graphs, Boolean formulas, and other structures that are defined succinctly. Our