.png){kind=icon}
.png){kind=icon}
Return
A 2-approximation for the maximum satisfying bisection problem
.png){kind=icon}
OA
AI
DOI：10.1016/j.ejor.2010.11.010.png)
.png){kind=icon}
.png){kind=icon}
Share.png){kind=icon}
Save
Abstract
En 中文
Given a graph G = (V,E), a satisfying bisection of G is a partition of the vertex set V into two sets V-1, V-2, such that vertical bar V-1 vertical bar = vertical bar V-2 vertical bar and such that every vertex nu is an element of 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 NP-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. (C) 2010 Elsevier B.V. All rights reserved.
Keywords:
Approximation algorithm
Vertex partition
Complexity theory
AI Summary
Key information extracted from the uploaded paper, including a brief overview, abstract, background, key highlights, visual analysis, and future outlook.
Journal
IF:
6
Papers:
2.2W
Citations:
6.4W