Locating a discrete subtree of minimum variance on trees: New strategies to tackle a very hard problem

Abstract In this paper we study the problem of finding a discrete subtree of minimum variance with bounded size of a given tree. We show that the problem is NP-hard on very simple trees and it remains difficult even if we consider the Mean Absolute Deviation criterion on star graphs. Referring to the variance criterion, we first propose a reformulation of the problem as an Integer Quadratic Program that, however, does not have particular structural properties that may help in finding good lower bounds on the optimal value of the problem. Then, basing on recent results on conic optimization, we investigate alternative reformulations of the problem in order to obtain some lower bounds. In particular, we exploit a continuous linear, conic, reformulation of the problem and show that this is, in fact, an exact linear reformulation of the Integer Quadratic Program. Alternatively, by referring to the upper envelope approach, we show how to obtain a lower bound for the optimal objective function value of our discrete tree-shaped facility location problem in pseudo-polynomial time.