๐”– Bobbio Scriptorium
โœฆ   LIBER   โœฆ

A Randomized Approximation Scheme for Metric MAX-CUT

โœ Scribed by W. Fernandez de la Vega; Claire Kenyon

Publisher
Elsevier Science
Year
2001
Tongue
English
Weight
113 KB
Volume
63
Category
Article
ISSN
0022-0000

No coin nor oath required. For personal study only.

โœฆ Synopsis

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.

๐Ÿ“œ SIMILAR VOLUMES

MAX-CUT has a randomized approximation s
MAX-CUT has a randomized approximation scheme in dense graphs
โœ W. Fernandez de la Vega ๐Ÿ“‚ Article ๐Ÿ“… 1996 ๐Ÿ› John Wiley and Sons ๐ŸŒ English โš– 508 KB

A cut in a graph G = (V(G), E(G)) is the boundary 6(S) of some subset S V(G) and the maximum cut problem for G is to find the maximum number of edges in a cut. Let MC(G) denote this maximum. For any given 0 < a < 1, E > 0, and 17, we give a randomized algorithm which runs in a polynomial time and wh

A 78-approximation algorithm for metric
A 78-approximation algorithm for metric Max TSP
โœ Refael Hassin; Shlomi Rubinstein ๐Ÿ“‚ Article ๐Ÿ“… 2002 ๐Ÿ› Elsevier Science ๐ŸŒ English โš– 66 KB

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.

Combinatorial Properties and the Complex
Combinatorial Properties and the Complexity of a Max-cut Approximation
โœ Charles Delorme; Svatopluk Poljak ๐Ÿ“‚ Article ๐Ÿ“… 1993 ๐Ÿ› Elsevier Science ๐ŸŒ English โš– 667 KB

We study various properties of an eigenvalue upper bound on the max-cut problem. We show that the bound behaves in a manner similar to the max-cut for the operations of switching, vertex splitting, contraction and decomposition. It can also be adjusted for branch and bound techniques. We introduce a

A discrete filled function algorithm for
A discrete filled function algorithm for approximate global solutions of max-cut problems
โœ Ai-Fan Ling; Cheng-Xian Xu; Feng-Min Xu ๐Ÿ“‚ Article ๐Ÿ“… 2008 ๐Ÿ› Elsevier Science ๐ŸŒ English โš– 245 KB

A discrete filled function algorithm is proposed for approximate global solutions of max-cut problems. A new discrete filled function is defined for max-cut problems and the properties of the filled function are studied. Unlike general filled function methods, using the characteristic of max-cut pro