Reduction and Efficient Solution of ILP Models of Mixed Hamming Packings Yielding Improved Upper Bounds

Péter Naszvadi (), Peter Adam and Mátyás Koniorczyk
Additional contact information
Péter Naszvadi: Faculty of Informatics, Eötvös Loránd University, 1117 Budapest, Hungary
Peter Adam: HUN-REN Wigner Research Centre for Physics, 1121 Budapest, Hungary
Mátyás Koniorczyk: HUN-REN Wigner Research Centre for Physics, 1121 Budapest, Hungary

Mathematics, 2025, vol. 13, issue 16, 1-20

Abstract: We consider mixed Hamming packings, addressing the maximal cardinality of codes with a minimum codeword Hamming distance. We do not rely on any algebraic structure of the alphabets. We extend known-integer linear programming models of the problem to be efficiently tractable using standard ILP solvers. This is achieved by adopting the concept of contact graphs from classical continuous sphere packing problems to the present discrete context, resulting in a reduction technique for the models which enables their efficient solution as well as their decomposition to smaller subproblems. Based on our calculations, we provide a systematic summary of all lower and upper bounds for packings in the smallest Hamming spaces. The known results are reproduced, with some bounds found to be sharp, and the upper bounds improved in some cases.

Keywords: coding theory; minimum-distance codes; mixed Hamming packings; discrete sphere packing; ILP decomposition (search for similar items in EconPapers)
JEL-codes: C (search for similar items in EconPapers)
Date: 2025
References: Add references at CitEc
Citations:

Downloads: (external link)
https://www.mdpi.com/2227-7390/13/16/2633/pdf (application/pdf)
https://www.mdpi.com/2227-7390/13/16/2633/ (text/html)

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:gam:jmathe:v:13:y:2025:i:16:p:2633-:d:1726028

Access Statistics for this article

Mathematics is currently edited by Ms. Emma He

More articles in Mathematics from MDPI
Bibliographic data for series maintained by MDPI Indexing Manager ().