Return to Colloquia & Seminar listing

### Highly Symmetric Integer Linear Programs

**Algebra & Discrete Mathematics**

Speaker: | Prof. Michael Joswig, Technical Univ. Darmstadt Germany |

Location: | 2112 MSB |

Start time: | Fri, Sep 2 2011, 12:00PM |

A symmetry of an ILP is a linear transformation which acts as a signed permutation on the variables. Deciding the feasibility of an ILP is a well-known NP-dard problem. However, provided that the group of symmetries contains the alternating group A_n (in its standard action), we can present an algorithm which solves an ILP with m constraints in n variables in O(mn^2) time. Further, it will be discussed how finding ILP symmetries can be reduced to a graph isomorphism problem. This is joint work with Richard B\"odi and Katrin Herr.