DocumentCode
1254373
Title
Greedy and heuristic algorithms for codes and colorings
Author
Etzion, Tuvi ; Ostergard, Patric R J
Author_Institution
Dept. of Comput. Sci., Technion-Israel Inst. of Technol., Haifa, Israel
Volume
44
Issue
1
fYear
1998
fDate
1/1/1998 12:00:00 AM
Firstpage
382
Lastpage
388
Abstract
Many of the fundamental coding problems can be represented as graph problems. These problems are often intrinsically difficult and unsolved even if the code length is relatively small. With the motivation to improve lower bounds on the sizes of constant weight codes and asymmetric codes, we suggest a few greedy algorithms and other heuristic methods, which result in new, record-breaking codes. Some of the heuristics used are based on tabu search and evolutionary algorithms. Tables of new codes are presented
Keywords
codes; graph theory; search problems; asymmetric codes; code length; code size; colorings; constant weight codes; evolutionary algorithms; graph problems; greedy algorithms; heuristic algorithms; heuristic methods; lower bounds; minimum Hamming distance; minimum asymmetric distance; tabu search; Approximation methods; Computer science; Evolutionary computation; Extraterrestrial measurements; Graph theory; Greedy algorithms; Heuristic algorithms; Space technology; Testing; Very large scale integration;
fLanguage
English
Journal_Title
Information Theory, IEEE Transactions on
Publisher
ieee
ISSN
0018-9448
Type
jour
DOI
10.1109/18.651069
Filename
651069
Link To Document