This paper considers the special case of the robust network design problem where the dominant extreme points of the demand polyhedron have a disjoint support. In this case static and dynamic routing lead to the same optimal solution, both for the splittable and the unspittable case. As a consequence, the robust network design problem with (splittable) dynamic routing is polynomially solvable, whereas it is coNP-Hard in the general case. This result applies to particular instances of the single-source Hose model.
Static and Dynamic Routing Under Disjoint Dominant Extreme Demands
FRANGIONI, ANTONIO;SCUTELLA', MARIA GRAZIA
2011-01-01
Abstract
This paper considers the special case of the robust network design problem where the dominant extreme points of the demand polyhedron have a disjoint support. In this case static and dynamic routing lead to the same optimal solution, both for the splittable and the unspittable case. As a consequence, the robust network design problem with (splittable) dynamic routing is polynomially solvable, whereas it is coNP-Hard in the general case. This result applies to particular instances of the single-source Hose model.File in questo prodotto:
File | Dimensione | Formato | |
---|---|---|---|
pdrelse.pdf
accesso aperto
Descrizione: Documento in Post-print
Tipologia:
Documento in Post-print
Licenza:
Creative commons
Dimensione
159.87 kB
Formato
Adobe PDF
|
159.87 kB | Adobe PDF | Visualizza/Apri |
I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.