A new binary (17,4,5) constant weight code

Cryptography and Communications - Tập 15 - Trang 443-453 - 2022
Moshe Milshtein1
1Sarasota, United States

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