MathOverflow is a question and answer site for professional mathematicians. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

The Littlewood-Richardson cone $LR_{n, k}$ consists of all $k-$tuples $(a_1, a_2, \dots, a_k)$ of real $n-$vectors with monotonically decreasing entries such that there exist $k$ $n \times n-$Hermitian matrices $A_1, A_2, \dots, A_k$ such that $A_1 + A_2 + \dots + A_k = 0$ and their eigenvalues are the entries in the respective vectors $a_1, \dots, a_k$.

A consequence of Knutson and Tao's work in, (and results of Groschel-Lovasz-Schrijver's book on combinatorial optimization) is that one can optimize a linear function over an affine slice of this cone (which is polyhedral, but has exponentially many facets) in polynomial time.

Although its description is more complicated than the orthant or the cone of positive semi-definite matrices, this cone does seem a basic object. So here, finally, is the question:

Are there any combinatorial optimization questions that can be relaxed to linear optimization over such convex sets?

share|cite|improve this question

Your Answer


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

Browse other questions tagged or ask your own question.