×

zbMATH — the first resource for mathematics

A multilevel bilinear programming algorithm for the vertex separator problem. (English) Zbl 1394.90546
Summary: The Vertex Separator Problem for a graph is to find the smallest collection of vertices whose removal breaks the graph into two disconnected subsets that satisfy specified size constraints. The Vertex Separator Problem was formulated in the paper [the first two authors, Eur. J. Oper. Res. 240, No. 2, 328–337 (2015; Zbl 1357.90166)] as a continuous (non-concave/non-convex) bilinear quadratic program. In this paper, we develop a more general continuous bilinear program which incorporates vertex weights, and which applies to the coarse graphs that are generated in a multilevel compression of the original Vertex Separator Problem. We develop a method for improving upon a given vertex separator by applying a Mountain Climbing Algorithm to the bilinear program using an incidence vector for the separator as a starting guess. Sufficient conditions are developed under which the algorithm can improve upon the starting guess after at most two iterations. The refinement algorithm is augmented with a perturbation technique to enable escapes from local optima and is embedded in a multilevel framework for solving large scale instances of the problem. The multilevel algorithm is shown through computational experiments to perform particularly well on communication and collaboration networks.

MSC:
90C35 Programming involving graphs or networks
90C27 Combinatorial optimization
90C20 Quadratic programming
90C06 Large-scale problems in mathematical programming
PDF BibTeX XML Cite
Full Text: DOI arXiv
References:
[1] Acer, S., Kayaaslan, E., Aykanat, C.: A recursive bipartitioning algorithm for permuting sparse square matrices into block diagonal form with overlap. SIAM J. Sci. Comput. 35(1), C99-C121 (2013). doi:10.1137/120861242 · Zbl 1263.05059
[2] Ashcraft, C.C., Liu, J.W.H.: A partition improvement algorithm for generalized nested dissection. Technical Report BCSTECH-94-020, Boeing Computer Services, Seattle, WA (1994) · Zbl 0819.65079
[3] Benlic, U., Hao, J.: Breakout local search for the vertex separator problem. In: Proceedings of the Twenty-Third International Joint Conference on Artificial Intelligence (2013) · Zbl 1401.90108
[4] Brandt, A; Ron, D; Cong, J (ed.); Shinnerl, JR (ed.), Chapter 1: multigrid solvers and multilevel optimization strategies, (2003), Alphen
[5] Bui, T; Jones, C, Finding good approximate vertex and edge partitions is NP-hard, Inf. Process. Lett., 42, 153-159, (1992) · Zbl 0764.68061
[6] Buluç, A; Meyerhenke, H; Safro, I; Sanders, P; Schulz, C; Kliemann, L (ed.); Sanders, P (ed.), Recent advances in graph partitioning, 117-158, (2016), Berlin
[7] Burmester, M; Desmedt, Y; Wang, Y; Luby, M (ed.); Rolim, J (ed.); Serna, M (ed.), Using approximation hardness to achieve dependable computation, No. 1518, 172-186, (1998), Berlin
[8] Chen, J; Safro, I, Algebraic distance on graphs, SIAM J. Sci. Comput., 33, 3468-3490, (2011) · Zbl 1235.05042
[9] Davis, T.A.: Direct Methods for Sparse Linear Systems. SIAM, Philadelphia (2006) · Zbl 1119.65021
[10] Davis, TA, University of florida sparse matrix collection, ACM Trans. Math. Softw., 38, 1-25, (2011) · Zbl 1365.65123
[11] Davis, TA; Hager, WW; Hungerford, JT, The separable convex quadratic knapsack problem, ACM Trans. Math. Softw., 42, 1-25, (2016) · Zbl 1369.65072
[12] Evrendilek, C, Vertex separators for partitioning a graph, Sensors, 8, 635-657, (2008)
[13] Feige, U; Hajiaghayi, M; Lee, J, Improved approximation algorithms for vertex separators, SIAM J. Comput., 38, 629-657, (2008) · Zbl 1172.68063
[14] Fiduccia, C.M., Mattheyses, R.M.: A linear-time heuristic for improving network partitions. In: Proceedings of 19th Design Automation Conference, pp. 175-181. Las Vegas, NV (1982)
[15] Fukuyama, J, NP-completeness of the planar separator problems, J. Graph Algorithms Appl., 10, 317-328, (2006) · Zbl 1178.68378
[16] George, A., Liu, J.W.H.: Computer Solution of Large Sparse Positive Definite Systems. Prentice-Hall, Englewood Cliffs (1981) · Zbl 0516.65010
[17] Gilbert, JR; Zmijewski, E, A parallel graph partitioning algorithm for a message-passing multiprocessor, Intl. J. Parallel Program., 16, 498-513, (1987) · Zbl 0657.68073
[18] Hager, WW; Hungerford, JT, Optimality conditions for maximizing a function over a polyhedron, Math. Program., 145, 179-198, (2014) · Zbl 1298.90127
[19] Hager, WW; Hungerford, JT, Continuous quadratic programming formulations of optimization problems on graphs, Eur. J. Oper. Res., 240, 328-337, (2015) · Zbl 1357.90166
[20] Hendrickson, B., Leland, R.: A multilevel algorithm for partitioning graphs. In: Proceedings of Supercomputing ’95. IEEE (1995) · Zbl 0816.68093
[21] Hendrickson, B., Rothberg, E.: Effective sparse matrix ordering: just around the bend. In: Proceedings of 8th SIAM Conference on Parallel Processing for Scientific Computing (1997) · Zbl 0353.90069
[22] http://snap.stanford.edu/data/ · Zbl 0657.68073
[23] Karypis, G., Kumar, V.: METIS: unstructured graph partitioning and sparse matrix ordering system. Technical Report, Department of Computer Science, University of Minnesota (1995) · Zbl 1172.68063
[24] Karypis, G; Kumar, V, A fast and high quality multilevel scheme for partitioning irregular graphs, SIAM J. Sci. Comput., 20, 359-392, (1998) · Zbl 0915.68129
[25] Kayaaslan, E; Pinar, A; Catalyürek, U; Aykanat, C, Partitioning hypergraphs in scientific computing applications through vertex separators, SIAM J. Sci. Comput., 34, a970-a992, (2012) · Zbl 1245.05104
[26] Kernighan, BW; Lin, S, An efficient heuristic procedure for partitioning graphs, Bell Syst. Tech. J., 49, 291-307, (1970) · Zbl 0333.05001
[27] Kim, D., Frye, G.R., Kwon, S.S., Chang, H.J., Tokuta, A.O.: On combinatoric approach to circumvent internet censorship using decoy routers. In: Military Communications Conference, 2013. MILCOM 2013., pp. 1-6. IEEE (2013)
[28] Konno, H, A cutting plane algorithm for solving bilinear programs, Math. Program., 11, 14-27, (1976) · Zbl 0353.90069
[29] Leiserson, C., Lewis, J.: Orderings for parallel sparse symmetric factorization. In: Third SIAM Conference on Parallel Processing for Scientific Computing, pp. 27-31. SIAM Publications (1987) · Zbl 0764.68061
[30] Leiserson, C.: Area-efficient graph layout (for VLSI). In: Proceedings of 21st Annual Symposium on the Foundations of Computer Science, pp. 270-281. IEEE (1980) · Zbl 1245.05104
[31] Litsas, C., Pagourtzis, A., Panagiotakos, G., Sakavalas, D.: On the resilience and uniqueness of CPA for secure broadcast. In: IACR Cryptology ePrint Archive (2013)
[32] Miller, G; Teng, SH; Thurston, W; Vavasis, S, Geometric separators for finite element meshes, SIAM J. Sci. Comput., 19, 364-386, (1998) · Zbl 0914.65123
[33] Nocedal, J., Wright, S.J.: Numerical Optimization, 2nd edn. Springer, New York (2006) · Zbl 1104.65059
[34] Pothen, A; Simon, HD; Liou, K, Partitioning sparse matrices with eigenvectors of graphs, SIAM J. Matrix Anal. Appl., 11, 430-452, (1990) · Zbl 0711.65034
[35] Rendl, F., Sotirov, R.: The min-cut and vertex separator problem. Comput. Optim. Appl. (2017). doi:10.1007/s10589-017-9943-4 · Zbl 1393.90126
[36] Ron, D; Safro, I; Brandt, A, Relaxation-based coarsening and multiscale graph organization, Multiscale Model. Simul., 9, 407-423, (2011) · Zbl 1219.68125
[37] Safro, I., Sanders, P., Schulz, C.: Advanced coarsening schemes for graph partitioning. ACM J. Exp. Algorithm. 19(2), Article 2.2 (2014) · Zbl 1347.68355
[38] Safro, I; Ron, D; Brandt, A, Graph minimum linear arrangement by multilevel weighted edge contractions, J. Algorithms, 60, 24-41, (2006) · Zbl 1096.68687
[39] Ullman, J.: Computational Aspects of VLSI. Computer Science Press, Rockville (1984) · Zbl 0539.68021
[40] Vanderbei, R.J.: Linear Programming: Foundations and Extensions, 4th edn. Springer, Berlin (2014) · Zbl 1299.90243
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.