User daniel - MathOverflow most recent 30 from http://mathoverflow.net 2013-06-20T00:53:31Z http://mathoverflow.net/feeds/user/7412 http://www.creativecommons.org/licenses/by-nc/2.5/rdf http://mathoverflow.net/questions/30976/condition-number-for-ellipsoid-method-matrix Condition number for Ellipsoid method matrix daniel 2010-07-07T23:22:05Z 2010-11-21T16:22:13Z <p>Hello,</p> <p>When using the ellipsoid method (for solving a linear program for example), the volume of the ellipsoid at each iteration is proven to decrease, and do so by at least a factor of $e^{1/2n}$.</p> <p>What can you say about the condition number of the ellipsoid? Specifically, a good result would guarantee a slow increase in the condition number (maybe depending on volume decrease).</p> <p>Thanks,</p> <p>Daniel</p> http://mathoverflow.net/questions/40784/trees-with-the-same-degree-sequences/40793#40793 Answer by daniel for Trees with the same degree sequences daniel 2010-10-01T21:36:19Z 2010-10-01T21:36:19Z <p>Consider two trees $G$ and $H$ with 14 vertices. Both will have degree sequence $(2,0,6,6)$ i.e. having two vertices of degree 4. $G$ will have the two 4-vertices connected to 3 leaves each and with a 6 vertex long chain between them. $H$ will have the two 4-vertices connected with a single edge. In addition, each will have three 2 vertex long chains connected to them (one 2-vertex connected to a leaf).</p> <p>Finally, each leaf of $G$ is connected to a 4 vertex and each leaf of $H$ is connected to a 2 vertex.</p> <p>A picture would do the trick better.</p> http://mathoverflow.net/questions/39946/transitive-closure-of-multigraphs Transitive closure of multigraphs daniel 2010-09-25T12:53:24Z 2010-09-29T14:43:52Z <p>The transitive closure of a <em>directed graph</em>, is another directed graph which encodes the reachability of nodes from other nodes. If $G$ is a graph, the edge $(v_1,v_2)$ is in it's transitive closure $G^{tc}$ iff there is a directed path from $v_1$ to $v_2$ in $G$.</p> <p>A <em>multigraph</em> can have multiple edges between nodes. The question is what would be natural definitions for the transitive closure of a multigraph?</p> <p>An obvious answer would be the transitive closure of the induced graph (same graph with multiple edges between verices replaced with a single edge).</p> <p>Are there already interesting graphs derivable from a multigraph which could earn the title of 'transitive closure'?</p> http://mathoverflow.net/questions/40784/trees-with-the-same-degree-sequences/40793#40793 Comment by daniel daniel 2010-10-01T22:22:46Z 2010-10-01T22:22:46Z Of course, there is a simpler example with 10 vertices. Perhaps I can even draw: =&gt;-&lt;= and &gt;-----&lt; . http://mathoverflow.net/questions/30976/condition-number-for-ellipsoid-method-matrix Comment by daniel daniel 2010-07-09T19:20:50Z 2010-07-09T19:20:50Z I've had a look at the reference (will have to dig deeper though). Since I am looking for a worst-case bound, a specific run would provide a lower bound for the worst-case. Intuitively, I think the case which cuts the ellipsoid in the same direction each iteration, will increase condition number maximally. Starting from a ball, this produces a single sequence of ellipses, with exponentially rising condition number (but a smaller exponent than the one controlling volume). Again, no calculation, just intuitive guessing. http://mathoverflow.net/questions/30976/condition-number-for-ellipsoid-method-matrix Comment by daniel daniel 2010-07-08T11:40:11Z 2010-07-08T11:40:11Z Not an explicit reference. But I can try and make the problem clearer. First an ellipsoid can be defined as: $E = \{ x | (x-c)^{T} S^{-1} (x-c) &lt; 1 \}$ with $c$ the center and $S$ a positive semi-definite matrix. The condition number of $S$ can be given as $\lambda_{max}/\lambda_{min}$. It is an expression of how elongated the ellipsoid is. Furthermore, in the ellipsoid algorithm, the ellipsoid is updated every iteration to a new one covering the intersection of the old ellipsoid with a half plane (to keep things simple, let us assume the half-plane goes through the center $c$).