Abstract
LetG=(N,E) be an undirected graph. We present several new techniques for partitioning the node setN intok disjoint subsets of specified sizes. These techniques involve eigenvalue bounds and tools from continuous optimization. Comparisons with examples taken from the literature show these techniques to be very successful.
Article PDF
Similar content being viewed by others
Avoid common mistakes on your manuscript.
References
E.R. Barnes, An algorithm for partitioning the nodes of a graph, SIAM J. Alg. Discr. Math. 3(1982)541–550.
E.R. Barnes and A.J. Hoffman, Partitioning, spectra, and linear programming, in:Progress in Combinatorial Optimization, ed. W.E. Pulleyblank (Academic Press, 1984) pp. 13–25.
E.R. Barnes, A. Vannelli and J.Q. Walker, A new heuristic for partitioning the nodes of a graph, SIAM J. Discr. Math. 1(1988)299–305.
R.B. Boppana, Eigenvalues and graph bisection: An average case analysis, in:Proc. 28th Annual Symp. on Computer Science (IEEE, 1987) pp. 280–285.
N. Christofides and P. Brooker, The optimal partitioning of graphs, SIAM J. Appl. Math. 30(1976)55–69.
M. Conforti, M.R. Rao and S. Sassano, The equipartition polytope, Math. Progr. 49(1990)49–90.
J. Cullum, W.E. Donath and P. Wolfe, The minimization of certain nondifferentiable sums of eigenvalues of symmetric matrices, Math. Progr. Study 3(1975)35–55.
Ch. Delorme and S. Poljak, Combinatorial properties and the complexity of a max-cut approximation, Euro. J. Combinatorics 14(1993)313–333.
Ch. Delorme and S. Poljak, Laplacian eigenvalues and the maximum cut problem, Math. Progr. 62(1993)557–574.
W.E. Donath and A.J. Hoffman, Lower bounds for the partitioning of graphs, IBM J. Res. Develop. 17(1973)420–425.
J. Falkner, F. Rendl and H. Wolkowicz, A computational study of graph partitioning, Math. Progr. 66(1994)211–240.
W. Gander, Least squares with a quadratic constraint, Numer. Math. 36(1981)291–307.
W. Gander, G.H. Golub and U. von Matt, A constrained eigenvalue problem, Lin. Alg. Appl. 114/115(1989)815–839.
D.M. Gay, Computing optimal locally constrained steps, SIAM J. Sci. Stat. Comput. 2(1981)186–197.
B. Gollan, Eigenvalue perturbations and nonlinear parametric optimization, Math. Progr. Studies 30(1987)67–81.
S.W. Hadley, Continuous optimization approaches for the quadratic assignment problem, Ph.D. Thesis, University of Waterloo, Canada (1989).
S.W. Hadley, F. Rendl and H. Wolkowicz, A new lower bound via projection for the quadratic assignment problem, Math. Oper. Res. 17(1992)727–739.
Ch. Helmberg, B. Mohar, S. Poljak and F. Rendl, A spectra approach to bandwidth and separator problems in graphs, Technical Report, Graz (1992).
A. Kamath and N. Karmakar, A continuous approach to computer upper bounds in quadratic maximization problems with integer constraints,Proc. Conf. on Recent Advances in Global Optimization, ed. Floudas and Pardalos (1991) pp. 125–140.
A. Kamath and N. Karmakar, A continuous method for computing bounds in integer quadratic optimization problems, J. Global Optim. 2(1992)229–241.
T. Lengauer,Combinatorial Algorithms for Integrated Circuit Layout (Wiley, Chichester, 1990).
B. Mohar and S. Poljak, Eigenvalues and the max-cut problem, Czech. Math. J. 40(115)(1990) 343–352.
J.J. Moré and D.C. Sorensen, Computing a trust region step, SIAM J. Sci. Statist. Comput. 4(1983)553–572.
M.L. Overton and R.S. Womersley, On the sum of the largest eigenvalues of a symmetric matrix, SIAM J. Matrix Anal. Appl. 13(1992)41–45.
S. Poljak and F. Rendl, Solving the max-cut problem using eigenvalues, Report 91735, Bonn (1991).
S. Poljak and F. Rendl, Nonpolyhedral relaxations of graoh bisection problems, Report CDLDO-13, University of Technology, Graz (1992).
A. Pothen, H.D. Simon and K.-P. Liou, Partitioning sparse matrices with eigenvectors of graphs, SIAM J. Matrix Anal. Appl. 11(1990)430–452.
F. Rendl and H. Wolkowicz, Applications of parametric programming and eigenvalue maximization to the quadratic assignment problem, Math. Progr. 53(1992)63–78.
C. Roucairol and P. Hansen, Cut cost minimization in graph partitioning, in:Numerical and Applied Mathematics, ed. C. Brezinski (J.C. Baltzer, 1989) pp. 585–587.
H. Schramm and J. Zowe, A version of the Bundle idea for minimizing a nonsmooth function: Conceptual idea, convergence analysis, numerical results, SIAM J. Optim. 2(1992)121–152.
Author information
Authors and Affiliations
Rights and permissions
About this article
Cite this article
Rendl, F., Wolkowicz, H. A projection technique for partitioning the nodes of a graph. Ann Oper Res 58, 155–179 (1995). https://doi.org/10.1007/BF02032130
Issue Date:
DOI: https://doi.org/10.1007/BF02032130