ECCC - TR00-043

ECCC

Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login

Register

Classic Style

REPORTS > DETAIL:

Paper:

TR00-043 | 21st June 2000 00:00

A Note on Approximating MAX-BISECTION on Regular Graphs

Contact

Add Comment

TR00-043 Authors: Uriel Feige, Marek Karpinski, Michael Langberg
Publication: 23rd June 2000 16:03
Downloads: 3695

Keywords:

Approximation Algorithms, Approximation Ratios, derandomization, MAX-BISECTION, Max-Cut, NP-hardness, random graphs, Regular Graphs, Semidefinite programming

Abstract:

We design a $0.795$ approximation algorithm for the Max-Bisection problem
restricted to regular graphs. In the case of three regular graphs our
results imply an approximation ratio of $0.834$.

ISSN 1433-8092 | Imprint