Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

Since it is known that you can sort $n$ numbers by solving a certain kind of linear program - doesn't this imply a lower bound on the complexity of solving linear programs in general via the lower bound for sorting? But it's a bit tricky since the linear program in question has $n^2$ variables and $2n$ equalities. There is another method I know of that has $n$ variables and $2^n$ inequalities (although that number of inequalities can surely be reduced) - but I don't know how you could translate this into a lower bound...

For the linear program with $n^2$ variables and $2n$ equalities see this article (right at the bottom). If you are skeptical that this formulation does indeed sort the numbers, here is a matlab implementation.

Actually this particular formulation can be made more succint. Consider the optimization problem

max sum(D*P*x) over all permutation matrices P

here D is the matrix with 1,2,...n on the diagonal. Any increasing sequence would work as well - but 1,2,...n is pretty clear. x = (x1,x2,...,xn) is the vector of values to be sorted. So after applying some permutation you weight the value with D. So we want to solve this optimization problem for all the values of P (since D and x are known). sum() is the sum over all vector components. Since all the equations for this turn out to be linear this problem is solvable as a linear program.

share|improve this question

1 Answer 1

up vote 1 down vote accepted

The lower bound you get is not very helpful. Your program has size (at least) $n^2$, and the sorting lower bound is $n\log n$ arithmetic operations. This is sublinear in the size of the program, so you could get a better bound by showing that there are linear programs whose solution requires reading the entire input.

Even worse, extracting the sorted sequence out of the solution of the LP also takes time $\Omega(n^2)$, so that you actually don't get any lower bound at all! For all you know, the LP could have been solved at an instant, since the ensuing $n^2$ time expended to extract the sorted list would still be consistent with the $\Omega(n\log n)$ lower bound.

One last thing, if your list contains duplicates, then an optimal solution need not be integral. So a further "rounding" step may be required to turn it into an integral solution, depending on the algorithm (the simplex would always produce an integral solution).

share|improve this answer
    
It doesn't seem right that extracting the sorted sequence should be an $\Omega(n^2)$ operation... You are basically multiplying the sequence with the suitable permutation matrix (that is the (reshape(v,n,n)*x')' step in the matlab implementation). To say that multiplying a vector with a permutation matrix is a $\Omega(n^2)$ operation does not sound right at all. –  Peter Sheldrick Jun 11 '11 at 23:12
1  
The matrix has $n^2$ entries, so your matlab code is certainly $\Omega(n^2)$. It's true that there might be more efficient algorithms that exploit the fact that it's a permutation matrix, but one can probably show that the permutation simply cannot be determined with $o(n^2)$ probes. –  Yuval Filmus Jun 11 '11 at 23:34
    
Yuval Filmus, for the special case of a cyclic permutation, which is still a permuation matrix but also a circulant matrix, we can do it with an $n\log n$ fourier transform. So at least in this special case it's clearly not $n^2$. –  Peter Sheldrick Jun 11 at 22:20

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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