3
$\begingroup$

The real-world problem I'm trying to solve is to create an algorithm which finds the ideal channels where I can transmit radio traffic, inside a radio frequency band that could contain various disturbances. These n ideal channels are those who are furthest away from any of the disturbances, but also the furthest away from each other. Where n is a constant picked by me, depending on how many channels the radio can support.


In abstract terms, I have a chunk of generic data where each item could either be labelled "good" or "bad". It can be considered to be an array of booleans, or illustrated as a series of 1=good and 0=bad, for example 0010111100.

In this data, consecutive sequences of good data form good segments:

0010111100   data size=10
  ^ ^
  | +------- good segment 2, size 4
  +--------- good segment 1, size 1

In the best case, there only exists one good segment covering all of the data:

1111111111   data size=10, 1 good segment with size 10

No matter the nature of the data, I need to find the n "best places" that are furthest away from any bad data, but also from each other. It is considered equally bad to be near a "bad" item as it is to be near another "best place".

The ideal solution is where the minimum distance between all "best places" and bad data/other best places is as long as possible, for all best places.

For example, in the case of 1111111111 where n=3 places, they could be located as follows (simply divide the data size by 3):

1111111111   data size=10, n=3
  ^  ^  ^

Or in case of 0110111110 n=3, the following would be fine:

0110111110   data size=10, n=3
 ^   ^ ^

or

0110111110   data size=10, n=3
  ^  ^ ^

In case there is too much bad data, the problem has no solution. The sum of all good segment sizes must be at least n or there exists no solution. Example:

0000010001   data size=10, n=3, no solution possible.

I suppose one solution is to find the n best segments out of all the good segments - then simply find the n best places at the center of those segments.

But one problem then is that there aren't necessarily n good segments. In that case, the best places have to be divided across what good segments there are.

Are there any similar existing algorithms that could be used or modified to suit the above scenario?

I'm also wondering if there is a particular data structure that would beneficial to use in this case, other than a raw array? A heap binary tree consisting of good segments?

$\endgroup$
3
  • $\begingroup$ It sounds a lot like a factory location problem. $\endgroup$
    – adrianN
    Jan 3, 2017 at 12:32
  • $\begingroup$ You haven't clearly defined what counts as the best arrangement. What is the objective function you are trying to minimize/maximize? Minimize the sum of the squared distances between each pair of places? Maximize the minimum distance from any place to any other place or any bad location? Something else? Without that, the problem isn't well-defined. $\endgroup$
    – D.W.
    Jan 3, 2017 at 17:17
  • $\begingroup$ @D.W. "Maximize the minimum distance from any place to any other place or any bad location" This. I'll edit to clarify. $\endgroup$
    – Lundin
    Jan 4, 2017 at 7:55

1 Answer 1

3
$\begingroup$

I am going to assume you want to maximize the "separation". In particular, I'll say that a solution has separation $\ge s$ if every selected place is at least $s$ apart from any selected place, and if every selected place is at least $s$ away from any bad place.

Then this can be solved in $O(m \lg (m/n))$ time using binary search and a greedy algorithm, where $m = $ the data size. I'll show how to determine whether it's possible to place $n$ stations achieving separation $\ge s$, in $O(m)$ time; then you can use binary search on $s$ to find the largest $s$ achievable.

To determine whether separation $\ge s$ is achievable, just use a greedy algorithm with a left-to-right scan. Select the left-most place you can. Then, scanning left to right, select the first place that can be selected (taking into account it has to be at least $s$ to the right of the one you previously selected, and at least $s$ away from any bad place). Keep iterating. When you're done, that gives you the maximum number of places that can be selected, subject to the requirement that you have separation $\ge s$.

Now you can use binary search from here. If the number of places that could be selected was less than $n$, decrease $s$ and try again. If the number of places that could be selected was greater than or equal to $n$, increase $s$ and try again. There are at most $m/n$ possible values of $s$, so after $\lg (m/n)$ steps of binary search, this will terminate. If you start the binary search at the smallest possible value of $s$, the running time will be $O(m \lg s)$.

$\endgroup$
4
  • $\begingroup$ This sounds like it could work, but I can see one problem: when you find a place where you have a free space of exactly s to one side, but a free space of > s on the other side. This is a better place than one which has exactly s to both sides. So I suppose the algorithm has to keep track of how much free space on either side that every found place has, and then at the end of the search pick the n places which have the largest sum of free space to the left+right. This could of course be done during the iteration, by saving (up to) the n best places in a sorted container. $\endgroup$
    – Lundin
    Jan 4, 2017 at 9:17
  • 1
    $\begingroup$ @Lundin It depends on your goal. If you want to maximize the "minimum" distance between bad/selected channels, D.W.'s solution works fine and you don't need any extra effort. Even if you can find a channel with $s$ on one side and $>s$ on the other side, the solution is still optimal since we know $s+1$ doesn't work. In other word, it's not the bottleneck. If you need a tiebreaker you should formally define it. $\endgroup$
    – aaaaajack
    Jan 4, 2017 at 11:08
  • $\begingroup$ @aaaaajack The problem is that the total data size, as well as the size of a "good segment", are not necessarily divisible by s, or by n for that matter. Anyway, I suppose that if the results are off-by-one here and there is not at all critical for the purpose of the algorithm. $\endgroup$
    – Lundin
    Jan 4, 2017 at 12:53
  • $\begingroup$ @Lundin Why do you think it matters? The algorithm works well if the size is not divisible by anything. What the algorithm do is packing as many good channels as it can (possibly $>n$), while guaranteeing distance $\ge s$ at the same time. $\endgroup$
    – aaaaajack
    Jan 4, 2017 at 13:04

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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