Show simple item record

dc.contributor.authorZenklusen, Rico
dc.contributor.authorRies, Bernard
dc.date.accessioned2011-05-04T14:45:56Z
dc.date.available2011-05-04T14:45:56Z
dc.date.issued2011
dc.identifier.urihttps://basepub.dauphine.fr/handle/123456789/6184
dc.language.isoenen
dc.subjectComplexity theoryen
dc.subjectVertex partitionen
dc.subjectApproximation algorithmen
dc.subject.ddc511en
dc.titleA 2-approximation for the maximum satisfying bisection problemen
dc.typeArticle accepté pour publication ou publié
dc.contributor.editoruniversityotherDepartment of Mathematics, MIT;États-Unis
dc.description.abstractenGiven 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.en
dc.relation.isversionofjnlnameEuropean Journal of Operational Research
dc.relation.isversionofjnlvol210en
dc.relation.isversionofjnlissue2en
dc.relation.isversionofjnldate2011
dc.relation.isversionofjnlpages169-175en
dc.relation.isversionofdoihttp://dx.doi.org/10.1016/j.ejor.2010.11.010en
dc.description.sponsorshipprivateouien
dc.relation.isversionofjnlpublisherElsevieren
dc.subject.ddclabelAnalyseen


Files in this item

FilesSizeFormatView

There are no files associated with this item.

This item appears in the following Collection(s)

Show simple item record