Proposed by Peter van Beek
These problems are said to have many practical applications including sensor placements for x-ray crystallography and radio astronomy. A Golomb ruler may be defined as a set of m integers 0=a1<a2<…<am such that the m(m−1)/2 differences aj−ai,1<=i<j<=m are distinct. Such a ruler is said to contain m marks and is of length am. The objective is to find optimal (minimum length) or near optimal rulers. Note that a symmetry can be removed by adding the constraint that a2−a1<am−am−1, the first difference is less than the last.
There exist several interesting generalizations of the problem which have received attention like modular Golomb rulers (differences are all distinct mod a given base), disjoint Golomb rulers, Golomb rectangles (the 2-dimensional generalization of Golomb rulers), and difference triangle sets (sets of rulers with no common difference).