Since we are only given m distances maybe a numerical algorithm for MDS might work. For example we might start with a random nxn matrix and minimize the strain by gradient descent. For the desired runtime this would just have to converge in $O(m/n)$ steps. I’m not sure if this is realistic though. Also there might be better numerical algorithms for this specific problem. Has anyone looked into this yet?
I think running a single strain minimization iteration on m points in n dimensions takes O(m*n) steps. So there would need to be some reason to expect that it would converge in some constant (though possibly large) number of steps.
Unless you’re saying “for each node, run the strain minimization step until it converges, then do the same for each subsequent node”. I don’t know if the greedy algorithm works there, but if it does then maybe?
Also I kinda expect that if there’s something that works in O(n*m*log(m)) that’s probably fine.
(and yeah, “try the greedy exact solution for each node” was my “dumb solution” attempt).
Since we are only given m distances maybe a numerical algorithm for MDS might work. For example we might start with a random nxn matrix and minimize the strain by gradient descent. For the desired runtime this would just have to converge in $O(m/n)$ steps. I’m not sure if this is realistic though. Also there might be better numerical algorithms for this specific problem. Has anyone looked into this yet?
I think running a single strain minimization iteration on
mpoints inndimensions takes O(m*n) steps. So there would need to be some reason to expect that it would converge in some constant (though possibly large) number of steps.Unless you’re saying “for each node, run the strain minimization step until it converges, then do the same for each subsequent node”. I don’t know if the greedy algorithm works there, but if it does then maybe?
Also I kinda expect that if there’s something that works in
O(n*m*log(m))that’s probably fine.(and yeah, “try the greedy exact solution for each node” was my “dumb solution” attempt).