A unified framework for obtaining improved approximation algorithms for maximum graph bisection problems.

*(English)*Zbl 1017.68089Summary: We obtain improved semidefinite programming based approximation algorithms for all the natural maximum bisection problems of graphs. Among the problems considered are: MAX \({n\over 2}\)-BISECTION – partition the vertices of the graph into two sets of equal size such that the total weight of edges connecting vertices from different sides is maximized; MAX \({n\over 2}\)-VERTEX-COVER – find a set containing half of the vertices such that the total weight of edges touching this set is maximized; MAX \({n\over 2}\)-DENSE-SUBGRAPH – find a set containing half of the vertices such that the total weight of edges connecting two vertices from this set is maximized; and MAX \({n\over 2}\)-UNCUT – partition the vertices into two sets of equal size such that the total weight of edges that do not cross the cut is maximized. We also consider the directed versions of these problems, such as MAX \({n\over 2}\)-DIRECTED-BISECTION and MAX \({n\over 2}\)-DIRECTED-UNCUT. These results can be used to obtain improved approximation algorithms for the unbalanced versions of the partition problems mentioned above, where we want to partition the graph into two sets of size \(k\) and \(n- k\), where \(k\) is not necessarily \({n\over 2}\). Our results improve, extend and unify results of Frieze and Jerrum, Feige and Langberg, Ye, and others. All these results may be viewed as extensions of the MAX CUT algorithm of Goemans and Williamson, and the MAX 2-SAT and MAX DI-CUT algorithms of Feige and Geomans.

##### Software:

Outward rotations
PDF
BibTeX
XML
Cite

\textit{E. Halperin} and \textit{U. Zwick}, Random Struct. Algorithms 20, No. 3, 382--402 (2002; Zbl 1017.68089)

Full Text:
DOI

##### References:

[1] | and An 0.5-approximation algorithm for MAX DICUT with given sizes of parts, manuscript, 2000. |

[2] | Barahona, Math Program 36 pp 157– (1986) · Zbl 0616.90058 |

[3] | and Approximating the value of two prover proof systems, with applications to MAX-2SAT and MAX-DICUT, Proc 3rd Israel Symp Theory and Computing Systems, Tel Aviv, Israel, 1995, pp. 182-189. |

[4] | and Approximation algorithms for maximization problems arising in graph partitioning, manuscript, 1999. |

[5] | and The RPR2 rounding technique for semidefinite programs, Proc 28th Int Colloq Automata, Languages and Programming, Crete, Greece, 2001, pp. 213-224. · Zbl 0986.90041 |

[6] | and On the integrality ratio of semidefinite relaxations of MAX CUT, Proc 33th Annu ACM Symp Theory of Computing, Crete, Greece, 2001, to appear. · Zbl 1323.68298 |

[7] | and Improved approximation of Max-Cut on graphs of bounded degree, Technical Report, Electronic Colloquium on Computational Complexity, (E-CCC), University of Trier, Report No. TR00-043, 2000. |

[8] | and A note on approximating MAX-BISECTION on regular graphs, Technical Report, Electronic Colloquium on Computational Complexity, (E-CCC), University of Trier, Report No. TR00-043, 2000. |

[9] | Frieze, Algorithmica 18 pp 67– (1997) · Zbl 0873.68078 |

[10] | Goemans, J Appl Comput Math 42 pp 1115– (1995) |

[11] | Gr?tschel, Combinatorica 1 pp 169– (1981) · Zbl 0492.90056 |

[12] | and An improved rounding method and semidefinite programming relaxation for graph partition, manuscript, 2000. |

[13] | and On approximation of Max-Vertex-Cover, manuscript, 2000. |

[14] | and A 7/8-approximation algorithm for MAX 3SAT? Proc 38th Annu IEEE Symp Foundations of Computer Science, Miami Beach, Florida, 1997, pp. 406-415. |

[15] | Mahajan, SIAM J Comput 28 pp 1641– (1999) · Zbl 0928.68055 |

[16] | Nesterov, Optim Methods Software 9 pp 141– (1998) · Zbl 0904.90136 |

[17] | Tur?n, Mat Fiz Lapok 48 pp 436– (1941) |

[18] | and (Eds.), Handbook of semidefinite programming, Kluwer, Boston, 2000. |

[19] | A 0.699-approximation algorithm for Max-Bisection, manuscript, 1999. |

[20] | and Approximation of dense–subgraph and the complement of min-bisection, manuscript, 1999. |

[21] | Outward rotations: A tool for rounding solutions of semidefinite programming relaxations, with applications to max cut and other problems, Proc 31th Annu ACM Symp Theory of Computing, Atlanta, Georgia, 1999, pp. 679-687. · Zbl 1345.90064 |

[22] | Analyzing the MAX 2-SAT and MAX DI-CUT approximation algorithms of Feige and Goemans, 2000, submitted for publication. |

[23] | Computer assisted proof of optimal approximability results, Proc 13th Annu ACM-SIAM Symp Discrete Algorithms, San Francisco, California, 2002, pp. 496-505. · Zbl 1093.68640 |

This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.