Back

# Equivalence of Some LP-Based Lower Bounds for the Golomb Ruler Problem

## Christophe Meyer and Brigitte Jaumard

BibTeX reference

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.

, 30 pages

### Publication

Equivalence of some LP-based lower bounds for the Golomb ruler problem
and
Discrete Applied Mathematics, 154(1), 120–144, 2006 BibTeX reference