The cost of hyperpaths in directed hypergraphs can be measuread in various different ways, which have been used in a wide set of applications. Not surprisingly, depending on the considered measure function the cost to find optimum hyperpaths may range from NP-hard to linear time. A first solution for finding optimum hyperpaths in case of a superior functions (SUP) can be found in a seminal work by Knuth [5], which generalizes Dijkstra’s Algorithm [3] to deal with a grammar problem. In this paper we define a hierarchy of classes of optimization problems based on the properties of the cost measures. After showing that measures can be classified on the basis of the structure of the optimum hyperpath they determine, we present an alternative taxonomy of measure functions, based on their analytic properties, and prove structure theorems that relate the two hierarchies.
Structure theorems for optimum hyperpaths in directed hypergraphs / Ausiello, Giorgio; G. F., Italiano; Laura, Luigi; Nanni, Umberto; F., Sarracco. - STAMPA. - 7422:(2012), pp. 1-14. (Intervento presentato al convegno 2nd International Symposium on Combinatorial Optimization, ISCO 2012 tenutosi a Athens nel 19 April 2012 through 21 April 2012) [10.1007/978-3-642-32147-4_1].
Structure theorems for optimum hyperpaths in directed hypergraphs
AUSIELLO, Giorgio;LAURA, Luigi;NANNI, Umberto;
2012
Abstract
The cost of hyperpaths in directed hypergraphs can be measuread in various different ways, which have been used in a wide set of applications. Not surprisingly, depending on the considered measure function the cost to find optimum hyperpaths may range from NP-hard to linear time. A first solution for finding optimum hyperpaths in case of a superior functions (SUP) can be found in a seminal work by Knuth [5], which generalizes Dijkstra’s Algorithm [3] to deal with a grammar problem. In this paper we define a hierarchy of classes of optimization problems based on the properties of the cost measures. After showing that measures can be classified on the basis of the structure of the optimum hyperpath they determine, we present an alternative taxonomy of measure functions, based on their analytic properties, and prove structure theorems that relate the two hierarchies.File | Dimensione | Formato | |
---|---|---|---|
VE_2012_11573-759804.pdf
solo gestori archivio
Tipologia:
Versione editoriale (versione pubblicata con il layout dell'editore)
Licenza:
Tutti i diritti riservati (All rights reserved)
Dimensione
278.44 kB
Formato
Adobe PDF
|
278.44 kB | Adobe PDF | Contatta l'autore |
I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.