Article collection "Mathematical Problems of Cybernetics" №4, Moscow, 1992
Monotone transformations in discrete optimization and coding cost minimization problems for a class of self-synchronizing codes
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.