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: [img] PDF - Preprinted Version
Download (198kB) | Preview
Editorial actions: View Item View Item (Login required)
Content information:
Item Type: Article
Citations: 5 (Google Scholar) |
Uncontrolled Keywords: permutation groups integer linear programming
Subjects:
  • 90-XX Operations research, mathematical programming > 90Cxx Mathematical programming > 90C10 Integer programming

  • 20-XX Group theory and generalizations > 20Bxx Permutation groups > 20B40 Computational methods

    		•
    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