On greedy algorithms in coding theory
Gérard Cohen, Simon N. Litsyn, Gilles Zémor · IEEE Transactions on Information Theory · 1996
We study a wide class of problems in coding theory for which we consider two different formulations: in terms of incidence matrices and in terms of hypergraphs. These problems are dealt with using a greedy algorithm due to Stein (1974) and Lovasz (1975). Some examples, including constructing covering codes, codes for conflict resolution, separating systems, source encoding with distortion, etc., are given a unified treatment. Under certain conditions derandomization can be performed, leading to an essential reduction in the complexity of the constructions.