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.
2021
Tree-shaped facility; Variance criterion; Mean absolute deviation criterion; Conic linear programming; Semidefinite programming relaxation
01 Pubblicazione su rivista::01a Articolo in rivista
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.
File allegati a questo prodotto
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.

Utilizza questo identificativo per citare o creare un link a questo documento: https://hdl.handle.net/11573/1504957
Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus 1
  • ???jsp.display-item.citation.isi??? 0
social impact