"Linear Optimization over Permutation Groups"
Article by Christoph Buchheim, Michael Jünger, available as BibTeX Source.
Zentrum für Angewandte Informatik Köln, Lehrstuhl Jünger
Preprint Key:	zaik2004-470
Keywords:	integer linear programming, permutation groups
MSC codes:	20B40, 90C10
This article was published in 2005 in the journal "Discrete Optimization", volume 2, number 4, pages 308--319.
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.