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. 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.
Actions:
Download: |
Download (198kB) | Preview |
---|---|
Editorial actions: | ![]() |
Content information:
Item Type: | Article |
---|---|
Citations: | 5 (Google Scholar) | |
Uncontrolled Keywords: | permutation groups integer linear programming |
Subjects: |
|
Divisions: | Institute of Computer Science > Computer Science Department - Prof. Dr. Juenger |
Related URLs: |
Deposit Information:
ZAIK Number: | zaik2004-470 |
---|---|
Depositing User: | Christoph Buchheim |
Date Deposited: | 25 Nov 2005 00:00 |
Last Modified: | 12 Jan 2012 10:28 |
URI: | http://e-archive.informatik.uni-koeln.de/id/eprint/470 |