I am interested in using Michel Goemans' extended formulation first developed for the permutahedron to study comparator networks that are not sorting networks. In his paper "Smallest Compact Formulation for the Permutahedron" (An online version is available here http://math.mit.edu/~goemans/PAPERS/permutahedron.pdf), he shows that any sorting network can be used to obtain an extended formulation for the permutahedron. This is done by expressing each comparator in the network by a set of linear constraints.

In another paper, "Extended Formulations in Combinatorial Optimization," Conforti et al. discuss this formulation and show that it can also be applied to any comparator network, sorting networks being a special case (It's Theorem 6.8 in Section 6.5 in the version of the paper shown here http://integer.tepper.cmu.edu/webpub/ExtFor-Feb2010.pdf). I am interested in using this extended formulation to look at a specific class of comparator networks.

My question is this (basically a sanity check to make sure I understood the proof correctly and that it is valid).

Can the extended formulation developed by Michael Goemans be applied to comparator networks that are not sorting networks such that in every vertex the input to the network will be a permutation of {1, 2, ... n} that the comparator network will sort? I believe that's what the proof in Conforti et al says but I just wanted to be sure.

Thank you,


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.