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?
No comments:
Post a Comment