Slashdot Mirror
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."
you can't. i think the idea is that it has no redundant measurements, for example, 1235 measures 3 and 5 twice, 3215 does the same thing, 3512 does 3 twice, etc.
Yes.
0 mark
1 mark (0)
2 mark (0,1)
3 mark (0,1,3)
4 mark (0,1,4,6)
These are all OGRs, and complete. 5 is the first OGR where it is not complete. I don't think they stop being possible (but I could well be wrong).
Ratboy
Just another "Cubible(sic) Joe" 2 17 3061
Not really, alchemists were trying everything under the sun that could possibly convert something into gold. Brute forcing is a proven technique where you have an educated guess of what the problem is and then you use compuational cycles to do it.
My UID is prime is yours?
Actually, strictly speaking, both the travelling salesman problem and finding an efficient Gollumb ruler with n marks are not NP-complete. To be NP-complete, a problem must require a yes/no solution.
For instance "Is this particular Gollumb ruler optimal among all Gollumb rulers with n marks" asks a yes/no question, and could therefore be NP-complete. Also, the problem "Does there exist a way to visit the following cities without travelling more than n miles" is a decision problem. Note that we can usually phrase non-decision problems as decision problems, but going in the other direction can be trickier... you may in fact have to use the yes/no algorithm an exponentially growing number of times to solve the original problem!
It is true that NP-complete problems "map" to each other. In fact, this is part of their definition: an NP-complete problem is an NP problem that can map to any other NP problem. Essentially, NP-complete problems are the "hardest" problems of the NP problems. (And quickly, a problem is NP if given a solution and a "proof" to the problem, the "proof" can be verified in polynomial time. This loosely implies that if you can try all perspective solutions simultaneously, you can solve the problem in polynomial time, but if you have to try all possible solutions consecutively, it could take a while.)
The article does mention that this problem is "like" NP-complete problems, but does not suggest any reason for this except for the presumed requirement of exponential time (which by the way is not necessarily a requirement for NP-completeness... this is in fact one of the outstanding questions in computer science).
To get back to your original question (does an approximation algorithm for this approximate other NP-complete problems)... let's assume that the decision version of this problem is NP-complete. Then an approximation is more of a guess (with one-sided error) about the answer to the yes/no version. In this case, you have an approximator (with one-sided error) for all NP-complete problems. But this might not really provide an efficient or even correct solution for any corresponding non-decision problem.
Finally, approximators for the travelling salesman problem do already exist. Not surprisingly, the more reliable and accurate the approximation algorithm, the more time it requires.
I hope this clarifies things...
Thou shalt not begin a subject line or post with the word "Umm".
Say you have a process in which some sort of radioactive decay generates pairs of photons, and you have a bunch of detectors. The thing you want to measure is P(theta) -- the probability that a pair of photons are emitted at the angle theta. Something like an OGR would be used to arrange your detectors to get the maximum amount of data.
Of course what I described uses a circular array, not a linear array, but the idea is the same.
Fundamentally, a lot of science is measuring power in signals as a function of frequency. If you take a finite series of measurements, the frequencies that you can detect are basically those whose wavelength is 1/N the seperation between two detectors. The more different seperations you have, the more frequencies you can detect, and the better you can reconstruct the signal.
Briefly (probably too briefly) this and similar sounding challenges have real world applications in optimization, where you are trying to figure out how to get what you need without it costing any more than necessary.
For example, suppose you needed to do something that involved two things that had to be the right distance apart, which might mean physical distance, or two oscillators on different frequencies, or two voltages, or whatever. Just two things separated by some value.
You could get pairs separated by 1,2,3,4, etc. by just having one thing (telescope, oscillator, electrode, etc.) located at values 0,1,2,3,4, etc. But suppose each of those things cost you $10 million and you had a $50 million budget. You could still lay them out at 0,1,2,3, and 4, but is there another layout where your $50 million could buy you more bang for the buck?
How could you lay out 5 things to have the maximum number of different gaps between any pair? And this problem adds another constraint, which is to make the total distance from the least value to the greatest value as small as possible. There are real world problems where that's a constraint, too, such as buying the land on which to situate telescopes.
Once problems like this are tackled and optimal solutions found using just numbers, then somebody who later comes along with a practical problem who has heard about this work can take advantage of this work to optimize his system.
"Those who have never entered upon scientific pursuits know not a tithe of the poetry by which they are surrounded."
That would be an approximation algorithm. There are in fact approximation algorithms for the traveling salesman problem. The simplest one yields a tour no more than twice the length of the optimal tour. There is a better ones that gives a tour no more than 3/2 times the length of the optimal tour though and you can get a better approximation for some special cases.
There is a lot of effort going into finding approximation algorithms. Some problems seem to be harder to find good approximations for than others, but it's not possible to take an approximation from one NP-complete problem to generate an approximation for all other NP-complete problems.
The reason for this is that formally, NP-complete problems are phrased as decision problems. A decision problem basically amounts to "Does this data have the X property?" For the traveling salesman problem you would phrase the decision problem as "Does this weighted graph have a tour visiting each vertex of weight less than N?" The mapping between two NP-complete problems is a mapping for the data that each problem takes as input. This mapping does not provide you with a mapping between near-optimal solutions to one problem and near-optimal solutions to another. Furthermore, some NP-complete problems can only be phrased as a decision problem. For these problems, there are no near-optimal solutions; for all data, the answer is either yes or no.
But despite that, yes approximation algorithms really are a big deal and private companies are giving grants to people working on commercially applicable ones. Right now I'd say that the study of approximation algorithms and probabilistic algorithms (i.e. algorithms that yield a correct answer most of the time) are where we're seeing the most development in computer science.
My only political goal is to see to it that no political party achieves its goals.
It allows you to measure: 1,3,4,5,8,9,2,7,10,11
You cannot measure six because no two distance markings differ by six.
?-|||-----x<*))))><
Imagine that a 'mark' consists of a honkin' huge radio telescope dish. Different distances between dishes equates (I think!) to inferometry at different wavelengths.
So, build a hundred dishes, or 13? (the smallest OGR over 100 has 13 marks, and measures 106).