The auction-reduction algorithm is a strongly polynomial version of the auction method for the shortest path problem. In this paper we extend the auction-reduction algorithm to different types of shortest hyperpath problems in directed hypergraphs. The results of preliminary computational experiences show that the auction-reduction method is comparable to other known methods for specific classes of hypergraphs.
Auction algorithms for shortest hyperpath problems / R., DE LEONE; Pretolani, Daniele. - In: SIAM JOURNAL ON OPTIMIZATION. - ISSN 1052-6234. - STAMPA. - 11:1(2000), pp. 149-159. [10.1137/S1052623498343477]
Auction algorithms for shortest hyperpath problems
PRETOLANI, Daniele
2000
Abstract
The auction-reduction algorithm is a strongly polynomial version of the auction method for the shortest path problem. In this paper we extend the auction-reduction algorithm to different types of shortest hyperpath problems in directed hypergraphs. The results of preliminary computational experiences show that the auction-reduction method is comparable to other known methods for specific classes of hypergraphs.
Pubblicazioni consigliate
I metadati presenti in IRIS UNIMORE sono rilasciati con licenza Creative Commons CC0 1.0 Universal, mentre i file delle pubblicazioni sono rilasciati con licenza Attribuzione 4.0 Internazionale (CC BY 4.0), salvo diversa indicazione.
In caso di violazione di copyright, contattare Supporto Iris
