News for hackers. Stuff that matters.
Re:Computer Scientists Break Traveling Salesperson Record by kats on Thursday October 08, 2020 @02:17PM (#24722039)
> proved that an algorithm devised a decade ago beats Christofides’ 50% factor, though they were only able to subtract 0.2 billionth of a trillionth of a trillionth of a percent.

That is 0.0000000000000000000000000000000002% better than the existing solution.

Re:Computer Scientists Break Traveling Salesperson Record by morcheeba on Thursday October 08, 2020 @06:55PM (#24724828)
So much less than the 0.01% of the variation in identical computers due to 100ppm crystal variation. Also less than the 0.0001% variation due to the temperature in the room changing 1 degree.
Re:Computer Scientists Break Traveling Salesperson Record by jobigoud on Friday October 09, 2020 @03:29AM (#24727680)
Wonder if it's less than the probability of getting hit by a cosmic ray flipping a bit somewhere in the implementation and changing the result.
Re:Computer Scientists Break Traveling Salesperson Record by bitcharmer on Friday October 09, 2020 @04:25AM (#24727928)
This is very interesting.

Where can I find more details on crystal quality in popular CPUs like Intel's Xeons?

Re:Computer Scientists Break Traveling Salesperson Record by morcheeba on Friday October 09, 2020 @12:07PM (#24731273)
XEONs use a 100MHz referenced called "BCLK" and scale this up to the different frequencies it needs internally (core, dram, pci, etc.). Typically this info is found in the datasheet, but only the DC parameters (voltage min/max) etc were found in the first datasheet I found. Timing is so important that often processor manufacturers will have an apnote discussing it in detail, often with suggested parts and circuit layouts.

https://www.intel.com/content/www/us/en/products/docs/proces...

Re:Computer Scientists Break Traveling Salesperson Record by jquery on Thursday October 08, 2020 @09:12PM (#24725701)
That’s might be all they were able to prove, although in practice the results may be much better.
Re:Computer Scientists Break Traveling Salesperson Record by blackbear_ on Thursday October 08, 2020 @04:16PM (#24723415)
Are you missing two zeros or am I counting incorrectly? The paper claims an improvement of 10-36 or smaller
Re:Computer Scientists Break Traveling Salesperson Record by triclops200 on Thursday October 08, 2020 @04:20PM (#24723461)
Percent moves two zeros over factor
Re:Computer Scientists Break Traveling Salesperson Record by gitgud on Thursday October 08, 2020 @10:28PM (#24726126)
Is it a probabilistic improvement, like over millions of iterations?

It does mention choosing tree paths at random... so couldn't that be an improvement by chance?

Re:Computer Scientists Break Traveling Salesperson Record by lamchob on Friday October 09, 2020 @05:12AM (#24728141)
No, they don't just random sample the base trees and hope for a better result. Their "actual work" is providing a 80 page proof for their improvement.