2

I have a set of frequency values and I'd like to find the most likely subsets of values meeting the following conditions:

  • values in each subset should be harmonically related (approximately multiples of a given value)

  • the number of subsets should be as small as possible

  • every subset should have a minimum number of missing harmonics smaller than the highest value

E.g. [1,2,3,4,10,20,30] should return [1,2,3,4] and [10,20,30] (a set with all the values is not optimal because, even if they are harmonically related, there are many missing values)

The brute force method could be to compute all the possible subsets of values in the sets and compute some cost value, but that would take way too long time.

Is there any efficient algorithm to perform this task (or something similar)?

jul
  • 36,404
  • 64
  • 191
  • 318

1 Answers1

2

I would reduce the problem to minimum set cover, which, although NP-hard, often is efficiently solvable in practice via integer programming. I'm assuming that it would be reasonable to decompose [1, 2, 3, 4, 8, 12, 16] as [1, 2, 3, 4] and [4, 8, 12, 16], with 4 repeating.

To solve set cover (well, to use stock integer-program solvers, anyway), we need to enumerate all of the maximal allowed subsets. If the fundamental (i.e., the given value) must belong to the set, then, for each frequency, we can enumerate its multiples in order until too many in a row are missing. If not, we try all pairs of frequencies, assume that their fundamental is their approximate greatest common divisor, and extend the subset downward and upward until too many frequencies are missing.

Community
  • 1
  • 1
David Eisenstat
  • 64,237
  • 7
  • 60
  • 120