A 2-approximation for the maximum satisfying bisection problem

DOI10.1016/J.EJOR.2010.11.010zbMath1220.90153OpenAlexW2059601777MaRDI QIDQ531427

Rico Zenklusen, Bernard Ries

Publication date: 29 April 2011

Published in: European Journal of Operational Research (Search for Journal in Brave)

Full work available at URL: http://doc.rero.ch/record/328808/files/satiscopy.pdf

zbMATH Keywords

approximation algorithmcomplexity theoryvertex partition

Mathematics Subject Classification ID

Programming involving graphs or networks (90C35) Approximation methods and heuristics in mathematical programming (90C59)

Related Items (1)

An improved kernel for max-bisection above tight lower bound

Cites Work

• Approximation of satisfactory bisection problems
• Satisfactory graph partition, variants, and generalizations
• Algorithmic approach to the satisfactory graph partitioning problem
• Combinatorial optimization. Polyhedra and efficiency (3 volumes)
• The satisfactory partition problem
• Unnamed Item

This page was built for publication: A 2-approximation for the maximum satisfying bisection problem