Mathematics and Computational Sciences

Practical algorithm for the Beltway problem with a complexity parameter introduction

Document Type : Original Article

Author

Reza Nadimi

Department of Computer Science, Faculty of Mathematical Sciences, University of Mazandaran, Iran.

https://doi.org/10.30511/mcs.2025.2041761.1234
Abstract
The Beltway problem is a famous computational geometry challenge relevant to fields like bioinformatics and crystallography.
Not only is the complexity class of the Beltway problem not known but there is no practical non-polynomial time algorithm to solve it. This paper models the problem as a Constraint Satisfaction
Problem (CSP) and applies a backtracking approach with forward-checking to explore the solution space. Moreover, it introduces a "multiplicity rate" parameter to measure the input's complexity, observing
that higher multiplicity generally increases run-time. To the best of the author's knowledge, no deterministic algorithm exists that can solve large instances of the Beltway problem.
Experimental results indicate that the algorithm
performs efficiently for low-multiplicity instances and acceptably under higher multiplicities.

Keywords

Reconstruction
Constraint Satisfaction
Forward Checking

Subjects

[1] Fomin E., A simple approach to the reconstruction of a set of points from the multiset of (n 2) pairwise distances in n2 steps for the sequencing problem: I. theory,J. Comput. Biol., vol 23(9), pp. 769–775, 2016.
[2] Fomin E., A simple approach to the reconstruction of a set of points from the multiset of (n 2) pairwise distances in n2 steps for the sequencing problem: II. algorithm, J. Comput. Biol.,vol 23(12), pp. 934–942, 2016.
[3] Fomin E., A simple approach to the reconstruction of a set of points from the multiset of (n 2) pairwise distances in n2 steps for the sequencing problem: III. noise inputs for the beltway case, J. Comput. Biol., vol 26 (1), pp. 68–75, 2019.
[4] Lemke, P., Skiena, S.S., Smith, W.D. Reconstructing Sets From Interpoint Distances. Discrete and Computational Geometry. vol 25, 2003. Springer, Berlin, Heidelberg.
[5] Shuai Huang and Ivan Dokmanic, Reconstructing Point Sets from Distance Distributions, IEEE Transactions on Signal Processing, vol. 69(1), pp. 1811–-1827, 2021.
[6] Skiena, S. S., Smith, W. D. and Lemke P., Reconstructing sets from interpoint distances, presented in Proceedings of the 6th SoCG, New York, NY, USA„ pp. 332–339, 1990.
Mathematics and Computational Sciences
Volume 6, Issue 1
Winter 2025
Pages 104-115

  • Receive Date 23 September 2024
  • Revise Date 07 November 2024
  • Accept Date 17 January 2025

Home

Submit Manuscript

Reviewers

Contact Us