Optimal 24 mark Golomb Ruler Proven

globring writes "Four years ago, distributed.net users undertook the search for the optimal 24 mark Golomb Ruler. This year sees the successful conclusion of that effort. The diagram of the optimal ruler can be seen here. If you have no idea what a Golomb Ruler is, you can read up on them. Work on finding the optimal 25 mark ruler is still in progress."

Comments

Brute forcing useful but not as interesting

[TheLink]

Brute forcing is like what some alchemists did - try all the combinations and get a result.

It's more interesting if you can find a "summary" or new point of view.

Also, IMO a solution (not talking about proof) that is magnitudes larger than the problem is not very good, and that a good solution is like good "compression".

Distribution of differences?

[Anonymous Coward]

The linked figure containing intrapair differences for the 24-mark OGR was very interesting to me.

I suppose I could look this up, but I'm too lazy at the moment, and I'm not an expert in math.

But I'm wondering if anyone knows what the distribution of intrapair differences looks like. Does it follow any known distribution? Is it something that someone has looked into?

I'm in statistics, so these things are interesting to me.

Is'nt RC5-72 rather useless?

[GQuon]

Slashdot beat the Amiga team in OGR-24, but the Amiga team is leading the Slashdot team in OGR-25: OGR-25 Team Listing

But the Dutch Power Cows leads in both efforts.

OGR-24 blocks have been scarce for the last few months, so the statistics have been rather erratic.

At least the OGR effort is more useful than the RC5-72 effort. We showed how quick DES and RC5-56 could be broken quickly with a bruce force attack with spare CPU cycles. But why do RC5-72? It's not that interesting.

I'm doing OGR-25 now, and when that's finished I might go on to something like folding @ home, if there's a client.

Such a thing as a "Complete" Golomb ruler?

[dschuetz]

Do Golomb rulers exist that can measure every integer distance from 1 up to their length?

That is, a ruler with marks at (0,1,2) can measure lengths of 1, 2, and 3 units, and is 3 units long. The sample ruler on the above-linked site has marks at (0,1,4,9,11), and can measure every length between 1 and 11 EXCEPT 6. You can swap the first two blocks (giving (0,3,4,9,11)) but then you lose the ability to measure 10.

I guess what I'm asking is whether these rulers exist, and how many are they? Or is there a point where they stop being possible?

Re:Such a thing as a "Complete" Golomb ruler?

[JiffyPop]

What I take from the minimum rulers you give is that they prove that if you have a ruler that can measure every distance from 1 to 11 that it will either be longer than 11 units or it will have more than one way to measure at least one of the lengths. Looking at a table of optimal golomb rulers (google) I see that any optimal golomb ruler longer than 6 units (4 marks at 0-1-4-6) is not "complete," or in other words it cannot measure every unit distance up to and including its length.

Re:Such a thing as a "Complete" Golomb ruler?

[Anonymous Coward]

For an n-mark ruler, the length has to be n*(n-1)/2 because that's the number of ways of picking 2 marks, and we're asking for that many distinct distance, from 1 to n*(n-1)/2.

For 5 marks and more it's impossible. Here's the best you can do:

5 mark (0,1,2,7,10), 9/10 distinct distances
6 mark (0,1,2,4,9,15), 13/15 distinct distances
7 mark (0,1,3,6,13,17,21), 19/21 distinct distances
8 mark (0,1,7,11,20,23,25,28), 26/28 distinct distances
9 mark (0,1,2,3,14,21,26,30,36), 32/36 distinct distances
10 mark (0,1,2,10,24,27,32,39,43,45), 40/45 distinct distances

Gollumb rulers and np-complete problems

[davidwr]

I'm no expert on np-complete problems, and this is literally an off-the-cuff idea, so feel free to shoot it down or run with it:

Someone once proved that np-complete problems map to each other. That is, if you solve one, you've solved them all. this page linked in the main story suggests that Golumb Rulers are "like" np complete problems. If it is indeed np complete, then maybe an efficient-but-suboptimal solution to the Golomb Ruler problem will map to any other np-complete problem.

The same link mentions cyclic difference sets as a means of producing very efficient Golumb rulers, at least up to n=150.

If this technique maps to other problems, like the travelling-salesman problem, then "practical" albeit not-quite-optimal solutions can be found relatively easily. If you are a traveling salesman, do you really care if your 100-stop route has a small amount of waste, if finding a better solution might take 10 years of cpu time?

Likewise, if there are other "not quite optimal" solutions to np-complete problems for n>150, perhaps these solutions can be applied to the Golumb ruler problem, to generate "good enough" rulers of longer lengths.

Of course, if the Golumb ruler problem doesn't map to the other problems, then "nevermind."