{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,23]],"date-time":"2025-10-23T11:16:36Z","timestamp":1761218196757,"version":"build-2065373602"},"reference-count":31,"publisher":"MDPI AG","issue":"12","license":[{"start":{"date-parts":[[2019,12,6]],"date-time":"2019-12-06T00:00:00Z","timestamp":1575590400000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0\/"}],"funder":[{"DOI":"10.13039\/501100003725","name":"National Research Foundation of Korea","doi-asserted-by":"publisher","award":["NRF-2017R1C1B5018298"],"award-info":[{"award-number":["NRF-2017R1C1B5018298"]}],"id":[{"id":"10.13039\/501100003725","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Entropy"],"abstract":"<jats:p>The size of the largest binary single deletion code has been unknown for more than 50 years. It is known that Varshamov\u2013Tenengolts (VT) code is an optimum single deletion code for block length     n \u2264 10    ; however, only a few upper bounds of the size of single deletion code are proposed for larger n. We provide improved upper bounds using Mixed Integer Linear Programming (MILP) relaxation technique. Especially, we show the size of single deletion code is smaller than or equal to 173 when the block length n is 11. In the second half of the paper, we propose a conjecture that is equivalent to the long-lasting conjecture that \u201cVT code is optimum for all n\u201d. This equivalent formulation of the conjecture contains small sub-problems that can be numerically verified. We provide numerical results that support the conjecture.<\/jats:p>","DOI":"10.3390\/e21121202","type":"journal-article","created":{"date-parts":[[2019,12,6]],"date-time":"2019-12-06T10:41:44Z","timestamp":1575628904000},"page":"1202","update-policy":"https:\/\/doi.org\/10.3390\/mdpi_crossmark_policy","source":"Crossref","is-referenced-by-count":3,"title":["Nonasymptotic Upper Bounds on Binary Single Deletion Codes via Mixed Integer Linear Programming"],"prefix":"10.3390","volume":"21","author":[{"ORCID":"https:\/\/orcid.org\/0000-0002-6346-4182","authenticated-orcid":false,"given":"Albert","family":"No","sequence":"first","affiliation":[{"name":"Department of Electronic and Electrical Engineering, Hongik University, Seoul 04066, Korea"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"1968","published-online":{"date-parts":[[2019,12,6]]},"reference":[{"key":"ref_1","doi-asserted-by":"crossref","first-page":"6192","DOI":"10.1109\/TIT.2013.2262020","article-title":"Optimal coding for the binary deletion channel with small deletion probability","volume":"59","author":"Kanoria","year":"2013","journal-title":"IEEE Trans. Inf. Theory"},{"key":"ref_2","first-page":"273","article-title":"On single-deletion-correcting codes","volume":"10","author":"Sloane","year":"2000","journal-title":"Codes Des."},{"key":"ref_3","first-page":"288","article-title":"Codes which correct single asymmetric errors","volume":"161","author":"Varshamov","year":"1965","journal-title":"Autom. I Telemkhanika"},{"key":"ref_4","doi-asserted-by":"crossref","first-page":"766","DOI":"10.1109\/TIT.1984.1056962","article-title":"Nonbinary codes, correcting single deletion or insertion (Corresp.)","volume":"30","author":"Tenengolts","year":"1984","journal-title":"IEEE Trans. Inf. Theory"},{"key":"ref_5","doi-asserted-by":"crossref","first-page":"965","DOI":"10.1109\/TIT.2018.2876281","article-title":"Codes correcting two deletions","volume":"65","author":"Gabrys","year":"2018","journal-title":"IEEE Trans. Inf. Theory"},{"key":"ref_6","doi-asserted-by":"crossref","unstructured":"Sima, J., and Bruck, J. (2019, January 7\u201312). Optimal k-Deletion Correcting Codes. Proceedings of the 2019 IEEE International Symposium on Information Theory (ISIT), Paris, France.","DOI":"10.1109\/ISIT.2019.8849750"},{"key":"ref_7","first-page":"707","article-title":"Binary codes capable of correcting deletions, insertions, and reversals","volume":"10","author":"Levenshtein","year":"1966","journal-title":"Sov. Phys. Dokl."},{"key":"ref_8","unstructured":"Levenshtein, V.I. (July, January 30). Bounds for deletion\/insertion correcting codes. Proceedings of the IEEE International Symposium on Information Theory, Lausanne, Switzerland."},{"key":"ref_9","doi-asserted-by":"crossref","first-page":"5115","DOI":"10.1109\/TIT.2013.2257917","article-title":"Nonasymptotic upper bounds for deletion correcting codes","volume":"59","author":"Kulkarni","year":"2013","journal-title":"IEEE Trans. Inf. Theory"},{"key":"ref_10","doi-asserted-by":"crossref","first-page":"3862","DOI":"10.1109\/TIT.2014.2317698","article-title":"An improvement to Levenshtein\u2019s upper bound on the cardinality of deletion correcting codes","volume":"60","author":"Cullina","year":"2014","journal-title":"IEEE Trans. Inf. Theory"},{"key":"ref_11","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1109\/TIT.1979.1055985","article-title":"On the Shannon capacity of a graph","volume":"25","year":"1979","journal-title":"IEEE Trans. Inf. Theory"},{"key":"ref_12","doi-asserted-by":"crossref","unstructured":"Butenko, S., Pardalos, P., Sergienko, I., Shylo, V., and Stetsyuk, P. (2009). Estimating the size of correcting codes using extremal graph problems. Optimization, Springer.","DOI":"10.1007\/978-0-387-98096-6_12"},{"key":"ref_13","doi-asserted-by":"crossref","first-page":"79","DOI":"10.1016\/j.disc.2013.11.003","article-title":"On the Varshamov\u2013Tenengolts construction on binary strings","volume":"317","author":"Kulkarni","year":"2014","journal-title":"Discret. Math."},{"key":"ref_14","unstructured":"Sloane, N.J.A. (2019, October 03). Challenge Problems: Independent Sets in Graphs. Available online: https:\/\/oeis.org\/A265032\/a265032.html."},{"key":"ref_15","first-page":"8","article-title":"Binary codes capable of correcting spurious insertions and deletion of ones","volume":"1","author":"Levenshtein","year":"1965","journal-title":"Probl. Inf. Transm."},{"key":"ref_16","doi-asserted-by":"crossref","first-page":"241","DOI":"10.1515\/dma.1992.2.3.241","article-title":"On perfect codes in deletion and insertion metric","volume":"2","author":"Levenshtein","year":"1992","journal-title":"Discret. Math. Appl."},{"key":"ref_17","first-page":"249","article-title":"A number-theoretic function with an application in the theory of coding","volume":"19","author":"Ginzburg","year":"1967","journal-title":"Probl. Kibern."},{"key":"ref_18","doi-asserted-by":"crossref","first-page":"211","DOI":"10.1016\/j.tcs.2015.09.023","article-title":"Branch-and-reduce exponential\/fpt algorithms in practice: A case study of vertex cover","volume":"609","author":"Akiba","year":"2016","journal-title":"Theor. Comput. Sci."},{"key":"ref_19","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1145\/3355502","article-title":"Scalable kernelization for maximum independent sets","volume":"24","author":"Hespe","year":"2019","journal-title":"J. Exp. Algorithmics (JEA)"},{"key":"ref_20","doi-asserted-by":"crossref","first-page":"571","DOI":"10.1016\/j.cor.2010.07.019","article-title":"An exact bit-parallel algorithm for the maximum clique problem","volume":"38","year":"2011","journal-title":"Comput. Oper. Res."},{"key":"ref_21","unstructured":"Mitchell, S., OSullivan, M., and Dunning, I. (2011). PuLP: A Linear Programming Toolkit for Python, The University of Auckland."},{"key":"ref_22","unstructured":"Forrest, J., Ralphs, T., Vigerske, S., Kristjansson, B., Lubin, M., Santos, H., and Saltzman, M. (2019, October 03). coin-or\/Cbc: Version 2.9.9. Available online: https:\/\/dx.doi.org\/10.5281\/zenodo.1317566."},{"key":"ref_23","unstructured":"Bliek1\u00fa, C., Bonami, P., and Lodi, A. (2014, January 16\u201317). Solving mixed-integer quadratic programming problems with IBM-CPLEX: a progress report. Proceedings of the Twenty-Sixth RAMP Symposium, Tokyo, Japan."},{"key":"ref_24","doi-asserted-by":"crossref","unstructured":"Absi, N., and van den Heuvel, W. (2019). Worst case analysis of Relax and Fix heuristics for lot-sizing problems. Eur. J. Oper. Res.","DOI":"10.1016\/j.ejor.2019.06.010"},{"key":"ref_25","doi-asserted-by":"crossref","first-page":"247","DOI":"10.1016\/j.ijpe.2009.08.022","article-title":"A fix-and-optimize approach for the multi-level capacitated lot sizing problem","volume":"123","author":"Helber","year":"2010","journal-title":"Int. J. Prod. Econ."},{"key":"ref_26","doi-asserted-by":"crossref","first-page":"1074","DOI":"10.1016\/j.asoc.2017.07.018","article-title":"Integrating LP-guided variable fixing with MIP heuristics in the robust design of hybrid wired-wireless FTTx access networks","volume":"61","author":"Mett","year":"2017","journal-title":"Appl. Soft Comput."},{"key":"ref_27","doi-asserted-by":"crossref","first-page":"62","DOI":"10.1016\/j.ejor.2008.01.044","article-title":"New convergent heuristics for 0\u20131 mixed integer programming","volume":"195","author":"Wilbaut","year":"2009","journal-title":"Eur. J. Oper. Res."},{"key":"ref_28","doi-asserted-by":"crossref","first-page":"125","DOI":"10.1007\/s10479-009-0546-z","article-title":"Improved convergent heuristics for the 0-1 multidimensional knapsack problem","volume":"183","author":"Hanafi","year":"2011","journal-title":"Ann. Oper. Res."},{"key":"ref_29","doi-asserted-by":"crossref","first-page":"4135","DOI":"10.1016\/j.asoc.2011.02.032","article-title":"Hybrid metaheuristics in combinatorial optimization: A survey","volume":"11","author":"Blum","year":"2011","journal-title":"Appl. Soft Comput."},{"key":"ref_30","doi-asserted-by":"crossref","first-page":"201","DOI":"10.1137\/1025045","article-title":"Time Warps, String Edits, and Macromolecules: The Theory and Practice of Sequence Comparison","volume":"25","author":"Sankoff","year":"1983","journal-title":"SIAM Rev."},{"key":"ref_31","doi-asserted-by":"crossref","first-page":"594","DOI":"10.1080\/10556788.2017.1322081","article-title":"A framework for solving mixed-integer semidefinite programs","volume":"33","author":"Gally","year":"2018","journal-title":"Optim. Methods Softw."}],"container-title":["Entropy"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.mdpi.com\/1099-4300\/21\/12\/1202\/pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,10,11]],"date-time":"2025-10-11T13:41:00Z","timestamp":1760190060000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.mdpi.com\/1099-4300\/21\/12\/1202"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2019,12,6]]},"references-count":31,"journal-issue":{"issue":"12","published-online":{"date-parts":[[2019,12]]}},"alternative-id":["e21121202"],"URL":"https:\/\/doi.org\/10.3390\/e21121202","relation":{},"ISSN":["1099-4300"],"issn-type":[{"type":"electronic","value":"1099-4300"}],"subject":[],"published":{"date-parts":[[2019,12,6]]}}}