ZIB

Treffer pro Seite

Treffer 1 - 1 | 1 Treffer

Sortierung

Digitale Medien

The convex hull of a linear congruence relation in zero-one variables (1995)

Alevras, Dimitris ; Rijal, Minendra P.

Springer

Mathematical methods of operations research 41 (1995), S. 1-23

zur Merkliste hinzufügen auf der Merkliste

Details

ISSN: 1432-5217

Quelle: Springer Online Journal Archives 1860-2000

Thema: Mathematik , Wirtschaftswissenschaften

Notizen: Abstract A class of optimization problems over subsets of zero-one vectors of then-dimensional unit cube given by a special linear congruence relation is considered. The general problem is formulated as a zero-one linear program, minimal and complete descriptions of the associated polytopes by linear inequalities are derived and an $$\mathcal{O}(n \log n)$$ time algorithm for the optimization problems is given. Since the number of inequalities that completely describe the polytope grows exponentially withn, we also give a separation algorithm that identifies violated inequalities in time $$\mathcal{O}(n^2 )$$ . A particular variation of the bin packing problem is a special case of our problem and can thus be solved in polynomial time.

Materialart: Digitale Medien

URL: http://dx.doi.org/10.1007/BF01415061

Permalink

Bibliothek	Standort	Signatur	Band/Heft/Jahr	Verfügbarkeit

Andere fanden auch interessant ...

Artikel (Nationallizenzen)

Volltext

Treffer 1 - 1 | 1 Treffer