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