Publications of Claudio Gentile

This page shows all publications that appeared in the IASI annual research reports. Authors currently affiliated with the Institute are always listed with the full name.

You can browse through them using either the links of the following line or those associated with author names.

Show all publications of the year  2005, with author Gentile C., in the category IASI Research Reports (or show them all):


IASI Research Report n. 627  (Next)  

Antonio Frangioni, Claudio Gentile

Prim-Based BCT Preconditioners for Min-Cost Flow Problems

ABSTRACT
Support-graph preconditioners have been shown to be a valuable tool for the iterative solution, via a Preconditioned Conjugate Gradient method, of the KKT systems that must be solved at each ietration of an Interior Point algorithm for the solution of Min Cost Flow problems. Thesepreconditioners extract a proper triangulated subgraph, with "large" weight , of the original graph: in practice, trees and Brother-Connected Trees (BCTs) of depth two have been shown to be most computationally efficient families of subgraphs. In the literature, approximate versions of the Kruskal algorithm for maximum-weight spanning trees have most often been used for choosing the subgraphs; Prim-based approaches have been used for trees, but no comparison have ever been reported. We propose Prim-based heuristics for BCTs, which require nontrivial modifications w.r.t. the previously proposed Kruskal-based approaches, and present a computational comparison of the different approaches, and present a computational comparison of the different approaches, which shows that Prim-based heuristics are most often preferable to Kruskal-based ones.
back
- - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - -