This chapter is devoted to compact extended formulations of tree problems. First, we give a compact extended formulation for the relaxation of the Steiner tree problem. We then describe the well-known minimum spanning tree problem, for which there exist polynomial algorithms and exponential-size models. We use both LP techniques and nonnegative rank factorization to provide compact extended formulations. Finally we present two NP-hard problems related to spanning trees of some relevance in the literature. The first one deals with bounded-degree spanning trees and the second one with minimal routing-cost trees, that have a considerable importance in network design and computational biology.
Trees
Lancia G.;Serafini P.
2018-01-01
Abstract
This chapter is devoted to compact extended formulations of tree problems. First, we give a compact extended formulation for the relaxation of the Steiner tree problem. We then describe the well-known minimum spanning tree problem, for which there exist polynomial algorithms and exponential-size models. We use both LP techniques and nonnegative rank factorization to provide compact extended formulations. Finally we present two NP-hard problems related to spanning trees of some relevance in the literature. The first one deals with bounded-degree spanning trees and the second one with minimal routing-cost trees, that have a considerable importance in network design and computational biology.I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.
