News for hackers. Stuff that matters.
Re:Subhash Khot and the Unique Games Conjecture by beagle3 on Wednesday August 13, 2014 @04:31AM (#8171962)
Great description. Obviously codeflo knows this, but it's worth pointing out that "roundtrip" means "visiting every city exactly once". Euclidean problem geometry guarantees it (it's always faster to go directly) but many problems, even though emerging from seemingly euclidean space, do not have this property - e.g. if you're using a car, the road network might induce non-euclidean distance geometry that would make the fast roundtrip include more than one visit to a node.

There are no comments on this comment yet.