Prim-based support-graph preconditioners for Min-Cost Flow Problems (Articolo in rivista)

Type
Label
  • Prim-based support-graph preconditioners for Min-Cost Flow Problems (Articolo in rivista) (literal)
Anno
  • 2007-01-01T00:00:00+01:00 (literal)
Alternative label
  • Frangioni, A.; Gentile, C. (2007)
    Prim-based support-graph preconditioners for Min-Cost Flow Problems
    in Computational optimization and applications
    (literal)
Http://www.cnr.it/ontology/cnr/pubblicazioni.owl#autori
  • Frangioni, A.; Gentile, C. (literal)
Pagina inizio
  • 271 (literal)
Pagina fine
  • 287 (literal)
Http://www.cnr.it/ontology/cnr/pubblicazioni.owl#numeroVolume
  • 36 (literal)
Rivista
Http://www.cnr.it/ontology/cnr/pubblicazioni.owl#note
  • n.2-3 ISSN 0926-6003 (literal)
Note
  • ISI Web of Science (WOS) (literal)
Http://www.cnr.it/ontology/cnr/pubblicazioni.owl#affiliazioni
  • Frangioni Antonio, Università di Pisa, Dipartimento di Informatica associato presso IASI (literal)
Titolo
  • Prim-based support-graph preconditioners for Min-Cost Flow Problems (literal)
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 iteration of an Interior Point algorithm for the solution of Min Cost Flow problems. These preconditioners 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 the 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, which shows that Prim-based heuristics are most often preferable to Kruskal-based ones. (literal)
Prodotto di
Autore CNR
Insieme di parole chiave

Incoming links:


Autore CNR di
Prodotto
Http://www.cnr.it/ontology/cnr/pubblicazioni.owl#rivistaDi
Insieme di parole chiave di
data.CNR.it