# Complexity of a weirdo two-dimensional sorting problem

Please forgive me if this is easy for some reason.

Suppose given $S$, a set of $n^2$ points in $\mathbb{R}^2$.

I want to choose a bijective map $f$ from $S$ to the set of lattice points in $\lbrace 0,\ldots,n-1\rbrace \times \lbrace 0,\ldots,n-1\rbrace$ so as to maximize the sum, over all $p$ in $S$, of the dot product $p \cdot f(p)$.

If, instead of $\mathbb{R}^2$, I had $\mathbb{R}^1$, and I was putting $S$ in bijection with $\lbrace0,\ldots,n-1\rbrace$, then this would simply be sorting $S$ and one knows how to do that fast.

For this problem, it's not even obvious to me how to do it in a number of steps that's polynomial in $n$.

Is this easy? Is it an example of a known genre of optimization problem?

-
I am somewhat tempted to vandalize your title by inserting a colon after the word "weirdo"... Nice question, by the way –  Yemon Choi Nov 4 '11 at 2:42
It would help to be more explicit about the goal. Please clarify p . f(p)? Gerhard "Ask Me About System Design" Paseman, 2011.11.03 –  Gerhard Paseman Nov 4 '11 at 2:54
It's a dot product, with the lattice points viewed as elements of the inner product space $\mathbb R^n$. Note to asker: mathbb is the command to make your R's look cool. Your problem is certainly a linear programming problem. I don't know anything more specific. –  Will Sawin Nov 4 '11 at 3:10
Well, en.wikipedia.org/wiki/Hungarian_algorithm certainly works here but, perhaps, you can do even better. –  fedja Nov 4 '11 at 3:14

To elaborate on the comments of Will Sawin and fedja: The question isn't a sorting problem, but it is a matching problem. If $S$ is your arbitrary set and $G = [n]^2$ is your grid, then you are marrying elements of $S$ to elements in $G$, where the happiness of each marriage is your dot product $p \cdot f(p)$. Any happiness function on $S \times G$, not necessarily one that is bilinear in the plane, can be maximized in polynomial time. That's because the convex hull of the set of permutation matrices has few facets: It's the Birkhoff polytope of doubly stochastic matrices. You can apply the general theorem that linear programming with polynomially many facets can be done in polynomial time. For the specific case of the Birkhoff polytope, there is an optimized linear programming algorithm, the Hungarian algorithm, that was discovered and known to be fast before the result that LP is polynomial time in general.

The Hungarian algorithm is already much faster than generic optimization strategies (which generally aren't polynomial time at all). The remaining question is whether you can devise a sorting algorithm that's even faster, maybe even quasilinear time like linear sorting. It's difficult to rule that out, but the setup is sufficiently complicated that I'd be surprised/impressed.

I guess one thing is worth trying: Whether you can prove that you climb to the maximum by separately sorting each row and column of the grid until the permutation is both row-stable and column-stable. That looks a bit like linear programming, and it also looks like a shortcut. Even if this idea doesn't work, it might ably accelerate those linear programming algorithms that travel along the 1-skeleton of the polytope, such as the simplex algorithm. You could also throw in sorting along other straight lines. The Hungarian algorithm does not travel along the 1-skeleton; instead it's a dual/primal algorithm. Actually, traveling along the 1-skeleton of the Birkhoff polytope is a tricky matter because the vertices are highly degenerate. But there are tricks for that such as desingularizing the polytope by making a generic perturbation of the facets.

-