Abstract
The minimum linear arrangement problem consists of finding an embedding of the nodes of a graph on the line such that the sum of the resulting edge lengths is minimized. The problem is among the classical NP-hard optimization problems and there has been extensive research on exact and approximative algorithms. In this paper, we introduce a new model based on binary variables d ijk that are equal to 1 if nodes i and j have distance k in the ordering. We analyze this model and point to connections and differences to a model using integer distance variables. Based on computational experiments, we argue that our model is worth further theoretical and practical investigation and that is has potentials yet to be examined.
This is a preview of subscription content, log in via an institution to check access.
Similar content being viewed by others
References
Adolphson D (1977) Single machine job sequencing with precedence constraints. SIAM J Comput 6(1):40–54
Amaral A, Letchford AN (2012) A polyhedral approach to the single row facility layout probles. Math Program, to appear
Caprara A, Letchford A, Salazar-Gonzáles J (2011a) Decorous lower bounds for minimum linear arrangement. INFORMS J Comput 23:26–40
Caprara A, Oswald M, Reinelt G, Schwarz R, Traversi E (2011b) Optimal linear arrangements using betweenness variables. Math Program Comput. doi:10.1007/s12532-011-0027-7
Chen P (1976) The entity-relationship model—toward a unified view of data. ACM Trans Database Syst 1:9–36
Díaz J, Petit J, Spirakis P (1998) Heuristics for the MinLA problem: am empirical and theoretical analysis (extended abstract). Working paper
Díaz J, Petit J, Serna M (2002) A survey on graph layout problems. ACM Comput Surv 34(3):313–356
Duff I, Grimes R, Lewis J (1992) User’s guide for the Harwell–Boeing sparse matrix collection. Technical report TR/PA/92/86, CERFACS, Toulouse, France
Even G, Naor J, Rao S, Schieber B (2000) Divide-and-conquer approximation algorithms via spreading metrics. J ACM 47(4):585–616
Even S, Shiloach Y (1978) NP-completeness of several arrangements problems. Technical report, TR-43, The Technicon, Haifa
Fernau H (2005) Parameterized algorithmics: a graph-theoretic approach. Habilitation thesis, University of Tübingen
Fernau H (2008) Parameterized algorithmics for linear arrangement problems. Discrete Appl Math 156(17):3166–3177
Gane C, Sarson T (1977) Structured systems analysis: tools and techniques, 1st edn. McDonnell Douglas Systems Integration Company
Gutin G, Rafiey A, Szeider S, Yeo A (2007) The linear arrangement problem parametrized above guaranteed value. Theory Comput Syst 41(3):521–538
Hanan M, Kurtzberg J (1972) A review of the placement and quadratic assignment problems. SIAM Rev 14(2):324–342
Harper L (1964) Optimal assignments of numbers to vertices. SIAM J Appl Math 12(1):131–135
Hassin R, Rubinstein S (2000) Approximation algorithms for maximum linear arrangement. In: Algorithm theory—SWAT 2000. Lecture notes in computer science, vol 1851. Springer, Berlin, pp 633–643
Horton S (1997) The optimal linear arrangement problem: algorithms and approximation. PhD thesis, Georgia Institute of Technology, USA
Ilog (2002) Cplex 8.1
Karp R (1993) Mapping the genome: some combinatorial problems arising in molecular biology. In: Proceedings of the twenty-fifth annual ACM symposium on theory of computing, pp 278–285
Koren Y, Harel D (2002) A multi-scale algorithm for the linear arrangement problem. In: Revised papers from the 28th international workshop on graph-theoretic concepts in computer science. Lecture notes in computer science, vol 2573, pp 296–309
Liu W, Vannelli A (1995) Generating lower bounds for the linear arrangement problem. Discrete Appl Math 59(2):137–151
Mitchison G, Durbin R (1986) Optimal numberings of an N×N array. SIAM J Algebr Discrete Methods 7(4):571–582
Petit J (2001) Layout problems. PhD thesis, Universitat Politécnica de Catalunya
Petit J (2003) Experiments on the minimum linear arrangement problem. ACM J Exp Algorithmics 8
Ravi R, Agrawal A, Klein P (1991) Ordering problems approximated: single-processor scheduling and interval graphs connection. Lect Notes Comput Sci 150:751–762
Safro I, Ron D, Brandt A (2006) Graph minimum linear arrangement by multilevel weighted edge contractions. J Algorithms 60(1):24–41
Schwarz R (2010) A branch-and-cut algorithm with betweenness variables for the linear arrangement problems. Master’s thesis, Universität Heidelberg
Seitz H (2010) Contributions to the minimum linear arrangement problem. PhD thesis, Universität Heidelberg
Serna M, Thilikos D (2005) Parameterized complexity for graph layout problems. Bull Eur Assoc Theor Comput Sci 86:41–65
Thienel S (1995) ABACUS: A Branch-And-CUt system. PhD thesis, Universtät zu Köln
Vannelli A, Rowan G (1986) An eigenvector based approach for multistack VLSI layout. In: Proceedings of the midwest symposium on circuits and systems, vol 29, pp 435–439
Author information
Authors and Affiliations
Corresponding author
Rights and permissions
About this article
Cite this article
Reinelt, G., Seitz, H. On a binary distance model for the minimum linear arrangement problem. TOP 22, 384–396 (2014). https://doi.org/10.1007/s11750-012-0263-7
Received:
Accepted:
Published:
Issue Date:
DOI: https://doi.org/10.1007/s11750-012-0263-7