Retour

G-2003-81

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

et

référence BibTeX

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
et
Discrete Applied Mathematics, 154(1), 120–144, 2006 référence BibTeX