Universität zu Köln

Buchheim, Christoph ORCID: 0000-0001-9974-404X and Jünger, Michael (2005). Linear Optimization over Permutation Groups. Discrete Optimization, 2 (4). pp. 308-319. Springer.

Preview

PDF zaik2004-470.pdf - Draft Version Download (198kB) | Preview

Abstract

For a permutation group given by a set of generators, the problem of finding "special" group members is NP-hard in many cases. E.g., this is true for the problem of finding a permutation with a minimum number of fixed points or a permutation with a minimal Hamming distance from a given permutation. Many of these problems can be modeled as linear optimization problems over permutation groups. We develop a polyhedral approach to this general problem and derive an exact and practically fast algorithm based on the branch&cut-technique.

Item Type:	Article
Creators:	Creators Email ORCID ORCID Put Code Buchheim, Christoph UNSPECIFIED https://orcid.org/0000-0001-9974-404X UNSPECIFIED Jünger, Michael UNSPECIFIED UNSPECIFIED UNSPECIFIED
URN:	urn:nbn:de:hbz:38-548769
Journal or Publication Title:	Discrete Optimization
Volume:	2
Number:	4
Page Range:	pp. 308-319
Date:	2005
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/54876