KIAM Main page Web Library  •  Publication Searh  Русский 

Article collection "Mathematical Problems of Cybernetics" №4, Moscow, 1992
Authors: Vorob'eva E.G.
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.
discrete optimization, self-synchronizing codes, Huffman method, monotone transformations
Publication language: russian,  pages: 21 (p. 73-93)
Research direction:
Mathematical problems and theory of numerical methods
Russian source text:
List of publications citation:
Export link to publication in format:   RIS    BibTeX
About authors:
  • Vorob'eva Elena Germanovna