ARCA è l'archivio istituzionale ad accesso aperto della ricerca dell'Università Ca' Foscari Venezia e nasce nel 2014 con lo scopo di raccogliere, diffondere e conservare la produzione scientifica dell'Università. Costituisce di fatto il catalogo della ricerca di Ateneo.ARCA è un sistema Open Access: è non solo consultabile da tutti e visibile nei motori di ricerca, ma anche interoperabile con il portale cerCa. In questo modo vengono valorizzate la produzione scientifica dell'Ateneo e la visibilità dei ricercatori.
EnglishThe image containment problem (ICP) is a minimum cost design problem concerning the containment of particular polyhedra, called zonotopes, that are images of boxes through linear transformations. The ICP is NP-hard. Here we study a family of nontrivial ICP instances, called worst case demand (WCD) instances. We prove that such instances can be recognized and solved in polynomial time via linear programming. Then we characterize the classes of instances that are WCD independently on the choice of the cost vector (structurally worst case demand classes (SWCD)) and we show that recognizing whether a class of instances is SWCD is a coNP-complete problem. Finally, we describe two families of SWCD classes that are interesting from an applicative point of view: the classes defined by the incidence matrices of particular directed graphs and those defined by pre-Leontief matrices.
| Autori: | |
| Titolo: | The image containment problem and some classes of polynomial instances |
| Data di pubblicazione: | 2006 |
| Appare nelle tipologie: | 2.1 Articolo su rivista |
File in questo prodotto:
| File | Descrizione | Tipologia | Licenza | |
|---|---|---|---|---|
| 2006SIAMOpt.pdf | Post-print | Accesso chiuso-personale | Riservato |
http://hdl.handle.net/10278/28940
Copyright © 2019