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.
Accepté le :
Première publication :
Publié le :
DOI : 10.1051/ro/2021103
Keywords: Nonlinear programming, Golomb Ruler Problem, continuous models
@article{RO_2021__55_4_2241_0,
author = {Duxbury, Phil and Lavor, Carlile and de Salles-Neto, Luiz Leduino},
title = {A conjecture on a continuous optimization model for the {Golomb} {Ruler} {Problem}},
journal = {RAIRO. Operations Research},
pages = {2241--2246},
year = {2021},
publisher = {EDP-Sciences},
volume = {55},
number = {4},
doi = {10.1051/ro/2021103},
mrnumber = {4292305},
zbl = {1479.90167},
language = {en},
url = {https://www.numdam.org/articles/10.1051/ro/2021103/}
}
TY - JOUR AU - Duxbury, Phil AU - Lavor, Carlile AU - de Salles-Neto, Luiz Leduino TI - A conjecture on a continuous optimization model for the Golomb Ruler Problem JO - RAIRO. Operations Research PY - 2021 SP - 2241 EP - 2246 VL - 55 IS - 4 PB - EDP-Sciences UR - https://www.numdam.org/articles/10.1051/ro/2021103/ DO - 10.1051/ro/2021103 LA - en ID - RO_2021__55_4_2241_0 ER -
%0 Journal Article %A Duxbury, Phil %A Lavor, Carlile %A de Salles-Neto, Luiz Leduino %T A conjecture on a continuous optimization model for the Golomb Ruler Problem %J RAIRO. Operations Research %D 2021 %P 2241-2246 %V 55 %N 4 %I EDP-Sciences %U https://www.numdam.org/articles/10.1051/ro/2021103/ %R 10.1051/ro/2021103 %G en %F RO_2021__55_4_2241_0
Duxbury, Phil; Lavor, Carlile; de Salles-Neto, Luiz Leduino. A conjecture on a continuous optimization model for the Golomb Ruler Problem. RAIRO. Operations Research, Tome 55 (2021) no. 4, pp. 2241-2246. doi: 10.1051/ro/2021103
[1] , Intermodulation interference in radio systems. Bell Labs Tech. J. 32 (1953) 63–73. | DOI
[2] , , , and , Recent results on assigned and unassigned distance geometry with applications to protein molecules and nanostructures. Ann. Oper. Res. 271 (2018) 161–203. | MR | Zbl | DOI
[3] and , Applications of numbered undirected graphs. Proc. IEEE 65 (1977) 562–570. | DOI
[4] , and , Some new possibilities of optimum synthetic linear arrays for radioastronomy. Astron. Astrophys. 41 (1975) 409–411.
[5] , and , A new algorithm for Golomb ruler derivation and proof of the 19 mark ruler. IEEE Trans. Inf. Theory 44 (1998) 379–382. | MR | Zbl | DOI
[6] , A review of the available construction methods for Golomb rulers. Adv. Math. Commun. 3 (2009) 235–250. | MR | Zbl | DOI
[7] and , On a problem of Sidon in additive number theory and on some related problems. J. London Math. Soc. 16 (1941) 212–215. | MR | Zbl | DOI
[8] and , A computational comparison of optimization methods for the Golomb Ruler Problem. Lecture Notes Comput. Sci. 11494 (2019) 409–425. | Zbl | DOI
[9] , , and , An Introduction to Distance Geometry Applied to Molecular Geometry. Springer Briefs, Springer, New York (2017). | MR | DOI
[10] and , Six mathematical gems from the history of distance geometry. Int. Trans. Oper. Res. 23 (2016) 897–920. | MR | Zbl | DOI
[11] and , Euclidean Distance Geometry: An Introduction. Springer, New York (2017). | MR | DOI
[12] , , and , Euclidean distance geometry and applications. SIAM Rev. 56 (2014) 3–69. | MR | Zbl | DOI
[13] and , Application of linear programming to the optimal difference triangle set problem. IEEE Trans. Inf. Theory 37 (1991) 1486–1488. | MR | DOI
[14] and , Equivalence of some LP-based lower bounds for the Golomb Ruler Problem. Discrete Appl. Math. 154 (2006) 120–144. | MR | Zbl | DOI
[15] and , On the complexity of constructing Golomb Rulers. Discrete Appl. Math. 157 (2009) 738–748. | MR | Zbl | DOI
[16] , , and , eds., Distance Geometry: Theory, Methods, and Applications. Springer, New York (2013). | MR | Zbl | DOI
[17] and , Design of orthogonal Golomb rulers with applications in wireless localization. In: Proc. of the 48th Asilomar Conference on Signals, Systems and Computers (2014) 1497–1501.
[18] and , A class of binary recurrent codes with limited error propagation. IEEE Trans. Inf. Theory 13 (1967) 106–113. | Zbl | DOI
[19] , Some new optimum Golomb rulers. IEEE Trans. Inf. Theory 36 (1990) 183–184. | MR | Zbl | DOI
[20] , Symmetric Golomb squares. IEEE Trans. Inf. Theory 50 (2004) 1846–1847. | MR | Zbl | DOI
[21] , Ein Satz uber trigonometrische polynome und seine anwendungen in der theorie der Fourier-Reihen. Math. Annal. 106 (1932) 536–539. | MR | Zbl | DOI
[22] , A theorem in finite projective geometry and some applications to number theory. Trans. Am. Math. Soc. 43 (1938) 377–385. | MR | JFM | DOI
[23] and , A Lagrangian relaxation for Golomb rulers. Lecture Notes Comput. Sci. 7874 (2013) 251–267. | Zbl | DOI
Cité par Sources :
