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.
Locating a discrete subtree of minimum variance on trees: New strategies to tackle a very hard problem / Puerto, J.; Ricca, F.; Scozzari, A.. - In: DISCRETE APPLIED MATHEMATICS. - ISSN 0166-218X. - 289:(2021), pp. 78-92.
Locating a discrete subtree of minimum variance on trees: New strategies to tackle a very hard problem
F. Ricca;A. Scozzari
2021
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.File | Dimensione | Formato | |
---|---|---|---|
Ricca_Locating-subtree_2021.pdf
solo gestori archivio
Tipologia:
Versione editoriale (versione pubblicata con il layout dell'editore)
Licenza:
Tutti i diritti riservati (All rights reserved)
Dimensione
698.58 kB
Formato
Adobe PDF
|
698.58 kB | Adobe PDF | Contatta l'autore |
I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.