What question did this study set out to answer?

This research aims to find the optimal median string that minimizes distances in a binary string set using integer programming models.

June 17, 2026Open Access

Integer Programming Models for the Median of a 0-1 String Set Under Levenshtein Distance

Key Points

This research aims to find the optimal median string that minimizes distances in a binary string set using integer programming models.
Developed two novel integer linear programming models for median string optimization.
Conducted numerical experiments comparing the new models to existing formulations in the literature.
The proposed integer linear programming models outperformed existing methods.
Numerical experiments demonstrated significant improvements in solution efficiency.

Abstract

The Median String Problem calls for finding a string that minimizes the average distance from a given set of strings. Under the Levenshtein (or edit) metric, the problem is NP-hard even for binary strings. We devised two novel integer linear programming models for this case and tested them against the only formulation we are aware of in the literature. Our numerical experiments attest to the efficacy of the proposed approach.

KI fragen

Bookmark

View Full Paper

Cite This Study

Arbib et al. (Thu,) studied this question.

synapsesocial.com/papers/6a323aead50b63ecad205ab7 https://doi.org/https://doi.org/10.4230/lipics.sea.2026.4

Also Consider

Synapse has enriched 5 closely related papers on similar clinical questions. Consider them for comparative context:

KI fragen

Bookmark

View Full Paper