Corrupted distances, still a near-optimal spanning tree: logarithmic approximation under arbitrary tampering, with no true-distance queries
In a metric whose pairwise distances are each corrupted with fixed probability by an adversary, an algorithm sees only the corrupted values. For increase-only, decrease-only and unrestricted corruption, the work gives polynomial-time or quasi-polynomial-time approximations, reaching a logarithmic factor in the unrestricted case that matches the known information-theoretic lower bound, all without querying true distances.