1
$\begingroup$

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 first 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.

The networks I am most interested in studying have the following properties.

  • The comparator network has n inputs and up to 2*n comparators
  • Every line is connected to at least one comparator
  • No two comparators are connected to the same two horizontal lines
  • The output of the network is sorted
  • The network is not a sorting network

I am only interested in linear optimization over the input variables and I would like to know if there is a simpler way to solve this problem (the network described above) than running a linear program. Linear programming is fine but I just wanted to make sure I wasn't missing anything obvious.

Does the comparator network described have any properties that make a simpler algorithm possible?

Thank you,

$\endgroup$

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.