DocumentCode
1317061
Title
On greedy algorithms in coding theory
Author
Cohen, Gérard D. ; Litsyn, Simon ; Zémor, Gilles
Author_Institution
ENST, Paris, France
Volume
42
Issue
6
fYear
1996
fDate
11/1/1996 12:00:00 AM
Firstpage
2053
Lastpage
2057
Abstract
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
Keywords
computational complexity; graph theory; matrix algebra; source coding; coding theory; complexity reduction; conflict resolution; covering codes; derandomization; distortion; greedy algorithms; hypergraphs; incidence matrices; separating systems; source encoding; Automata; Cryptography; Decoding; Greedy algorithms; Information theory; Linear code; Quantization; Rate distortion theory; Testing; Upper bound;
fLanguage
English
Journal_Title
Information Theory, IEEE Transactions on
Publisher
ieee
ISSN
0018-9448
Type
jour
DOI
10.1109/18.556707
Filename
556707
Link To Document