 A 2-approximation for the maximum satisfying bisection problemBernard Ries and Rico Zenklusen European Journal of Operational Research, 2011, vol. 210, issue 2, 169-175 Abstract: Given a graph G = (V, E), a satisfying bisection of G is a partition of the vertex set V into two sets V1, V2, such that |V1| = |V2|, and such that every vertex v [set membership, variant] V has at least as many neighbors in its own set as in the other set. The problem of deciding whether a graph G admits such a partition is -complete. In Bazgan et al. (2008) [C. Bazgan, Z. Tuza, D. Vanderpooten, Approximation of satisfactory bisection problems, Journal of Computer and System Sciences 75 (5) (2008) 875-883], the authors present a polynomial-time 3-approximation for maximizing the number of satisfied vertices in a bisection. It remained an open problem whether one could find a (3 - c)-approximation, for c > 0 (see Bazgan et al. (2010) [C. Bazgan, Z. Tuza, D. Vanderpooten, Satisfactory graph partition, variants, and generalizations, European Journal of Operational Research 206 (2) (2010) 271-280]). In this paper, we solve this problem by presenting a polynomial-time 2-approximation algorithm for the maximum number of satisfied vertices in a satisfying bisection. Keywords: Approximation; algorithm; Vertex; partition; Complexity; theory (search for similar items in EconPapers) Downloads: (external link) Related works: Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text Persistent link: https://EconPapers.repec.org/RePEc:eee:ejores:v:210:y:2011:i:2:p:169-175 Access Statistics for this article European Journal of Operational Research is currently edited by Roman Slowinski, Jesus Artalejo, Jean-Charles. Billaut, Robert Dyson and Lorenzo Peccati More articles in European Journal of Operational Research from Elsevier |
Is your work missing from RePEc? Here is how to contribute.
Questions or problems? Check the EconPapers FAQ or send mail to .
EconPapers is hosted by the
School of Business at Örebro University.