UC Davis Mathematics

Mathematics Colloquia and Seminars

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.