User mcuturi - MathOverflow most recent 30 from http://mathoverflow.net 2013-05-23T15:11:39Z http://mathoverflow.net/feeds/user/9804 http://www.creativecommons.org/licenses/by-nc/2.5/rdf http://mathoverflow.net/questions/128985/how-do-you-call-a-function-that-satisfies-the-metric-axioms-except-for-the-coinci how do you call a function that satisfies the metric axioms except for the coincidence axiom? mcuturi 2013-04-28T08:11:28Z 2013-04-28T08:23:51Z <p>Hello everyone.</p> <p>I am studying a bivariate function $d$ on a set $\mathcal{X}\times \mathcal{X}$ which is <strong>symmetric</strong> and satisfies all <strong>triangle inequalities</strong> but does not agree with the coincidence axiom (which says that $d(x,y)=0\Leftrightarrow x=y$). </p> <p>Pseudodistances are such that only $d(x,y)=0 \Leftarrow x=y$. </p> <p>In the case I am concerned with, the function is actually such that $d(x,y)>0$ for <strong>all</strong> $x,y$ (including $d(x,x)>0$) and so only the implication $\Rightarrow$ would be valid, trivially because $d(x,y)$ is never 0.</p> <p>I have been looking for a proper generalization of distance functions that would take into account that case but I have not found any. Do such functions bear a name and have they ever been considered in the context of generalized metrics?</p> <p>Many thanks in advance, Marco</p> http://mathoverflow.net/questions/98327/in-a-transportation-problem-given-a-northwestern-corner-rule-solution-how-many In a transportation problem, given a northwestern corner rule solution, how many row and column permutations correspond to that solution? mcuturi 2012-05-30T04:30:24Z 2012-05-30T06:35:24Z <p>Consider a $n,n$ transportation problem with two $d$ dimensional integral vectors $r$ and $c$ with the same total sum.</p> <p>The Northwestern corner rule is a simple way to create a basic feasible solution to the transportation problem, that is find an integral matrix $X$ with row-sum equal to $r$ and column-sum equal to $c$. </p> <p>Described with examples <a href="http://www.universalteacherpublications.com/univ/ebooks/or/Ch5/nw.htm" rel="nofollow">here</a>, the rule iteratively creates a transportation table $$X=[x_{ij}]_{i,j\leq d}$$ between $r$ and $c$ by going through the following steps (paraphrasing the bottom of Page 2 of this <a href="http://www.newton.ac.uk/preprints/NI02033.pdf" rel="nofollow">preprint</a> by L. Stougie):</p> <p>The rule starts by giving the highest possible value to $x_{11}$, and at each step when a highest possible value is given to entry $x_{ij}$ it moves on to $x_{ij+1}$ in case $x_{ij}$ filled column $j$, or to $x_{i+1j}$ in case $x_{ij}$ filled row $i$, and proceeds until $x_{nn}$ has received a value.</p> <p>L. Stougie makes the remark at the bottom of Page 2 that any row or column permutation (that is in the order of $r$ or $c$) yields a unique Northwestern solution, but that there exists an exponential number of row/column permutations that may share the same Northwestern solution. </p> <p>My question is: do we know what that number is? </p> <p>Although I can imagine from a combinatorial point of view why this number may grow exponentially (suppose $d\geq 5$ that $r$ starts as $r=[5,\cdots]$ and $c$ as $c=[1,1,1,1,1,...]$ then there are at least $5!$ different permutations of the order of $c$ that will leave the Northwestern solution unchanged) I wonder if there is a way to compute this number exactly?</p> http://mathoverflow.net/questions/75873/extreme-points-of-transportation-polytope/93868#93868 Answer by mcuturi for Extreme points of transportation polytope mcuturi 2012-04-12T14:07:26Z 2012-04-12T14:07:26Z <p>The answer above is partially wrong. The kind of extreme points which are obtained through the construction above, known as the northwest corner rule, can only generate a subset of extreme points (not all of them) of the polytope. To be more precise, the northwest rule can only generate those extreme points for which the graph (as described in the bottom of the answer above) is a caterpillar tree, as can be checked further here: <a href="http://www.newton.ac.uk/preprints/NI02033.pdf" rel="nofollow">http://www.newton.ac.uk/preprints/NI02033.pdf</a></p> http://mathoverflow.net/questions/13682/which-mathematical-ideas-have-done-most-to-change-history/58620#58620 Answer by mcuturi for Which mathematical ideas have done most to change history? mcuturi 2011-03-16T07:50:30Z 2011-03-16T08:31:36Z <p>The central limit theorem, with all its application in statistics and test theory, which guide a lot of current research in the medical sciences as well as the social sciences. On a more general note, the notion of statistics, tests, and risk assessment. Given the recent turn of events I guess we still have a lot to learn unfortunately.</p> <p>You can also get some ideas by looking in the article </p> <p>"The Best of the 20th Century: Editors Name Top 10 Algorithms" published in 2000 in SIAM news. The pdf can be accessed here for instance:</p> <p><a href="http://x86.cs.duke.edu/courses/fall06/cps258/references/topten.pdf" rel="nofollow">http://x86.cs.duke.edu/courses/fall06/cps258/references/topten.pdf</a></p> http://mathoverflow.net/questions/53469/concise-formula-for-number-of-paths-from-0-0-to-n-m-with-horizontal-vertical concise formula for number of paths from (0,0) to (n,m) with horizontal, vertical and diagonal moves? mcuturi 2011-01-27T09:29:40Z 2011-01-27T12:52:03Z <p>The number of increasing paths from (0,0) to (n,m) with only vertical (north) and horizontal (east) moves can be easily proved to be $\binom{n+m}{n}$. When adding the possibility of making diagonal (north-east) moves, I get that the total number of possible paths is $F(n,m)=\sum_{p=\max(n,m)}^{n+m}\binom{p}{n+m-p, p-m, p-n}$.</p> <p>I am wondering if there is a more concise (without the sum) formula for $F$ or any pointer to a more precise study of $F$? The relation $F(n,m)=F(n-1,m)+F(n-1,m-1)+F(n,m-1)$ can also provide us with the bivariate generating function of $F$ but I am not sure that helps... Many thanks in advance.</p> http://mathoverflow.net/questions/128985/how-do-you-call-a-function-that-satisfies-the-metric-axioms-except-for-the-coinci Comment by mcuturi mcuturi 2013-04-29T04:52:13Z 2013-04-29T04:52:13Z And to answer Pietro, I plan to use that in a machine learning context, so it's an applied problem. I'll probably stick to $1_{x\ne y} d(x,y)$ to turn it (somewhat artificially, I agree) into a distance. http://mathoverflow.net/questions/128985/how-do-you-call-a-function-that-satisfies-the-metric-axioms-except-for-the-coinci Comment by mcuturi mcuturi 2013-04-29T04:49:31Z 2013-04-29T04:49:31Z Thanks for all your comments! I gave it some extra thought. I see two links: negative definite kernels (in the sense of [Berg Christensen Ressel](<a href="http://books.google.co.jp/books/about/Harmonic_analysis_on_semigroups.html?id=zz2DQgAACAAJ&amp;redir_esc=y" rel="nofollow">books.google.co.jp/books/about/&hellip;</a>). They consider negative definite kernels $\psi$ (p.82) that may not be such that $\psi(x,x)=0$. Negative definite kernels and distances are different, but they are somewhat related (the bigger, the more different). The other thing that's easy to check is that $1_{x\ne y} d(x,y)$ is itself a distance. It's not continuous.. but still a distance! http://mathoverflow.net/questions/98327/in-a-transportation-problem-given-a-northwestern-corner-rule-solution-how-many Comment by mcuturi mcuturi 2012-05-30T08:23:22Z 2012-05-30T08:23:22Z Brendan, many thanks for your first comment. Thinking aloud now: consider the partial sums $R_i=\sum_{k=1}^d r_i$ and define $C_i$ accordingly. We can consider $n(X)$ column permutations that leave $X$ unchanged, where $n(X)= \prod_{j=1}^{d-1} p_j!$ where $p_j=\text{card}\{ i| 1\leq i \leq d, R_{j} \leq C_i &lt; R_{j+1}\}$. I am not sure this is enough though... http://mathoverflow.net/questions/98327/in-a-transportation-problem-given-a-northwestern-corner-rule-solution-how-many Comment by mcuturi mcuturi 2012-05-30T07:22:38Z 2012-05-30T07:22:38Z The number of caterpillar forests is indeed an upper bound on the number of NWC solutions, since the graph corresponding to a NWC solution is a caterpillar forest. My question is more simple (I think): given $r$, $c$ and corresponding solution NWC solution $X$, how many row and column permutations of $r$ and $c$ correspond to that solution? http://mathoverflow.net/questions/75873/extreme-points-of-transportation-polytope/93868#93868 Comment by mcuturi mcuturi 2012-04-13T01:08:29Z 2012-04-13T01:08:29Z Apologies... I misread your answer. You are right, what you describe is not the NWC but a more general approach. Many thanks for your comment, it was very useful. http://mathoverflow.net/questions/53469/concise-formula-for-number-of-paths-from-0-0-to-n-m-with-horizontal-vertical Comment by mcuturi mcuturi 2011-01-27T21:53:24Z 2011-01-27T21:53:24Z Thanks for the tip! Will definitely do that next time. Thanks to everyone for helping me on this one!!