A note on approximating max-bisection on regular graphs

Uriel Feige; Marek Karpinski; Michael Langberg

doi:10.1016/S0020-0190(00)00189-7

A note on approximating max-bisection on regular graphs

Uriel Feige
, Marek Karpinski
, Michael Langberg

Department of Electrical Engineering

Weizmann Institute of Science

Research output: Contribution to journal › Article › peer-review

22 Scopus citations

Abstract

A 0.795 approximation algorithm for the Max-Bisection problem is designed. The algorithm is restricted to regular graphs. In the case of three regular graphs, the results imply an approximation ratio of 0.834.

Original language	English
Pages (from-to)	181-188
Number of pages	8
Journal	Information Processing Letters
Volume	79
Issue number	4
DOIs	https://doi.org/10.1016/S0020-0190(00)00189-7
State	Published - Aug 15 2001

Keywords

Approximation algorithms
Max-Bisection
Max-Cut
Regular graphs
Semidefinite programming

Access to Document

10.1016/S0020-0190(00)00189-7

Cite this

@article{2a82b673be444338885827431cb6ccdf,

title = "A note on approximating max-bisection on regular graphs",

abstract = "A 0.795 approximation algorithm for the Max-Bisection problem is designed. The algorithm is restricted to regular graphs. In the case of three regular graphs, the results imply an approximation ratio of 0.834.",

keywords = "Approximation algorithms, Max-Bisection, Max-Cut, Regular graphs, Semidefinite programming",

author = "Uriel Feige and Marek Karpinski and Michael Langberg",

year = "2001",

month = aug,

day = "15",

doi = "10.1016/S0020-0190(00)00189-7",

language = "English",

volume = "79",

pages = "181--188",

journal = "Information Processing Letters",

issn = "0020-0190",

publisher = "Elsevier B.V.",

number = "4",

}

TY - JOUR

T1 - A note on approximating max-bisection on regular graphs

AU - Feige, Uriel

AU - Karpinski, Marek

AU - Langberg, Michael

PY - 2001/8/15

Y1 - 2001/8/15

N2 - A 0.795 approximation algorithm for the Max-Bisection problem is designed. The algorithm is restricted to regular graphs. In the case of three regular graphs, the results imply an approximation ratio of 0.834.

AB - A 0.795 approximation algorithm for the Max-Bisection problem is designed. The algorithm is restricted to regular graphs. In the case of three regular graphs, the results imply an approximation ratio of 0.834.

KW - Approximation algorithms

KW - Max-Bisection

KW - Max-Cut

KW - Regular graphs

KW - Semidefinite programming

UR - https://www.scopus.com/pages/publications/0035882612

U2 - 10.1016/S0020-0190(00)00189-7

DO - 10.1016/S0020-0190(00)00189-7

M3 - Article

AN - SCOPUS:0035882612

SN - 0020-0190

VL - 79

SP - 181

EP - 188

JO - Information Processing Letters

JF - Information Processing Letters

IS - 4

ER -

A note on approximating max-bisection on regular graphs

Abstract

Keywords

Access to Document

Other files and links

Fingerprint

Cite this