Basic variable neighborhood search for the minimum sitting arrangement problem
Tóm tắt
The minimum sitting arrangement (MinSA) problem is a linear layout problem consisting in minimizing the number of errors produced when a signed graph is embedded into a line. This problem has been previously tackled by theoretical and heuristic approaches in the literature. In this paper we present a basic variable neighborhood search (BVNS) algorithm for solving the problem. First, we introduce a novel constructive scheme based on the identification of cliques from the input graph, when only the positive edges are considered. The solutions obtained by the constructive procedure are then used as a starting point for the proposed BVNS algorithm. Efficient implementations of the several configurations of the local search procedure within the BVNS are described. The algorithmic proposal is then compared with previous approaches in the state of the art for the MinSA over different sets of referred instances. The obtained results supported by non-parametric statistical tests, indicate that BVNS can be considered as the new state-of-the-art algorithm for the MinSA.
Tài liệu tham khảo
Benítez, F., Aracena, J., Thraves, C.: The sitting closer to friends than enemies problem in the circumference. Technical report (2018). arXiv:1811.02699
Bron, C., Kerbosch, J.: Algorithm 457: finding all cliques of an undirected graph. Commun. ACM 16(9), 575–577 (1973). ISSN 0001-0782
Burkard, R.E., Çela, E., Pardalos, P.M., Pitsoulis, L.S.: The quadratic assignment problem. In: Du, D.-Z., Pardalos, P.M. (eds.) Handbook of Combinatorial Optimization. Springer, Boston, MA (1998)
Cygan, M., Pilipczuk, M., Pilipczuk, M., Wojtaszczyk, J.O.: Sitting closer to friends than enemies, revisited. In: Proceedings of the 37th International Conference on Mathematical Foundations of Computer Science, MFCS’12, pp. 296–307, Berlin, Heidelberg (2012). Springer-Verlag. ISBN 978-3-642-32588-5
Cygan, M., Pilipczuk, M., Pilipczuk, M., Wojtaszczyk, J.O.: Sitting closer to friends than enemies, revisited. Theory Comput. Syst. 56(2), 394–405 (2015)
Duarte, A., Pantrigo, J.J., Pardo, E.G., Mladenović, N.: Multi-objective variable neighborhood search: an application to combinatorial optimization problems. J. Glob. Optim. 63(3), 515–536 (2015)
Duarte, A., Pantrigo, J.J., Pardo, E.G., Sánchez-Oro, J.: Parallel variable neighbourhood search strategies for the cutwidth minimization problem. IMA J. Manag. Math. 27(1), 55–73 (2016)
Feo, T.A., Resende, M.G.C.: Greedy randomized adaptive search procedures. J. Glob. Optim. 6(2), 109–133 (1995)
Hansen, N., Mladenović, P., Todosijević, R., Hanafi, S.: Variable neighborhood search: basics and variants. EURO J. Comput. Optim. 5(3), 423–454 (2017). ISSN 2192-4414
Hansen, P., Mladenović, N.: Variable Neighborhood Search, pp. 313–337. Springer US, Boston (2014). ISBN 978-1-4614-6940-7
Harary, F.: Graph Theory. In: Addison-Wesley Series in Mathematics. Addison Wesley, Reading (1969)
Karp, R.M.: Reducibility Among Combinatorial Problems, pp. 85–103. Springer US, Boston (1972). ISBN 978-1-4684-2001-2
Kermarrec, A.-M., Thraves, C.: Can Everybody Sit Closer to Their Friends Than Their Enemies? pp. 388–399. Springer, Berlin (2011). ISBN 978-3-642-22993-0
Kermarrec, A.-M., Thraves, C.: Signed graph embedding: when everybody can sit closer to friends than enemies. CoRR (2014). arXiv:1405.5023
Laguna, M., Martí, R., Campos, V.: Intensification and diversification with elite tabu search solutions for the linear ordering problem. Comput. Oper. Res. 26(12), 1217–1230 (1999). ISSN 0305-0548
Leskovec, J., Huttenlocher, D., Kleinberg, J.: Signed networks in social media. In: Proceedings of the SIGCHI Conference on Human Factors in Computing Systems, CHI ’10, pp. 1361–1370, New York, NY (2010a). ACM. ISBN 978-1-60558-929-9
Leskovec, J., Huttenlocher, D., Kleinberg, J.: Predicting positive and negative links in online social networks. In: Proceedings of the 19th International Conference on World Wide Web, WWW’10, pp. 641–650, New York, NY (2010b). ACM. ISBN 978-1-60558-799-8
Lozano, M., Duarte, A., Gortázar, F., Martí, R.: Variable neighborhood search with ejection chains for the antibandwidth problem. J. Heuristics 18(6), 919–938 (2012)
Mladenović, N., Hansen, P.: Variable neighborhood search. Comput. Oper. Res. 24(11), 1097–1100 (1997)
Pantrigo, J.J., Martí, R., Duarte, A., Pardo, E.G.: Scatter search for the cutwidth minimization problem. Ann. Oper. Res. 199(1), 285–304 (2012)
Pardalos, P.M., Rendl, F., Wolkowicz, H.: The quadratic assignment problem: a survey and recent developments. In: Proceedings of the DIMACS Workshop on Quadratic Assignment Problems, volume 16 of DIMACS Series in Discrete Mathematics and Theoretical Computer Science, pp. 1–42. American Mathematical Society (1994)
Pardo, E.G., Soto, M., Thraves, C.: Embedding signed graphs in the line. J. Combin. Optim. 29(2), 451–471 (2015). ISSN 1573-2886
Pardo, E.G., Martí, R., Duarte, A.: Linear layout problems. In: Martí, R., Panos, P., Resende, M. (eds.) Handbook of Heuristics. Springer, Cham (2016)
Pardo, E.G., Mladenović, N., Pantrigo, J.J., Duarte, A.: Variable formulation search for the cutwidth minimization problem. Appl. Soft Comput. 13(5), 2242–2252 (2013)
Safro, I., Ron, D., Brandt, A.: Graph minimum linear arrangement by multilevel weighted edge contractions. J. Algorithms 60(1), 24–41 (2006). ISSN 0196-6774
Sánchez-Oro, J., Pantrigo, J.J., Duarte, A.: Combining intensification and diversification strategies in VNS. An application to the vertex separation problem. Comput. Oper. Res. 52(Part B(0)), 209–219 (2014)
Szell, M., Lambiotte, R., Thurner, S.: Multirelational organization of large-scale social networks in an online world. Proc. Natl. Acad. Sci. 107(31), 13636–13641 (2010)