Universität zu Köln

Jünger, Michael, Lee, Eva K., Mutzel, Petra ORCID: 0000-0001-7621-971X and Odenthal, Thomas (1997). A Polyhedral Approach to the Multi-Layer Crossing Minimization Problem. Springer. ['eprint_fieldopt_monograph_type_preprint' not defined].

Preview

PDF zpr97-299.pdf - Submitted Version Download (214kB) | Preview

Abstract

We study the multi-layer crossing minimization problem from a polyhedral point of view. After the introduction of an integer programming formulation of the multi-layer crossing minimization problem, we examine the 2-layer case and derive several classes of facets of the associated polytope. Preliminary computational results for 2- and 3-layer instances indicate, that the usage of the corresponding facet-defining inequalities in a branch-and-cut approach may only lead to a practically useful algorithm, if deeper polyhedral studies are conducted.

Item Type:	Monograph (['eprint_fieldopt_monograph_type_preprint' not defined])
Creators:	Creators Email ORCID ORCID Put Code Jünger, Michael UNSPECIFIED UNSPECIFIED UNSPECIFIED Lee, Eva K. UNSPECIFIED UNSPECIFIED UNSPECIFIED Mutzel, Petra UNSPECIFIED https://orcid.org/0000-0001-7621-971X UNSPECIFIED Odenthal, Thomas UNSPECIFIED UNSPECIFIED UNSPECIFIED
URN:	urn:nbn:de:hbz:38-548170
Series Name:	Lecture notes in computer science
Volume:	1353
Page Range:	pp. 13-24
Date:	1997
Publisher:	Springer
Language:	English
Faculty:	Faculty of Mathematics and Natural Sciences
Divisions:	Faculty of Mathematics and Natural Sciences > Department of Mathematics and Computer Science > Institute of Computer Science
Subjects:	Data processing Computer science
Refereed:	No
URI:	http://kups.ub.uni-koeln.de/id/eprint/54817