In this paper we consider the exact solution of the closest string problem (CSP). In general, exact algorithms for an NP-hard problem are either branch and bound procedures or dynamic programs. With respect to branch and bound, we give a new Integer Linear Programming formulation, improving over the standard one, and also suggest some combinatorial lower bounds for a possible non-ILP branch and bound approach. Furthermore, we describe the first dynamic programming procedure for the CSP.

New modeling ideas for the exact solution of the closest string problem

Giuseppe Lancia
2018

Abstract

In this paper we consider the exact solution of the closest string problem (CSP). In general, exact algorithms for an NP-hard problem are either branch and bound procedures or dynamic programs. With respect to branch and bound, we give a new Integer Linear Programming formulation, improving over the standard one, and also suggest some combinatorial lower bounds for a possible non-ILP branch and bound approach. Furthermore, we describe the first dynamic programming procedure for the CSP.
978-3-319-99132-0
File in questo prodotto:
File Dimensione Formato  
BIOKDD2018.pdf

non disponibili

Descrizione: draft
Tipologia: Documento in Pre-print
Licenza: Non pubblico
Dimensione 190.84 kB
Formato Adobe PDF
190.84 kB Adobe PDF   Visualizza/Apri   Richiedi una copia

I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.

Utilizza questo identificativo per citare o creare un link a questo documento: http://hdl.handle.net/11390/1128773
Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus 1
  • ???jsp.display-item.citation.isi??? 0
social impact