2026-09-22T03:57:40Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:26008 2026-09-05T19:34:17Z ddc:004 open_access

Integer Programming Models for the Median of a 0-1 String Set Under Levenshtein Distance Arbib, Claudio D'Ascenzo, Andrea Karaşan, Oya E. Pizzuti, Andrea Levenshtein Distance Median String Problem Integer Programming 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. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Claudio Arbib and Andrea D'Ascenzo and Oya E. Karaşan and Andrea Pizzuti 2026 Is Part Of LIPIcs, Volume 371, 24th International Symposium on Experimental Algorithms (SEA 2026) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.SEA.2026.4 urn:nbn:de:0030-drops-260081 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SEA.2026.4 eng https://creativecommons.org/licenses/by/4.0/legalcode