A new binary (17,4,5) constant weight code
Tóm tắt
We describe a binary (17,4,5) constant weight code with 444 codewords, thus improving the lower bound for A(17,4,5) from 441 to 444. The code was discovered by a computer search implementing a new stochastic local search algorithm for the maximum independent set problem. The algorithm suggested is based on Generic Scuba Search, which is a known hybrid local search method exploiting neutrality in search landscapes.
Tài liệu tham khảo
Brouwer, A.E.: Bounds for binary constant weight codes. website at https://www.win.tue.nl/~aeb/codes/Andw.html. Accessed 24 Nov 2020
Tonchev, V.D.: Maximum disjoint bases and constant-weight codes. IEEE Trans. Inf. Theory 44(1), 333–334 (1998). https://doi.org/10.1109/18.651061
Ostergard, P.R.J.: Classification of binary constant weight codes. IEEE Trans. Inf. Theory 56(8), 3779–3785 (2010). https://doi.org/10.1109/TIT.2010.2050922
Hoos, H.H., Stützle, T.: Stochastic Local Search: Foundations and Applications. Elsevier, New York (2004)
Verel, S., Collard, P., Clergue, M.: Scuba search: when selection meets innovation. In: Proceedings of the 2004 Congress on Evolutionary Computation (IEEE Cat. No.04TH8753), vol. 1. pp. 924–931 (2004)
Marmion, M.E., Dhaenens, C., Jourdan, L., Liefooghe, A., Verel, S.: NILS: A neutrality-based iterated local search and its application to flowshop scheduling. In: Merz, P., Hao, J.K. (eds.) Evolutionary Computation in Combinatorial Optimization, pp. 191–202. Springer, Berlin (2011)
Marmion, M.E., Blot, A., Jourdan, L., Dhaenens, C.: Neutrality in the graph coloring problem. In: Nicosia, G., Pardalos, P. (eds.) Learning and Intelligent Optimization, pp. 125–130. Springer, Berlin (2013)
Barnett, L.: Netcrawling-optimal evolutionary search with neutral networks. In: Proceedings of the 2001 Congress on Evolutionary Computation (IEEE Cat. No.01TH8546). vol. 1, pp. 30–37. (2001)
Marmion, M.E., Dhaenens, C., Jourdan, L., Liefooghe, A., Verel, S.: The Road to VEGAS: Guiding the search over neutral networks. In: Proceedings of the 13th Annual Conference on Genetic and Evolutionary Computation. GECCO ’11. New York, NY, USA: Association for Computing Machinery, pp. 1979–1986. Available from: https://doi.org/10.1145/2001576.2001842 (2011)
Wu, Q., Hao, J.K.: A review on algorithms for maximum clique problems. Eur. J. Oper. Res. 242(3), 693–709 (2015). https://doi.org/10.1016/j.ejor.2014.09.064
Karp, R.M.: In: Miller, R.E., Thatcher, J.W., Bohlinger, J.D. (eds.) Reducibility among Combinatorial Problems. Boston, MA: Springer US. pp. 85–103. Available from: https://doi.org/10.1007/978-1-4684-2001-2_9 (1972)
Friden, C., Hertz, A., de Werra, D.: Stabulus: a technique for finding stable sets in large graphs with tabu search. Computing 42(1), 35–44 (1989)
Vitter, J.S.: Random sampling with a reservoir. ACM Trans. Math. Softw. 11(1), 37–57 (1985). https://doi.org/10.1145/3147.3165