
related topics 
{style, bgcolor, rowspan} 
{math, number, function} 
{war, force, army} 
{math, energy, light} 
{language, word, form} 

In mathematics, a Golomb ruler is a set of marks at integer positions along an imaginary ruler such that no two pairs of marks are the same distance apart. The number of marks on the ruler is its order, and the largest distance between two of its marks is its length. Translation and reflection of a Golomb ruler are considered trivial, so the smallest mark is customarily put at 0 and the next mark at the smaller of its two possible values.
The Golomb ruler was named for Solomon W. Golomb and discovered independently by Sidon^{[1]} and Babcock.^{[2]}
There is no requirement that a Golomb ruler be able to measure all distances up to its length, but if it does, it is called a perfect Golomb ruler. It has been proven that no perfect Golomb ruler exists for five or more marks.^{[3]} A Golomb ruler is optimal if no shorter Golomb ruler of the same order exists. Creating Golomb rulers is easy, but finding the optimal Golomb rulers for a specified order is computationally very challenging. Distributed.net has completed distributed massively parallel searches for optimal order24,^{[4]} order25^{[5]} and order26^{[6]}^{[7]} Golomb rulers, confirming the suspected candidates.^{[8]}^{[9]} Distributed.net also has plans to find optimal Golomb rulers (OGRs) of order27 and order28. However, they are not expected to take as long as the previous projects due to the discovery of an improved algorithm.^{[10]} Distributed.net is actively searching for the optimal order27 ruler; the expected time to discover it is about seven years.^{[11]}
One practical use of Golomb rulers is in the design of phased array radio antennas such as radio telescopes. Antennas in a [0,1,4,6] Golomb ruler configuration can often be seen at cell sites.^{[dubious – discuss]}
Currently, the complexity of finding OGRs of arbitrary order n (where n is given in unary) is unknown. In the past there was some speculation that it is an NPhard problem.^{[3]} Problems related to the construction of Golomb Rulers are provably shown to be NPhard, where it is also noted that no known NPcomplete problem has similar flavor to finding Golomb Rulers.^{[12]}
Contents
Full article ▸


related documents 
1977 
1974 
1987 
List of nearest stars 
KuyavianPomeranian Voivodeship 
1992 
Wikipedia:Boilerplate text 
List of Roman Emperors 
London Borough of Bexley 
1964 
1985 
1988 
Greater Poland Voivodeship 
Premiers of Tasmania 
Goodland, Kansas 
United States congressional delegations from Arizona 
ViceChancellor of Germany 
Premiers of Victoria 
1944 
1986 
1984 
List of Presidents of Mexico 
Windhoek 
1966 
Plymouth Argyle F.C. season 2001–02 
CaraşSeverin County 
Cirth 
1917 
Winnemucca, Nevada 
Norfolk, Nebraska 
