most recent 30 from http://mathoverflow.net 2013-05-21T03:49:33Z http://mathoverflow.net/feeds/question/33255 http://www.creativecommons.org/licenses/by-nc/2.5/rdf http://mathoverflow.net/questions/33255/can-the-littlewood-richardson-cone-be-used-for-combinatorial-optimization Hari 2010-07-25T07:25:38Z 2010-07-25T07:25:38Z

<p>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$.</p> <p>A consequence of Knutson and Tao's work in</p> <p><a href="http://www.ams.org/journals/jams/1999-12-04/S0894-0347-99-00299-4/S0894-0347-99-00299-4.pdf" rel="nofollow">http://www.ams.org/journals/jams/1999-12-04/S0894-0347-99-00299-4/S0894-0347-99-00299-4.pdf</a>, (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.</p> <p>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:</p> <p>Are there any combinatorial optimization questions that can be relaxed to linear optimization over such convex sets? </p>