Let's say I have a finite set S with, say, 1000 elements, and a function f on some subset of S. Suppose that f has no useful mathematical properties.

What algorithm is most relevant in finding the subset of S that maximizes f?

  • 1
    $\begingroup$ No useful properties? Then nothing's gonna work. You have to search the entire space. And $f$ is not monotonic, superadditive, zero-sum? Submodular, perhaps? $\endgroup$ – Pål GD Aug 1 '13 at 0:06
  • $\begingroup$ I agree that you need to tell us more if you want to have any hope of finding a useful solution. Why don't you tell us about where this problem arose? What's the context? What's the function? Perhaps some domain knowledge will help narrow this down and establish some properties of $f$ that enable faster search. $\endgroup$ – D.W. Aug 1 '13 at 6:17
  • $\begingroup$ What is the range of function $f$. Is it the real numbers or natural numbers or what? What exactly do you mean by "no useful mathematical properties". This would suggest that it is not a function at all. Maybe a bit of information might help for a probabilistic approach to the problem. $\endgroup$ – swarnim_narayan Aug 2 '13 at 10:49

The algorithm that iterates through every $2^{1000}$ subsets. Sorry, but stated like this, the answer is that there is no solution.

For every algorithm you come up with, I can come up with a subset $T \subseteq S$ such that $T$ is the last of all sets to be tested, and be the max of $f$.

| cite | improve this answer | |
  • 2
    $\begingroup$ On the upside, the algorithm is $\mathcal{O}(1)$! ;) $\endgroup$ – Luke Mathieson Aug 1 '13 at 4:06

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.