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

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

http://www.ams.org/journals/jams/1999-12-04/S0894-0347-99-00299-4/S0894-0347-99-00299-4.pdf, (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|improve this question

Your Answer

 
discard

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

Browse other questions tagged or ask your own question.