User mcuturi - MathOverflow

how do you call a function that satisfies the metric axioms except for the coincidence axiom?

2013-04-28T08:11:28Z

Hello everyone.

I am studying a bivariate function $d$ on a set $\mathcal{X}\times \mathcal{X}$ which is symmetric and satisfies all triangle inequalities but does not agree with the coincidence axiom (which says that $d(x,y)=0\Leftrightarrow x=y$).

Pseudodistances are such that only $d(x,y)=0 \Leftarrow x=y$.

In the case I am concerned with, the function is actually such that $d(x,y)>0$ for all $x,y$ (including $d(x,x)>0$) and so only the implication $\Rightarrow$ would be valid, trivially because $d(x,y)$ is never 0.

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?

Many thanks in advance, Marco

In a transportation problem, given a northwestern corner rule solution, how many row and column permutations correspond to that solution?

2012-05-30T04:30:24Z

Consider a $n,n$ transportation problem with two $d$ dimensional integral vectors $r$ and $c$ with the same total sum.

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$.

Described with examples here, 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 preprint by L. Stougie):

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.

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.

My question is: do we know what that number is?

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?

Answer by mcuturi for Extreme points of transportation polytope

2012-04-12T14:07:26Z

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: http://www.newton.ac.uk/preprints/NI02033.pdf

Answer by mcuturi for Which mathematical ideas have done most to change history?

2011-03-16T07:50:30Z

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.

You can also get some ideas by looking in the article

"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:

http://x86.cs.duke.edu/courses/fall06/cps258/references/topten.pdf

concise formula for number of paths from (0,0) to (n,m) with horizontal, vertical and diagonal moves?

2011-01-27T09:29:40Z

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}$.

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.

Comment by mcuturi

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.

Comment by mcuturi

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](books.google.co.jp/books/about/…). 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!

Comment by mcuturi

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 < R_{j+1}\}$. I am not sure this is enough though...

Comment by mcuturi

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?

Comment by mcuturi

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.

Comment by mcuturi

2011-01-27T21:53:24Z

Thanks for the tip! Will definitely do that next time. Thanks to everyone for helping me on this one!!