Issue |
RAIRO-Oper. Res.
Volume 55, Number 4, July-August 2021
|
|
---|---|---|
Page(s) | 2241 - 2246 | |
DOI | https://doi.org/10.1051/ro/2021103 | |
Published online | 29 July 2021 |
A conjecture on a continuous optimization model for the Golomb Ruler Problem
1
Michigan State University, Natural Science Building, 288 Farm Lane, East Lansing, MI, USA
2
University of Campinas (IMECC – Unicamp), Cidade Universitaria Zeferino Vaz, Campinas, Brazil
3
Federal University of Sao Paulo, Science and Technology Institute, Sao Jose dos Campos, Brazil
* Corresponding author: luiz.leduino@unifesp.br
Received:
31
March
2021
Accepted:
11
July
2021
A Golomb Ruler (GR) is a set of integer marks along an imaginary ruler such that all the distances of the marks are different. Computing a GR of minimum length is associated to many applications (from astronomy to information theory). Although not yet demonstrated to be NP-hard, the problem is computationally very challenging. This brief note proposes a new continuous optimization model for the problem and, based on a given theoretical result and some computational experiments, we conjecture that an optimal solution of this model is also a solution to an associated GR of minimum length.
Mathematics Subject Classification: 90C26 / 90C27
Key words: Nonlinear programming / Golomb Ruler Problem / continuous models
© The authors. Published by EDP Sciences, ROADEF, SMAI 2021
This is an Open Access article distributed under the terms of the Creative Commons Attribution License (https://creativecommons.org/licenses/by/4.0), which permits unrestricted use, distribution, and reproduction in any medium, provided the original work is properly cited.
Current usage metrics show cumulative count of Article Views (full-text article views including HTML views, PDF and ePub downloads, according to the available data) and Abstracts Views on Vision4Press platform.
Data correspond to usage on the plateform after 2015. The current usage metrics is available 48-96 hours after online publication and is updated daily on week days.
Initial download of the metrics may take a while.