New answers tagged algorithms
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
Is there an efficient algorithm for calculation of continued fraction expansion from decimal digits?
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
