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-01-01
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.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.
