Boosting Perturbation-Based Iterative Algorithms to Compute the Median String

Simple item page
datacite.creatorMirabal, Pedro
datacite.creatorAbreu, Jose
datacite.creatorSeco, Diego
datacite.creatorPedreira, Oscar
datacite.creatorChavez, Edgar
datacite.date2021-12-23
datacite.rightsAcceso Abierto
datacite.subject.englishalgorithm initialization
datacite.subject.englishApproximate median string
datacite.subject.englishhalf space proximal neighbors
datacite.titleBoosting Perturbation-Based Iterative Algorithms to Compute the Median String
dc.date.accessioned2025-01-29T20:19:21Z
dc.date.available2025-01-29T20:19:21Z
dc.descriptionFunding sponsor Horizon 2020 Framework Programme. Funding number 690941. Acronym H2020.
dc.description.abstractenThe most competitive heuristics for calculating the median string are those that use perturbation-based iterative algorithms. Given the complexity of this problem, which under many formulations is NP-hard, the computational cost involved in the exact solution is not affordable. In this work, the heuristic algorithms that solve this problem are addressed, emphasizing its initialization and the policy to order possible editing operations. Both factors have a significant weight in the solution of this problem. Initial string selection influences the algorithm's speed of convergence, as does the criterion chosen to select the modification to be made in each iteration of the algorithm. To obtain the initial string, we use the median of a subset of the original dataset; to obtain this subset, we employ the Half Space Proximal (HSP) test to the median of the dataset. This test provides sufficient diversity within the members of the subset while at the same time fulfilling the centrality criterion. Similarly, we provide an analysis of the stop condition of the algorithm, improving its performance without substantially damaging the quality of the solution. To analyze the results of our experiments, we computed the execution time of each proposed modification of the algorithms, the number of computed editing distances, and the quality of the solution obtained. With these experiments, we empirically validated our proposal.
dc.identifier.doi10.1109/ACCESS.2021.3137767
dc.identifier.urihttps://repositoriodigital.uct.cl/handle/10925/6167
dc.language.isoen
dc.rightsObra bajo licencia Creative Commons 4.0
dc.sourceIEEE Access
oaire.citationEndPage169308
oaire.citationStartPage169299
oaire.citationTitleArtículo
oaire.citationVolume9
oaire.resourceTypeArtículo
uct.catalogadormlj
uct.departamentoDepartamento de Ingeniería Informática
uct.indizacionSCOPUS
Files
Original bundle
Now showing 1 - 1 of 1
Thumbnail Image
Name:
Mirabal_Abreu_Seco_Pedreira_Chavez_Boosting_IEEE_2021_Vol9_169299-169308
Size:
1017.1 KB
Format:
Adobe Portable Document Format
Description:
Download
License bundle
Now showing 1 - 1 of 1
Thumbnail Image
Name:
license.txt
Size:
803 B
Format:
Item-specific license agreed upon to submission
Description:
Download
Collections
Ciencias de la Ingeniería