Lower and upper bounds for the linear arrangement problem on interval graphs
RAIRO - Operations Research - Recherche Opérationnelle, Tome 52 (2018) no. 4-5, pp. 1123-1145.

We deal here with the Linear Arrangement Problem (LAP) on interval graphs, any interval graph being given here together with its representation as the intersection graph of some collection of intervals, and so with related precedence and inclusion relations. We first propose a lower bound LB, which happens to be tight in the case of unit interval graphs. Next, we introduce the restriction PCLAP of LAP which is obtained by requiring any feasible solution of LAP to be consistent with the precedence relation, and prove that PCLAP can be solved in polynomial time. Finally, we show both theoretically and experimentally that PCLAP solutions are a good approximation for LAP on interval graphs.

Reçu le :
Accepté le :
DOI : 10.1051/ro/2017011
Classification : 90C27
Mots-clés : Interval Graphs, Linear Ordering
Quilliot, Alain 1 ; Rebaine, Djamal 1 ; Toussaint, Hélène 1

1 
@article{RO_2018__52_4-5_1123_0,
     author = {Quilliot, Alain and Rebaine, Djamal and Toussaint, H\'el\`ene},
     title = {Lower and upper bounds for the linear arrangement problem on interval graphs},
     journal = {RAIRO - Operations Research - Recherche Op\'erationnelle},
     pages = {1123--1145},
     publisher = {EDP-Sciences},
     volume = {52},
     number = {4-5},
     year = {2018},
     doi = {10.1051/ro/2017011},
     mrnumber = {3878613},
     zbl = {1411.90299},
     language = {en},
     url = {http://www.numdam.org/articles/10.1051/ro/2017011/}
}
TY  - JOUR
AU  - Quilliot, Alain
AU  - Rebaine, Djamal
AU  - Toussaint, Hélène
TI  - Lower and upper bounds for the linear arrangement problem on interval graphs
JO  - RAIRO - Operations Research - Recherche Opérationnelle
PY  - 2018
SP  - 1123
EP  - 1145
VL  - 52
IS  - 4-5
PB  - EDP-Sciences
UR  - http://www.numdam.org/articles/10.1051/ro/2017011/
DO  - 10.1051/ro/2017011
LA  - en
ID  - RO_2018__52_4-5_1123_0
ER  - 
%0 Journal Article
%A Quilliot, Alain
%A Rebaine, Djamal
%A Toussaint, Hélène
%T Lower and upper bounds for the linear arrangement problem on interval graphs
%J RAIRO - Operations Research - Recherche Opérationnelle
%D 2018
%P 1123-1145
%V 52
%N 4-5
%I EDP-Sciences
%U http://www.numdam.org/articles/10.1051/ro/2017011/
%R 10.1051/ro/2017011
%G en
%F RO_2018__52_4-5_1123_0
Quilliot, Alain; Rebaine, Djamal; Toussaint, Hélène. Lower and upper bounds for the linear arrangement problem on interval graphs. RAIRO - Operations Research - Recherche Opérationnelle, Tome 52 (2018) no. 4-5, pp. 1123-1145. doi : 10.1051/ro/2017011. http://www.numdam.org/articles/10.1051/ro/2017011/

[1] S. Achouri, T. Bossart and A. Munier−Kordon, A polynomial algorithm for MINDSC on a subclass of series parallel graphs. RAIRO: OR 49 (2009) 145–156. | DOI | Numdam | MR | Zbl

[2] N. Ailon, M. Charikar and A. Newman, Aggregating inconsistent information: ranking and clustering. Proc. of 37th ACM Symp. Theory Comput. (STOC) (2005) 684–693. | MR | Zbl

[3] C. Berge, Graphes et Hypergraphes. Dunod Ed, Paris (1974). | MR | Zbl

[4] F. Barahona and A.R. Mahjoub, On the cut polytope. Math. Program. 36 (1986) 157–173. | DOI | MR | Zbl

[5] A. Caprara, Lower bounds for the minimum linear arrangement of a graph. Electronic Notes Discrete Math. 36 (2010) 843–849. | DOI | Zbl

[6] A. Caprara, A. Letchford and J. Salazar, Decorous lower bounds for minimum linear arrangement. INFORMS J. Comput. 23 (2011) 26–40. | DOI | MR | Zbl

[7] F.K. Chung, On optimal linear arrangement of trees. Comput. Maths. Appl. 11 (1984) 43–60. | MR | Zbl

[8] V. Chvatal and C. Ebenegger, A note on line digraphs and the directed Max-Cut problem. Discrete Appl. Math. 29 (1990) 165–170. | DOI | MR | Zbl

[9] J. Cohen, F. Fomin, P. Heggernes, D. Kratsch and G. Kucherov, Optimal linear arrangement of interval graphs. Proc. of MFCS’06. Springer Verlag Berlin, Heidelberg (2006). | MR | Zbl

[10] D.G. Corneil, H. Kim, S. Natarajan, S. Olariu and A.P. Sprague, Simple linear time recognition of unit interval graphs. Information Processing Lett. 55 (1995) 99–104. | DOI | MR | Zbl

[11] J. Diaz, J. Petit and M. Serna, A survey on graph layout problems. ACM Comput. Surveys 34 (2002) 313–356. | DOI

[12] Even S., Shiloach Y., NP-Completeness of Several Arrangement Problems. Technical Report #43. Computer Science Department, The Technion, Haifa, Israel (1975).

[13] P. Fishburn, P. Tetali and P. Winkler, Optimal linear arrangement of a grid. Disc. Math. 213 (2000) 123–139. | DOI | MR | Zbl

[14] G.N. Frederickson and S.E. Hambrusch, Planar linear arrangements of outerplanar graphs. IEEETCS: IEEE Trans. Circuits Syst. 35 (1988) 323–333. | MR | Zbl

[15] M.R. Garey and D.S. Johnson, Computers and intractability: a guide to the theory of NP-completeness. Freeman and Co., New York (1979). | MR | Zbl

[16] M. Grotschel, The Sharpest Cut, MPS-SIAM Series on Optimization (2004). | Zbl

[17] A. Guenoche, B. Vandeputte−Riboud and J.-B.Denis, Selecting varieties using a series of trials and a combinatorial ordering method. Agronomy 14 (1994) 363–375. | DOI

[18] S.B. Horton, The optimal linear arrangement problem: algorithms and approximation. Ph.D. Thesis, Georgia Institute of Technology (1997).

[19] S.B. Horton, R.G. Parker and R.B. Borie, On minimum cuts and the linear arrangement problem. Discrete Appl. Math. 103 (2000) 127–139. | DOI | MR | Zbl

[20] O. Hudry, Complexity of voting procedures, in Encyclopedia of complexity and System Sciences. Edited by R. Meyers. Springer (2009). | DOI | Zbl

[21] S. Ilya, The minimum linear arrangement problem, M. Sc. thesis, Weismann Institute, Haifa, Israel (2003).

[22] Y. Koren and D. Harel, A multi-scale algorithm for the linear arrangement problem. In Revised Papers from the 28th International Workshop on Graph-Theoretic Concepts in Computer Science, WG ’02. Springer Verlag (2002) 296–309. | MR | Zbl

[23] A. Lad, R. Ghani and Y. Yang and B. Kisiel, Towards optimal ordering of prediction task. Proc. of SIAM Int. Conf. Datamining SDM09 (2009) 883–894.

[24] W. Liu and A. Vannelli, Generating lower bounds for the linear arrangement problem. Discrete Appl. Math. 59 (1995) 137–151. | DOI | MR | Zbl

[25] J. Petit, Approximation heuristics and benchmarking for the MinLA problem. Edited by R. Battiti and A. Bertossi. In Alex ’98 Proceedings, Univ. di Trento (1998) 112–128.

[26] J. Petit, Experiments on the minimum linear arrangement problem. ACM J. Exp. Algorithmics 8 (2003) 25–38. | DOI | MR | Zbl

[27] J. Petit, Addenda to the survey of layout problems. Bull. Eur. Assoc. Theor. Comput. Sci. 105 (2011) 177–201. | MR | Zbl

[28] P. Raoufi, H. Rostami and H. Bagherinezhad, An optimal time algorithm for the minimum linear arrangement of chord graphs. J. Infor. Syst. 238 (2013) 212–220. | MR | Zbl

[29] E. Rodriguez−Tello, J.-K. Hao and J. Torres−Jimenez, An effective two-stage simulated annealing algorithm for the Minimum Linear Arrangement problem. Comput. Oper. Res. 35 (2008) 3331–3346. | DOI | Zbl

[30] R. Schwarz, A branch-and-cut algorithm with betweenness variables for the Linear Arrangement problem. Diplomarbeit. Universität Heidelberg (2010).

[31] A. Van Zuylen and D.B. Williamson, Deterministic algorithms for rank aggregation and other ranking and clustering problems. Edited by C. Kaklamakis and M. Skutella,Approximation and on line Algorithms. In Vol. 4927 of Lect. Notes Comput. Sci. Springer Berlin (2008) 260–273. | DOI | MR | Zbl

[32] J. Yuan and S. Zhou, Optimal labelling of unit interval graphs. Appl. Math. 10 (1995) 337–344. | DOI | MR | Zbl

Cité par Sources :