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

Improved Approximation Algorithms for Bipartite Correlation Clustering

โœ Scribed by Ailon, Nir; Avigdor-Elgrabli, Noa; Liberty, Edo; van Zuylen, Anke

Book ID
118158322
Publisher
Society for Industrial and Applied Mathematics
Year
2012
Tongue
English
Weight
242 KB
Volume
41
Category
Article
ISSN
0097-5397

No coin nor oath required. For personal study only.

๐Ÿ“œ SIMILAR VOLUMES

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