# Tag Info

0

You have a $1D$ minimization problem and not an $argmin$-problem. Here, you could easily use a 1-Wasserstein distance (commonly known as the Earth mover's distance). For the 1-dimensional case, there is a closed form solution compute-able in linear time. I'll write more when I have the time.

5

You can formulate this problem as an assignment problem of the form $\min \sum_{i=1}^{n} \sum_{j=1}^{n} w_{i,j}x_{i,j}$ subject to $\sum_{j=1}^{n} x_{i,j}=1,\; i=1, 2, \ldots, n$ $\sum_{i=1}^{n} x_{i,j}=1, \; j=1, 2, \ldots, n$ $x_{i,j}=\mbox{0 or 1} \; i=1, 2, \ldots, n, j=1, 2, \ldots, n.$ Basically, $x_{i,j}=1$ if column $i$ of $A$ is matched with ...

2

I have not solved this exact problem, but a nearby problem is finding rational approximations to decimals (eg 0.333 => 1/3), for which I have used an algorithm called "mediant search". Under the hood, this search traverses an (implicit/infinite) data structure called the "Stern-Brocot tree", which is a novel way to enumerate every possible rational number in ...

4

Very interesting question! LAPACK-inspired adaptive strategy This reminds me of a bug that was found in a LAPACK routine (rank-revealing QR) related to 'downdating' norms: essentially, you are given the norm of a vector v, and you want to compute at each iteration in O(1) the norm of the same vector after chopping off its initial entry: v[1:], v[2:], ... (...

Top 50 recent answers are included