Approximation Algorithms for MAX-BISECTION on Low Degree Regular Graphs

• Autorzy: Karpinski M. , Kowaluk M. , Lingas A.
• Języki publikacji: EN

Abstrakty

EN

The max-bisection problem is to find a partition of the vertices of a graph into two equal size subsets that maximizes the number of edges with endpoints in both subsets. We obtain new improved approximation ratios for the max-bisection problem on the low degree k-regular graphs for 3 ≤ k Ł≤8, by deriving some improved transformations from a maximum cut into a maximum bisection. In the case of three regular graphs we obtain an approximation ratio of 0.854, and in the case of four and five regular graphs, approximation ratios of 0.805, and 0.812, respectively.

Słowa kluczowe

EN

graph bisection; approximation algorithms; regular graphs

• Wydawca: IOS Press
• Czasopismo: Fundamenta Informaticae
• Rocznik: 2004
• Tom: Vol. 62, nr 3,4
• Strony: 369--375
• Opis fizyczny: Bibliogr. 15 poz.

Twórcy

autor

Karpinski M.

• Department of Computer Science, University of Bonn, Bonn, Germany

autor

Kowaluk M.

• Institute of Informatics, Warsaw University, Banacha 2, Warsaw, Poland

autor

Lingas A.

• Department of Computer Science, Lund University, 22100 Lund, Sweden

Bibliografia

• [1] A.A. Ageev and M.I. Sviridenko. Approximation algorithms for Maximum Coverage and Max Cut with cardinality constraints. Proceedings of IPCO99, Lecture Notes in Computer Science 1610, pp. 17-30,1999.
• [2] S. Arora, D. Karger and M. Karpinski. Polynomial Time Approximation Schemes for Dense Instances of NP-hard Problems, Proceedings 27th ACM STOC, pp. 284-293,1995.
• [3] K. Diks, H.N. Djidjev, O. Sykora and I. Vrto. Edge Separators of Planar and Outerplanar Graphs with Applications. Journal of Algorithms 14, pp. 258-279 (1993).
• [4] U. Feige, M. Karpinski and M. Langberg. Improved Approximation of Max-Cut on Graphs of Bounded Degree. ECCC (http://www.eccc.uni-trier.de/eccc/), TROO-021 (2000), also in J. of Algorithms 43(2002), pp.201-219.
• [5] U. Feige, M. Karpinski and M. Langberg. A Note on Approximating MAX-BISECTION on Regular Graphs. Information Processing Letters 79 (2001), pp. 181-188.
• [6] A. Frieze and M. Jerrum. Improved approximation algorithms for MAX k-CUT and MAX BISECTION. Algorithmica 18, pp. 67-81, 1997.
• [7] M.X. Goemans and D.P. Williamson. Improved approximation algorithms for maximum cut and satisfiability problems using semidefinite programming. Journal of ACM, 42, pp. 1115-1145,1995.
• [8] F. Hadlock. Finding a maximum cut of a planar graph in polynomial time. SIAM J. Comput. Vol. 4, No. 3, pp. 221-225,1975.
• [9] MAX-CUT in Cubic Graphs. E. Halperin, D. Livnat, and U. Zwick. Proc. 13th ACM-SIAM SODA (2002), pp. 506-513.
• [10] E. Halperin and U. Zwick, Improved approximation algorithms for maximum graph bisection problems. Manuscript, 2000.
• [11] K. Jansen, M. Karpinski and A. Lingas and E. Seidel. Polynomial Time Approximation Schemes for MAXBISECTION on Planar and Geometric Graphs. Proc. STACS'2001, February 2001, Lecture Notes in Computer Science, Springer Verlag.
• [12] S. Khanna and R. Motwani. Towards a Syntactic Characterization of PTAS. Proceedings of the 28th ACM STOC, 1996, pp. 329-337.
• [13] R.J. Lipton and R.E. Tarjan. Applications of a planar separator theorem. SIAM J. Comput. Vol. 9, No. 3, pp.615-627,1980.
• [14] S. Mahajan and J. Ramesh. Derandomizing semidefinite programming based approximation algorithms. Proceedings of the 36th IEEE FOCS, pp. 162-169,1995.
• [15] Y. Ye, A 0.699 - approximation algorithm for Max-Bisection, Submitted to Math Programming, available at URL http://dollar.biz.uiowa.edu/col/ye, 1999