PulseExploreJournal ClubDebatesTrendingResearchersJournals
Instagram
HomeExploreJournal ClubTrending
Synapse
⌘+K
Synapse
June 17, 20260 citationsOpen Access

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

View Full Paper
CAClaudio ArbibADAndrea D’AscenzoOKOya Ekin Karaşan

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.

Ask AI
Helpful
Bookmark
Share
View Full Paper

Cite This Study

Arbib et al. (2026) studied this question.

synapsesocial.com/papers/6a323aead50b63ecad205ab7https://doi.org/10.4230/lipics.sea.2026.4
Ask AI
Helpful
Bookmark
Share
View Full Paper