Multilevel algorithms for linear ordering problems

ABSTRACT

Linear ordering problems are combinatorial optimization problems that deal with the minimization of different functionals by finding a suitable permutation of the graph vertices. These problems are widely used and studied in many practical and theoretical applications. In this paper, we present a variety of linear--time algorithms for these problems inspired by the Algebraic Multigrid approach, which is based on weighted-edge contraction. The experimental result for four such problems turned out to be better than every known result in almost all cases, while the short (linear) running time of the algorithms enables testing very large graphs.

REFERENCES

• 1: Bar-Yehuda, R., Even, G., Feldman, J., and Naor, J. 2001. Computing an optimal orientation of a balanced decomposition tree for linear arrangement problems. J. Graph Algorithms Appl. 5, 4, 1--27.
• 2: Barnard, S., Pothen, A., and Simon, H. 1995. A spectral algorithm for envelope reduction of sparse matrices. Numerical Linear Algebra Appl. 2, 4, 317--334.
• 3: Brandt, A. 1986. Algebraic multigrid theory: The symmetric case. J. Appl. Math. Comp. 19, 23--56. Preliminary proceedings of the International Multigrid Conference, April 6--8, 1983, Copper Mountain, CO.
• 4: Brandt, A. 2001. Multiscale scientific computation: Review 2001. In Multiscale and Multiresolution Methods (Proceeding of the Yosemite Educational Symposium, October 2000), T. Barth, R. Haimes, and T. Chan, Eds. Springer-Verlag.
• 5: Brandt, A. and Ron, D. 2003. Chapter 1 : Multigrid solvers and multilevel optimization strategies. In Multilevel Optimization and VLSICAD, J. Cong and J. R. Shinnerl, Eds. Kluwer, Boston, MA.
• 6: Brandt, A., McCormick, S., and Ruge, J. 1982. Algebraic multigrid (AMG) for automatic multigrid solution with application to geodetic computations. Tech. Rep., Institute for Computational Studies, Fort Collins, CO, POB 1852.
• 7: Brandt, A., McCormick, S., and Ruge, J. 1984. Algebraic multigrid (AMG) for sparse matrix equations. In Sparsity and its Applications, D. J. Evans, Ed. Cambridge University Press, Cambridge. 257--284.
• 8: Brandt, A., Ron, D., and Amit, D. 1986. Multi-level approaches to discrete-state and stochastic problems. In Multigrid Methods II, W. Hackbush and U. Trottenberg, Eds. Springer-Verlag, New York, 66--99.
• 9: Briggs, W. L., Henson, V. E., and McCormick, S. F. 2000. A multigrid tutorial: second edition. Society for Industrial and Applied Mathematics, Philadelphia, PA.
• 10: Campos, V., Glover, F., Laguna, M., and Martí, R. 2001. An experimental evaluation of a scatter search for the linear ordering problem. J. Global Optimization 21, 4, 397--414.
• 11: Caprara, A. and González, J. J. S. 2005. Laying out sparse graphs with provably minimum bandwidth. INFORMS J. Comput. 17, 3, 356--373.
• 12: Cheng, C.-K. 1987. Linear placement algorithm and applications to VLSI design. Network 17, 4, 439--464.
• 13: Corso, G. M. D. and Romani, F. 2001a. Heuristic spectral techniques for the reduction of bandwidth and work-bound of sparse matrices. Numerical Algorithms 28, 1--4 (Dec.), 117--136.
• 14: Corso, G. M. D. and Romani, F. 2001b. Heuristic spectral techniques for the reduction of bandwidth and work-bound of sparse matrices. Tech. Rep. TR-01-02, Universitá di Piza, Dipartimento di Informatica.
• 15: Cuthill, E. and McKee, J. 1969. Reducing the bandwidth of sparse symmetric matrices. In Proceedings of the 1969 24th national conference. ACM Press, New York. 157--172.
• 16: Davis, T. 1997. University of florida sparse matrix collection. NA Digest 97, 23.
• 17: Díaz, J., Petit, J., and Serna, M. 2002. A survey of graph layout problems. ACM Comput. Surv. 34, 3, 313--356.
• 18: Dueck, G. W. and Jeffs, J. 1995. A heuristic bandwidth reduction algorithm. J. Combinatorial Math. Combinatorial Comput. 18, 97--108.
• 19: Garey, M. R., Johnson, D. S., and Stockmeyer, L. 1974. Some simplified np-complete problems. In STOC'74: Proceedings of the 6th Annual ACM Symposium on Theory of Computing. ACM Press, New York. 47--63.
• 20: George, A. and Pothen, A. 1997. An analysis of spectral envelope reduction via quadratic assignment problems. SIAM J. Matrix Analysis Appl. 18, 3, 706--732.
• 21: Horton, S. B. 1997. The optimal linear arrangement problem: Algorithms and approximation. Ph.D. thesis, Georgia Institute of Technology.
• 22: Hu, Y. F. and Scott, J. A. 2001. A multilevel algorithm for wavefront reduction. SIAM J. Sci. Comput. 23, 4, 1352--1375.
• 23: Juvan, M. and Mohar, B. 1992. Optimal linear labelings and eigenvalues of graphs. Discrete Appl. Math. 36, 2, 153--168.
• 24: Kirkpatrick, S. 1981. Models of disordered systems. In Lecture Notes in Physics 149, C. Castellani, Ed. Springer-Verlag, New York.
• 25: Koren, Y. and Harel, D. 2002. Multi-scale algorithm for the linear arrangement problem. In Proceedings of 28th International Workshop on Graph-Theoretic Concepts.
• 26: Lai, Y. and Williams, K. 1999. A survey of solved problems and applications on bandwidth, edgesum, and profile of graphs. J. Graph Theory 31, 75--94.
• 27: Lim, A., Rodrigues, B., and Xiao, F. 2006. Heuristics for matrix bandwidth reduction. Europ. J. Operational Res. 174, 1, 69--91.
• 28: Martí, R., M., L., F., G., and Campos, V. 2001. Reducing the bandwidth of a sparse matrix with tabu search. Eur. J. Oper. Res. 135, 2, 211--220.
• 29: Mehlhorn, K. and Näher, S. 1995. Leda: a platform for combinatorial and geometric computing. Commun. ACM 38, 1, 96--102.
• 30: Petit, J. 2003. Experiments on the minimum linear arrangement problem. ACM J. Experimental Algorithmics, 8.
• 31: Pinana, E., Plana, I., Campos, V., and Martí, R. 2004. GRASP and path relinking for the matrix bandwidth minimization. Europ. J. Operational Res. 153, 1, 200--210.
• 32: Pozo, R., Dongarra, J. J., and Walker, D. W. 1993. Lapack++: a design overview of object-oriented extensions for high performance linear algebra. In Supercomputing '93: Proceedings of the 1993 ACM/IEEE Conference on Supercomputing. ACM Press, New York. 162--171.
• 33: Ron, D. 1990. Ph.D. thesis. development of fast numerical solvers for problems in optimization and statistical mechanics. Ph.D. thesis, The Weizmann Institute of Science.
• 34: Ron, D., Wishko-Stern, S., and Brandt, A. 2005. An algebraic multigrid based algorithm for bisectioning general graphs. Tech. Rep. MCS05-01, Department of Computer Science and Applied Mathematics, The Weizmann Institute of Science.
• 35: Ruge, J. and Stüben, K. 1987. Algebraic Multigrid. SIAM, 73--130.
• 36: Safro, I. Homepage of our projects. http://www.wisdom.weizmann.ac.il/~safro.
• 37: Safro, I., Ron, D., and Brandt, A. 2006a. Graph minimum linear arrangement by multilevel weighted edge contractions. J. Algorithms 60, 1, 24--41.
• 38: Safro, I., Ron, D., and Brandt, A. 2006b. Multilevel algorithm for the minimum 2-sum problem. J. Graph Algorithms Appl. 10, 2, 237--258.
• 39: Shahrokhi, F., Sýkora, O., Székely, L. A., and Vrto, I. 2001. On bipartite drawings and the linear arrangement problem. SIAM J. Comput. 30, 6, 1773--1789.
• 40: Sharon, E., Brandt, A., and Basri, R. 2000. Fast multiscale image segmentation. In Proceedings IEEE Conference on Computer Vision and Pattern Recognition. 70--77.
• 41: Stüben, K. 2001a. An introduction to algebraic multigrid. Academic Press, New York. 413--532.
• 42: Stüben, K. 2001b. A review of algebraic multigrid. J. Comput. Appl. Math. 128, 1-2, 281--309.

INDEX TERMS

Primary Classification:
  G. Mathematics of Computing
  G.2 DISCRETE MATHEMATICS
      G.2.2 Graph Theory

General Terms:
Algorithms, Design, Experimentation, Performance, Theory

Keywords:
Multilevel algorithm, algebraic multigrid, linear ordering