LP Pseudocodewords of Cycle Codes are Half-Integral
From MaRDI portal
Publication:6237978
Abstract: In his Ph.D. disseration, Feldman and his collaborators define the linear programming decoder for binary linear codes, which is a linear programming relaxation of the maximum-likelihood decoding problem. This decoder does not, in general, attain maximum-likelihood performance; however, the source of this discrepancy is known to be the presence of non-integral extreme points (vertices) within the fundamental polytope, vectors which are also called nontrivial linear programming pseudocodewords. Restricting to the class of cycle codes, we provide necessary conditions for a vector to be a linear programming pseudocodeword. In particular, the components of any such pseudocodeword can only assume values of zero, one-half, or one.
This page was built for publication: LP Pseudocodewords of Cycle Codes are Half-Integral
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6237978)
