✦ LIBER ✦

Improved approximation algorithms for MAXk-CUT and MAX BISECTION

✍ Scribed by A. Frieze; M. Jerrum

Book ID: 110547540
Publisher: Springer
Year: 1997
Tongue: English
Weight: 685 KB
Volume: 18
Category: Article
ISSN: 0178-4617
DOI: 10.1007/bf02523688

No coin nor oath required. For personal study only.

📜 SIMILAR VOLUMES

A .699-approximation algorithm for Max-B

A .699-approximation algorithm for Max-Bisection

✍ Yinyu Ye 📂 Article 📅 2001 🏛 Springer-Verlag 🌐 English ⚖ 71 KB

Approximation algorithms for MAX RES CUT

Approximation algorithms for MAX RES CUT with

✍ Aifan Ling; Le Tang; Chengxian Xu 📂 Article 📅 2009 🏛 Springer-Verlag 🌐 English ⚖ 464 KB

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

Improved Approximation Algorithms for MA

Improved Approximation Algorithms for MAX(frac{n}{{ ext{2}}})-DIRECTED-BISECTION and MAX(frac{n}{{ ext{2}}})-DENSE-SUBGRAPH

✍ Dachuan Xu; Jiye Han; Zhenghai Huang; Liping Zhang 📂 Article 📅 2003 🏛 Springer US 🌐 English ⚖ 99 KB

An improved approximation algorithm for

An improved approximation algorithm for requirement cut

✍ Anupam Gupta; Viswanath Nagarajan; R. Ravi 📂 Article 📅 2010 🏛 Elsevier Science 🌐 English ⚖ 506 KB

An Improved Approximation Algorithm for

An Improved Approximation Algorithm for MULTIWAY CUT

✍ Gruia Călinescu; Howard Karloff; Yuval Rabani 📂 Article 📅 2000 🏛 Elsevier Science 🌐 English ⚖ 132 KB

Given an undirected graph with edge costs and a subset of k nodes called terminals, a multiway cut is a subset of edges whose removal disconnects each terminal from the rest. Multiway Cut is the problem of finding a multiway cut of minimum cost. Previously, a very simple combinatorial algorithm due