A 2-approximation for the maximum satisfying bisection problem
Zenklusen, Rico; Ries, Bernard (2011), A 2-approximation for the maximum satisfying bisection problem, European Journal of Operational Research, 210, 2, p. 169-175. http://dx.doi.org/10.1016/j.ejor.2010.11.010
TypeArticle accepté pour publication ou publié
Journal nameEuropean Journal of Operational Research
MetadataShow full item record
Abstract (EN)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 midV1mid = midV2mid, 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 View the MathML source-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.
Subjects / KeywordsComplexity theory; Vertex partition; Approximation algorithm
Showing items related by title and author.
Blockers and transversalsnext term in some previous termsubclasses of bipartite graphs: When caterpillars are dancing on a gridnext term Bentz, Cédric; Costa, Marie-Christine; Ries, Bernard; de Werra, Dominique; Picouleau, Christophe; Zenklusen, Rico (2010) Article accepté pour publication ou publié