The 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.

The Image Containment Problem and some classes of polynomial instances

RINALDI, Franca
2006-01-01

Abstract

The 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.
File in questo prodotto:
File Dimensione Formato  
2006SIAMOpt.pdf

non disponibili

Tipologia: Altro materiale allegato
Licenza: Non pubblico
Dimensione 261.38 kB
Formato Adobe PDF
261.38 kB Adobe PDF   Visualizza/Apri   Richiedi una copia

I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.

Utilizza questo identificativo per citare o creare un link a questo documento: https://hdl.handle.net/11390/857253
 Attenzione

Attenzione! I dati visualizzati non sono stati sottoposti a validazione da parte dell'ateneo

Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus 0
  • ???jsp.display-item.citation.isi??? 0
social impact