Linear Optimization over Permutation Groups
Buchheim, Christoph and Jünger, Michael
(2005)
Linear Optimization over Permutation Groups.
Published in:
Discrete Optimization Vol. 2 (4).
pp. 308319.
Abstract
For a permutation group given by a set of generators, the problem of finding "special" group members is NPhard 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&cuttechnique.
Actions:
Download: 
PDF
 Preprinted Version
Download (198kB)  Preview 

Export as:  [error in script] 
Editorial actions:  View Item (Login required) 
Content information:
Item Type:  Article 

Citations:  [error in script] 5 (Google Scholar)  [error in script] 
Uncontrolled Keywords:  [error in script] 
Subjects: 

Uncontrolled Keywords:  permutation groups, integer linear programming 
Subjects:  90XX Operations research, mathematical programming > 90Cxx Mathematical programming > 90C10 Integer programming 20XX Group theory and generalizations > 20Bxx Permutation groups > 20B40 Computational methods 
Divisions:  Institute of Computer Science > Computer Science Department  Prof. Dr. Juenger 
Depositing User:  Christoph Buchheim 
Date Deposited:  25 Nov 2005 00:00 
Last Modified:  12 Jan 2012 10:28 
Deposit Information:
ZAIK Number:  [error in script] 

Depositing User:  Christoph Buchheim 
Date Deposited:  25 Nov 2005 00:00 
Last Modified:  12 Jan 2012 10:28 
URI:  http://earchive.informatik.unikoeln.de/id/eprint/470 