On the Design of Optimum Order 2 Golomb Ruler

Brigitte Jaumard, CRC Chair on the Optimization of Communication Networks, Université de Montréal, Department of Computer Science and Operations Research

Yannick Solari, Ecole Polytechnique de Montréal, Department of Electrical Engineering

Philippe Galinier, Ecole Polytechnique de Montréal, Department of Computer Engineering

A Golomb ruler with M marks can be defined as a set { a_i } of integers so that all differences d_ij = a_j - a_i, i ¹j are distinct. An order 2 Golomb ruler is a Golomb ruler such that all differences d_ijkl  = |d_kl - d_ij  | , i, j ¹ k, l are distinct as much as possible. Contruction of optimum order 2 Golomb ruler, i.e., of rulers of minimum length, is a highly combinatorial problem which has applications, e.g.,
in the design of convolutional self doubly orthogonal codes (CSO²C). We propose here a first exact algorithm, different from a pure exhaustive search, for building optimum order 2 Golomb rulers and provide optimal rulers for up to 9 marks and new rulers which improve on the previous ones for up to 20 marks.

[pdf]

Equivalence of some LP-based Lower Bounds for the Golomb Ruler Problem

Christophe Meyer, Université de Montréal, Department of Computer Science and Operations Research

Brigitte Jaumard, CRC Chair on the Optimization of Communication Networks, Université de Montréal, Department of Computer Science and Operations Research

The Golomb Ruler problem consists in finding n integers such that all possible differences are distinct and such that the largest difference is minimum.
We review three lower bounds based on linear programming that have been proposed in the literature for this problem, and propose a new one.
We then show that these 4 lower bounds are equal. Finally we discuss some computational experience aiming at identifying the easiest lower bound to compute in practice.

[pdf]