24
$\begingroup$

A surprising number of problems have fairly natural reductions to linear programming (LP). See Chapter 7 of [1] for examples such as network flows, bipartite matching, zero-sum games, shortest paths, a form of linear regression, and even circuit evaluation!

Since circuit evaluation reduces to linear programming, any problem in $P$ must have a linear programming formulation. Therefore, we have a "new" sorting algorithm, via reduction to a linear program. So, my questions are

  1. What is the linear program that will sort an array of $n$ real numbers?
  2. What is the running time of the reduce-to-LP-and-solve sorting algorithm?

  1. Algorithms by S. Dasgupta, C. Papadimitriou and U. Vazirani (2006)
$\endgroup$
  • 1
    $\begingroup$ Spoiler: pine.cs.yale.edu/pinewiki/… $\endgroup$ – Joe Sep 30 '12 at 1:22
  • 3
    $\begingroup$ If you already know the answer, why are you asking the question? $\endgroup$ – Yuval Filmus Sep 30 '12 at 6:49
  • 2
    $\begingroup$ @Joe It is fine to post interesting material even if you know the answer. The conventional way to do so is to answer your own question with an (elaborate) take (instead of posting a links to some document, which may break). $\endgroup$ – Raphael Sep 30 '12 at 16:47
  • $\begingroup$ @Raphael If no one else writes an answer, then I will when I have time. $\endgroup$ – Joe Sep 30 '12 at 20:38
  • $\begingroup$ @YuvalFilmus asking a question that you know the answer to is explicitly encouraged on stack exchange. $\endgroup$ – Joe Sep 30 '12 at 20:40
23
$\begingroup$

The following answer is basically equivalent to the one you already know, but may seem a bit less "magical". On the other hand, it's more technical, but I believe the general technique "write your problem as an optimization on permutation matrices and invoke Birkhoff-von Neumann" is a great one to know.

For a permutation $\sigma$ of $\{1, \ldots, n\}$ define the permutation matrix $P_\sigma$ as the 0-1 matrix such that $P_{ij} = 1$ if $j = \sigma(i)$ and $P_{ij}=0$ otherwise. This is simply the matrix which permutes the coordinates of a vector $x$ according to $\sigma$: if $y = P_\sigma x$ then $y_i = x_{\sigma(i)}$. I'll denote $y=P_{\sigma}x$ as $\sigma(x)$ from now on.

One more definition: a non-negative $n\times n$ matrix $M$ is doubly-stochastic if each one of its rows and each one of its columns sums to 1.

And one fact which is very important in combinatorial optimization - the Birkhoff-von Neumann theorem:

A matrix $M$ is doubly stochastic if and only if it is a convex combination of permutation matrices, i.e. if and only if there exist permutations $\sigma_1, \ldots, \sigma_k$ and positive reals $\alpha_1 , \ldots, \alpha_k$ such that $M = \sum_{i = 1}^k{\alpha_i P_{\sigma_i}}$ and $\sum{\alpha_i} = 1$.

Notice that a doubly stochastic matrix is defined by the inequalities

$$\forall i: \sum_{j = 1}^n{M_{ij}} = 1$$ $$\forall j: \sum_{i = 1}^n{M_{ij}} = 1$$ $$\forall i, j: M_{ij} \geq 0$$

All these inequalities taken together determine a polytope $P$, and the Birkhoff-von Neumann theorem states that the extremal points (vertices) of this polytope are all permutation matrices. From basic linear programming, we know this implies that any linear program which has the above inequalities as its constraints (and no other constraints) will have a permutation matrix as an optimal solution.

So given an input $a = (a_1, \ldots, a_n)$ to be sorted, we just need to come up with a linear objective $f_a(M)$ for which:

  • $f_a(P_\tau) < f_a(P_\sigma)$ if $\sigma(a)$ is sorted but $\tau(a)$ is not.

Then formulate a linear program with objective to maximize $f_a(M)$ and the inequalities above as constraints, and you are guaranteed that an optimal solution is the permutation matrix $P_\sigma$ for $\sigma$ such that $\sigma(a)$ is sorted. Of course, it's easy to "read off" $\sigma$ from $P_\sigma$.

One choice for $f_a(M)$ is $v^T M a$ where $v = (1, \ldots, n)$. Verify that

  • this is linear in $M$;
  • for $P_\sigma$, $f_a(P_\sigma) = \sum_{i = 1}^n{i a_{\sigma(i)}}$;
  • the above is maximized at the $\sigma$ for which $\sigma(a)$ is sorted (by contradiction: otherwise you could switch two coordinates of $\sigma(a)$ and achieve a higher value).

And voila, you have a linear program for sorting. Seems silly for sorting, but this is in fact a powerful method in optimization.

$\endgroup$
  • 1
    $\begingroup$ Something I have not dealt with: when there are multiple optimal solutions, some of them will not be permutation matrices (and some of course will). There are many easy ways to fix that: by perturbation you can remove duplicates in $a$. $\endgroup$ – Sasho Nikolov Sep 30 '12 at 23:24
  • 1
    $\begingroup$ When there are multiple optimal solutions some may not be permutation matrices (but always some optimal solution will be a permutation matrix). If the objective function is constant, then all feasible solutions are optimal. $\endgroup$ – Sasho Nikolov Apr 9 '17 at 18:30
  • 1
    $\begingroup$ @Turbo the linear program is completely written in this answer. Obviously it has no integrality constraints. I am not going to attempt to answer your second question. Sit down and try to write down GI as optimizing a linear function over doubly stochastic matrices, the way I have done here for sorting. See for yourself where it fails. $\endgroup$ – Sasho Nikolov Apr 25 '18 at 14:05
  • 1
    $\begingroup$ In practice you'd probably want to use simplex, but in theory you can get a polynomial time algorithm using a polynomial time LP solver, for example an interior point method, or the ellipsoid method. This will give you time polynomial in the bit complexity of $a$. When the constraint matrix is TUM (as is the case here), there exist strongly polytime solvers too cstheory.stackexchange.com/questions/4454/…. $\endgroup$ – Sasho Nikolov Jul 3 at 13:38
  • 1
    $\begingroup$ And yes, the easiest thing to do is to make sure you have a unique optimal solution, which you can do by adding a tiny random perturbation to $a$. $\endgroup$ – Sasho Nikolov Jul 3 at 13:45

Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.