Abstract
We consider the DENSE-n/2-SUBGRAPH problem, i.e., determine a block of half number nodes from a weighted graph such that the sum of the edge weights, within the subgraph induced by the block, is maximized. We prove that a strengthened semidefinite relaxation with a mixed rounding technique yields a 0.586 approximations of the problem. The previous best-known results for approximating this problem are 0.25 using a simple coin-toss randomization, 0.48 using a semidefinite relaxation, 0.5 using a linear programming relaxation or another semidefinite relaxation. In fact, an un-strengthened SDP relaxation provably yields no more than 0.5 approximation. We also consider the complement of the graph MIN-BISECTION problem, i.e., partitioning the nodes into two blocks of equal cardinality so as to maximize the weights of non-crossing edges. We present a 0.602 approximation of the complement of MIN-BISECTION.
Similar content being viewed by others
References
Bertsimas, D. and Ye, Y. (1998), Semidefinite relaxations, multivariate normal distributions, and order statistics. In: Du, D.-Z. and Pardalos, P.M. (eds.), Handbook of Combinatorial Opimization, Kluwer Academic Publishers, Dordrecht, Vol. 3, pp. 1–19.
Choi, C.C. and Ye, Y. (2000), Application of semidefinite programming to circuit partitioning. In: Pardalos, P.M. (ed.), Approximation and Complexity in Numerical Optimization. Kluwer Academic Publishers, Dordrecht, pp. 130–137.
Even, G., Naor, J., Rao, S. and Schieber, B. (1997), Fast approximate graph partitioning algorithms. 8th SODA, 639–648.
Feige, U. and Goemans, M.X. (1995), Approximating the value of two prover proof systems, with applications to MAX 2SAT and MAX DICUT. Proceedings of the Third Israel Symposium on Theory of Computing and Systems, pp. 182–189.
Feige, U. and Seltser, M. (1997), On the densest k-subgraph problem. Technical report, Department of Applied Mathematics and Computer Science, The Weizmann Institute, Rehovot, September.
Feige, U. and Langberg, M. (2001), Approximation algorithms for maximization problems arising in graph partitioning. Journal of Algorithms 41, 174–211.
Feige, U. and Krauthgamer, R. (2000), A polylogarithmic approximation of the minimum bisection. 41st FOCS 105–115.
Frieze, A. and Jerrum, M. (1997), Improved approximation algorithms for max k-cut and max bisection. Algorithmica 18, 67–81.
Garg, N., Saran, H. and Vazirani, V.V. (1994), Finding separator cuts in planar graphs within twice the optimal. 35th FOCS 14–23.
Goemans, M.X. (1996), Mathematical programming and approximation algorithms. Lecture given at the Summer School on Approximation Solution of Hard Combinatorial Problems, Udine, September.
Goemans, M.X. and Williamson, D.P. (1995), Improved approximation algorithms for maximum cut and satisfiability problems using semidefinite programming. Journal of the ACM 42, 1115–1145.
Leighton, T. and Rao, S. (1988), An approximate max-flow min-cut theorems for uniform multicommodity flow problem with applications to approximation algorithms. 28th FOCS 256–269.
Leighton, T. and Rao, S. (1999), Multicommodity max-flow, min-cut theorems and their use in designing approximation algorithms. Journal of the ACM 46, 787–832.
Mahajan, S. and Ramesh, H. (1999), Derandomizing semidefinite programming based approximation algorithms. SIAM J. of Computing 28, 1641–1663.
Nesterov, Y.E. (1998), Semidefinite relaxation and nonconvex quadratic optimization. Optimization Methods and Software 9, 141–160.
Shmoys, D.B. (1996), Cut problems and their application to divide-and-conquer. In: Hochbaum, D.S. (ed.), Approximation Algorithm for NP-hard Problems. PWS Publishers, pp. 192–235.
Srivastav, A. and Wolf, K. (1998), Finding dense subgraphs with semidefinite programming. In: Jansen, K. and Rolim, J. (eds.), Approximation Algorithms for Combinatorial Optimization, pp. 181–191.
Williamson, D.P. (1998), Lecture notes on approximation algorithms. Lecture Note, Fall.
Ye, Y. (2001), A 0.699-approximation algorithm for Max-Bisection. Mathematical Programming 90, 101–111.
Ye, Y. (1999), Approximating quadratic programming with bound and quadratic constraints. Mathematical Programming 84, 219–226.
Zwick, U. (1999), Outward rotations: a tool for rounding solutions of semidefinite programming relaxations, with applications to Max-Cut and other problems. 31th STOC 679–687.
Author information
Authors and Affiliations
Rights and permissions
About this article
Cite this article
Ye, Y., Zhang, J. Approximation of Dense-n/2-Subgraph and the Complement of Min-Bisection. Journal of Global Optimization 25, 55–73 (2003). https://doi.org/10.1023/A:1021390231133
Issue Date:
DOI: https://doi.org/10.1023/A:1021390231133