Search Results

Documents authored by Arbib, Claudio


Artifact
Software
D-hash/CenterLevenshtein

Authors: Claudio Arbib, Andrea D'Ascenzo, Oya E. Karaşan, and Andrea Pizzuti


Abstract

Cite as

Claudio Arbib, Andrea D'Ascenzo, Oya E. Karaşan, Andrea Pizzuti. D-hash/CenterLevenshtein (Software). Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2026)


Copy BibTex To Clipboard

@misc{dagstuhl-artifact-26233,
   title = {{D-hash/CenterLevenshtein}}, 
   author = {Arbib, Claudio and D'Ascenzo, Andrea and Kara\c{s}an, Oya E. and Pizzuti, Andrea},
   note = {Software, swhId: \href{https://archive.softwareheritage.org/swh:1:dir:29a2a7464e7ff0450026b55e399cfb749ef45866;origin=https://github.com/D-hash/CenterLevenshtein;visit=swh:1:snp:01fac08accd9c558de37aafc2b6b7af41b9bd484;anchor=swh:1:rev:234e93fa9babbd9987d9525c0e32669a4668a0a8}{\texttt{swh:1:dir:29a2a7464e7ff0450026b55e399cfb749ef45866}} (visited on 2026-06-15)},
   url = {https://github.com/D-hash/CenterLevenshtein},
   doi = {10.4230/artifacts.26233},
}
Document
Integer Programming Models for the Median of a 0-1 String Set Under Levenshtein Distance

Authors: Claudio Arbib, Andrea D'Ascenzo, Oya E. Karaşan, and Andrea Pizzuti

Published in: LIPIcs, Volume 371, 24th International Symposium on Experimental Algorithms (SEA 2026)


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.

Cite as

Claudio Arbib, Andrea D'Ascenzo, Oya E. Karaşan, and Andrea Pizzuti. Integer Programming Models for the Median of a 0-1 String Set Under Levenshtein Distance. In 24th International Symposium on Experimental Algorithms (SEA 2026). Leibniz International Proceedings in Informatics (LIPIcs), Volume 371, pp. 4:1-4:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2026)


Copy BibTex To Clipboard

@InProceedings{arbib_et_al:LIPIcs.SEA.2026.4,
  author =	{Arbib, Claudio and D'Ascenzo, Andrea and Kara\c{s}an, Oya E. and Pizzuti, Andrea},
  title =	{{Integer Programming Models for the Median of a 0-1 String Set Under Levenshtein Distance}},
  booktitle =	{24th International Symposium on Experimental Algorithms (SEA 2026)},
  pages =	{4:1--4:15},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-422-2},
  ISSN =	{1868-8969},
  year =	{2026},
  volume =	{371},
  editor =	{Aum\"{u}ller, Martin and Finocchi, Irene},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SEA.2026.4},
  URN =		{urn:nbn:de:0030-drops-260081},
  doi =		{10.4230/LIPIcs.SEA.2026.4},
  annote =	{Keywords: Levenshtein Distance, Median String Problem, Integer Programming}
}
Any Issues?
X

Feedback on the Current Page

CAPTCHA

Thanks for your feedback!

Feedback submitted to Dagstuhl Publishing

Could not send message

Please try again later or send an E-mail