Recent advances on the polyhedral combinatorics of the Balanced Minimum Evolution Problem (BMEP) enabled the identification of fundamental characteristics of the convex hull of the BMEP (or BMEP polytope) as well as the description of some of its facets. These results have been possible thanks to the assistance of general purpose softwares for polyhedral analyses, such as Polymake, whose running times however increase exponentially in function of input size. In this article, we address the problem of designing tailored algorithms for the study of the BMEP polytope, with special focus on the problem of enumerating its vertices. To this end, by exploiting some results from the polyhedral combinatorics of the BMEP and a particular encoding scheme based on Prüfer coding, we present an iterative enumeration algorithm that is faster than current general purpose softwares and that can be natively massively parallelized.

Recent advances on the polyhedral combinatorics of the Balanced Minimum Evolution Problem (BMEP) enabled the identification of fundamental characteristics of the convex hull of the BMEP (or BMEP polytope) as well as the description of some of its facets. These results have been possible thanks to the assistance of general purpose softwares for polyhedral analyses, such as Polymake, whose running times however become quickly unpractical. In this article, we address the problem of designing tailored algorithms for the study of the BMEP polytope, with special focus on the problem of enumerating its vertices. To this end, by exploiting some results from the polyhedral combinatorics of the BMEP and a particular encoding scheme based on Prfifer coding, we present an iterative enumeration algorithm that is markedly faster than current general purpose softwares and that can be natively massively parallelized. (C) 2019 Elsevier Ltd. All rights reserved.

Enumerating Vertices of the Balanced Minimum Evolution Polytope

Raffaele Pesenti;
2019

Abstract

Recent advances on the polyhedral combinatorics of the Balanced Minimum Evolution Problem (BMEP) enabled the identification of fundamental characteristics of the convex hull of the BMEP (or BMEP polytope) as well as the description of some of its facets. These results have been possible thanks to the assistance of general purpose softwares for polyhedral analyses, such as Polymake, whose running times however increase exponentially in function of input size. In this article, we address the problem of designing tailored algorithms for the study of the BMEP polytope, with special focus on the problem of enumerating its vertices. To this end, by exploiting some results from the polyhedral combinatorics of the BMEP and a particular encoding scheme based on Prüfer coding, we present an iterative enumeration algorithm that is faster than current general purpose softwares and that can be natively massively parallelized.
File in questo prodotto:
File Dimensione Formato  
BMEP_Vertex_Enum.pdf

non disponibili

Descrizione: Articolo principale
Tipologia: Documento in Pre-print
Licenza: Accesso chiuso-personale
Dimensione 191.15 kB
Formato Adobe PDF
191.15 kB Adobe PDF   Visualizza/Apri

I documenti in ARCA 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/10278/3713251
Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus 4
  • ???jsp.display-item.citation.isi??? 4
social impact