The article considers a problem of discrete optimization. Huffman's method is used for solving many problems of this kind, yet its application requires the construction of a minorant, which is a computationally intensive task. We suggest a method for solving a discrete optimization problem in the class of binary self-synchronizing codes, based only on an extension of the optimization domain that does not require the construction of a minorant. The suggested algorithm is a combination of the monotone search algorithm (which takes in account majorization) and the procedure of consecutive elimination. It has polynomial complexity which is asymptotically equivalent to the complexity of some Huffman algorithm implementations.

discrete optimization, self-synchronizing codes, Huffman method, monotone transformations

Mathematical problems and theory of numerical methods