Skip to main content
Log in

Approximation of Dense-n/2-Subgraph and the Complement of Min-Bisection

  • Published:
Journal of Global Optimization Aims and scope Submit manuscript

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.

This is a preview of subscription content, log in via an institution to check access.

Access this article

Price excludes VAT (USA)
Tax calculation will be finalised during checkout.

Instant access to the full article PDF.

Institutional subscriptions

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.

    Google Scholar 

  • 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.

    Google Scholar 

  • 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.

    Google Scholar 

  • Feige, U. and Langberg, M. (2001), Approximation algorithms for maximization problems arising in graph partitioning. Journal of Algorithms 41, 174–211.

    Google Scholar 

  • 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.

    Google Scholar 

  • 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.

    Google Scholar 

  • 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.

    Google Scholar 

  • Mahajan, S. and Ramesh, H. (1999), Derandomizing semidefinite programming based approximation algorithms. SIAM J. of Computing 28, 1641–1663.

    Google Scholar 

  • Nesterov, Y.E. (1998), Semidefinite relaxation and nonconvex quadratic optimization. Optimization Methods and Software 9, 141–160.

    Google Scholar 

  • 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.

    Google Scholar 

  • Ye, Y. (1999), Approximating quadratic programming with bound and quadratic constraints. Mathematical Programming 84, 219–226.

    Google Scholar 

  • 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.

Download references

Author information

Authors and Affiliations

Authors

Rights and permissions

Reprints 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

Download citation

  • Issue Date:

  • DOI: https://doi.org/10.1023/A:1021390231133

Navigation