Improved approximation algorithms for MAX \(\frac{n}2\)-DIRECTED-BISECTION and MAX \(\frac{n}2\)-DENSE-SUBGRAPH

DOI10.1023/A:1026094110647zbMath1046.90094OpenAlexW424054382MaRDI QIDQ1430177

Zheng-Hai Huang, Li-ping Zhang, Da-Chuan Xu, Ji-ye Han

Publication date: 27 May 2004

Published in: Journal of Global Optimization (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1023/a:1026094110647

zbMATH Keywords

Semidefinite programmingmax \(\frac{n}2\)-dense-subgraphmax \(\frac{n}2\)-directed-bisectionPolynomial-time approximation algorithm

Mathematics Subject Classification ID

Approximation methods and heuristics in mathematical programming (90C59) Semi-infinite programming (90C34) Approximation algorithms (68W25)

Related Items (6)

Improved approximating \(2\)-CatSP for \(\sigma\geq 0.50\) with an unbalanced rounding matrix ⋮ An improved approximation algorithm for the \(2\)-catalog segmentation problem using semidefinite programming relaxation ⋮ A continuation algorithm for max-cut problem ⋮ An approximation algorithm for the balanced Max-3-Uncut problem using complex semidefinite programming rounding ⋮ Sensor network localization, Euclidean distance matrix completions, and graph realization ⋮ An improved semidefinite programming hierarchies rounding approximation algorithm for maximum graph bisection problems

This page was built for publication: Improved approximation algorithms for MAX \(\frac{n}2\)-DIRECTED-BISECTION and MAX \(\frac{n}2\)-DENSE-SUBGRAPH