Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

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?

share|improve this question
2  
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
2  
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
7  
Well, en.wikipedia.org/wiki/Hungarian_algorithm certainly works here but, perhaps, you can do even better. –  fedja Nov 4 '11 at 3:14

1 Answer 1

up vote 18 down vote accepted

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.

share|improve this answer

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.