Let M be a non-negative square matrix. To each permutation P of its rows and columns we associate the sum S(P)of the cells that lie above the diagonal. By triangularization of the matrix M we mean the combinatorial problem of finding a permutation that minimizes S(P). The problem is NP hard, except that the case of an order matrix. Up to now only heiristic techiques existed, but it only very bad estimates on their goodness were available. The technique presented here finds in many cases of economical interest the optimal solution joining graph technique and integer programming. Releasing integrity condition and passing to the dual problem allows a powerful simplification through a proper analysis of intersectorial cycles. Mostly the released solution happens to be integer, thus solving the problem. Otherwise it supplies a very good upper estimate of the degree of linearity. Application is then made for Leontief's input-output matrixes of EU counties.

An exact method for triangularizing input-output matrixes

PICCININI, Livio Clemente;CHANG, Ting Fa Margherita
2007-01-01

Abstract

Let M be a non-negative square matrix. To each permutation P of its rows and columns we associate the sum S(P)of the cells that lie above the diagonal. By triangularization of the matrix M we mean the combinatorial problem of finding a permutation that minimizes S(P). The problem is NP hard, except that the case of an order matrix. Up to now only heiristic techiques existed, but it only very bad estimates on their goodness were available. The technique presented here finds in many cases of economical interest the optimal solution joining graph technique and integer programming. Releasing integrity condition and passing to the dual problem allows a powerful simplification through a proper analysis of intersectorial cycles. Mostly the released solution happens to be integer, thus solving the problem. Otherwise it supplies a very good upper estimate of the degree of linearity. Application is then made for Leontief's input-output matrixes of EU counties.
File in questo prodotto:
File Dimensione Formato  
Piccinini_ChangTriang.pdf

non disponibili

Tipologia: Altro materiale allegato
Licenza: Non pubblico
Dimensione 189.21 kB
Formato Adobe PDF
189.21 kB Adobe PDF   Visualizza/Apri   Richiedi una copia

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/11390/883497
 Attenzione

Attenzione! I dati visualizzati non sono stati sottoposti a validazione da parte dell'ateneo

Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus ND
  • ???jsp.display-item.citation.isi??? ND
social impact