scientific article; zbMATH DE number 1762086

MaRDI QIDQ4537699zbMATH OpenFDO

Authors Eran Halperin, Uri Zwick

Publication date 1 July 2002

zbMATH Keywords

semidefinite programmingapproximation algorithmsmaximum bisection

Mathematics Subject Classification ID

Programming involving graphs or networks (90C35) Graph theory (including graph drawing) in computer science (68R10) Semidefinite programming (90C22) Approximation algorithms (68W25)

Recommendations

• A unified framework for obtaining improved approximation algorithms for maximum graph bisection problems
• An improved semidefinite programming hierarchies rounding approximation algorithm for maximum graph bisection problems
• Improved approximation algorithms for MAX \(\frac{n}2\)-DIRECTED-BISECTION and MAX \(\frac{n}2\)-DENSE-SUBGRAPH
• Improved approximation algorithms for MAX \(k\)-CUT and MAX BISECTION
• Improved approximation algorithms for MAX k-cut and MAX BISECTION

Cited in

(19)

• Better Bounds for Graph Bisection
• scientific article; zbMATH DE number 2140434 (Why is no real title available?)
• An improved semidefinite programming hierarchies rounding approximation algorithm for maximum graph bisection problems
• Approximation algorithms for MAX RES CUT with limited unbalanced constraints
• An improved kernel for max-bisection above tight lower bound
• Approximation algorithm for MAX DICUT with given sizes of parts
• Better balance by being biased: a 0.8776-approximation for {\textsc{Max Bisection}}
• On approximation of max-vertex-cover
• An Enhancement of the Bisection Method Average Performance Preserving Minmax Optimality
• Complexity of approximating CSP with balance/hard constraints
• A unified framework for obtaining improved approximation algorithms for maximum graph bisection problems
• Improved approximation algorithms for MAX \(k\)-CUT and MAX BISECTION
• A .699-approximation algorithm for Max-Bisection.
• scientific article; zbMATH DE number 6401405 (Why is no real title available?)
• Approximation of dense-n/2-subgraph and the complement of min-bisection
• An Improved Semidefinite Programming Hierarchies Rounding Approximation Algorithm for Maximum Graph Bisection Problems
• Applications of the Dulmage--Mendelsohn Decomposition and Network Flow to Graph Bisection Improvement
• Improved approximation algorithms for the max-bisection and the disjoint 2-catalog segmentation problems
• Improved approximation algorithms for MAX \(\frac{n}2\)-DIRECTED-BISECTION and MAX \(\frac{n}2\)-DENSE-SUBGRAPH

This page was built for publication:

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4537699)