2
$\begingroup$

I am designing a feature recommendation system and I have encountered an algorithmic problem and I am wondering if any of you know if there are known algorithms to solve this type of issue. In our recommendation system the content recommended can have in its metadata information at what range it should be put. To demonstrate:

  • Items 1-2 can be put in slots 3-5

  • Items 3-4 can be put in slot 7-9

  • Item 5 can be put in slot 1

  • We are composing 9 element list which (based on content performance) may look like this: [5, 6, 2, 8, 1, 7, 3, 4, 9]

Implementation of this problem has a lot of corner cases (like ranges overlapping and content from 1 range takes the position from another range, thus making the whole result invalid). Do any of you know if there are some algorithms to handle this type of issue?

It would be best if the algorithm had time complexity lower than O(n^2)

Thanks a lot!

Improve this question
$\endgroup$
3
  • 2
    $\begingroup$ I don't understand your problem. What is the input, and what is the required output? $\endgroup$ – Yuval Filmus May 27 '20 at 11:24
  • $\begingroup$ Will it always be possible to fit all items? If not then do you have some type of priority for items or ranges? It sounds like the slot is like a priority, so do you want to work from slot 1 up? For example, if you have a list with 10 slots and 15 items, is it more important to put item 5 in slot 1 and skip item 3 or 4 because they have to be in slots 7-9? $\endgroup$ – Jason Goemaat May 27 '20 at 17:42
  • $\begingroup$ I don't understand what you mean by "We are composing 9 element list". I understand there are constraints on what items can be put in what slots, but what is the task? What do you want the output of the algorithm to be? Please edit the question to make it clearer what you are asking. Thank you! $\endgroup$ – D.W.♦ May 28 '20 at 4:25
5
$\begingroup$

Here is my guess at your problem.

There are a bunch of items that you need to place in a vector.

Each item has a set of allowed positions in the vector.

You need to find an assignment of items to positions in the vector.

This is an instance of bipartite maximum matching. On one side you have the items, on the other you have the positions in the vector. You add an edge if the item can be put in the position. A maximum matching is one that puts each item in an allowed position, without collisions.

Improve this answer
$\endgroup$
1
  • $\begingroup$ Exactly, thank you very much! $\endgroup$ – novy1234 May 27 '20 at 14:30
4
$\begingroup$

This answer presents two algorithms. The first uses flow network. The second, a faster algorithm, takes advantage of "ranges".

This problem can be solved using a unit capacity flow network (and Dinic's algorithm).

In order to transform the problem into a unit capacity flow network problem, we need to do the following:

  1. Make a node $v_i$ for every item $i$.
  2. Make a node $w_j$ for every position in the list $j$.
  3. Add an edge $e = (v_i,w_j)$ if item $i$ is allowed to go into position $j$.
  4. Add two nodes $s,t$ such that for every $i$, there is an edge $(s, v_i)$, and for every $j$, there is an edge $(w_j,t)$.
  5. All edges have capacity $1$.

The final graph is a unit capacity graph, and running Dinic's algorithm on it will return a max flow solution.

The max flow solution can be converted back to a solution of the original problem, by placing item i in slot j if there is flow between vi and wj.

Note: This algorithm will take $O(n^2)$ to convert to a flow network, and in the worst case Dinic's algorithm will take $O(n^{2.5})$, so the overall the time complexity is $O(n^{2.5})$.

Note: this algorithm misses a full proof to its correctness. please complete it if you manage to prove it

I noticed that you specifically use ranges and we could take advantage of that fact.

The algorithm:

  1. Sort all of the given ranges by their length (which means that $[5,6]$ comes before $[3,9]$ for example). let that sorted list be called R
  2. For every range $[i,j]$ in R:
    1. Find the first empty slot between i and j, and place the corresponding item there. if no empty slot was found, return NO_SOLUTION

Complexity analysis: Sorting takes $O(n\log n)$ time, and iterating through R takes $O(n)$, but every iteration can take (W.C) up to $O(n)$.

Overall $O(n\log n) + O(n^2) = O(n^2)$

Truth proof: let us split the proof to soundness and completeness:

soundness (if algorithm returns something, it is valid): pretty obvious since it only places items at legal free spots, thus if it will return something - its going to be correct.

completeness (if there is a solution, the algorithm will not return NO_SOLUTION): MISSING

Improve this answer
$\endgroup$
3
  • 1
    $\begingroup$ Welcome to Computer Science! You can use MathJax to format mathematics. See this tutorial. $\endgroup$ – Yuval Filmus May 27 '20 at 14:34
  • $\begingroup$ Thank you very much! $\endgroup$ – nir shahar May 27 '20 at 14:36
  • $\begingroup$ I have just noticed a problem in my second algorithm. When i will have time i will post a fixed version of it $\endgroup$ – nir shahar May 27 '20 at 23:19
1
$\begingroup$

Since you have ranges, I would first go by range. As a feature recommendation system I'm guessing that things in lower slots are more important. I would arrange the ranges with items that belong there sorted by lowest slot, then highest slot. I assume the items you don't list can go anywhere, so you would have these ranges:

  • Range A - Low: 1, High: 1, Items: 5
  • Range B - Low: 1, High: 9, Items: 6, 7, 8, 9
  • Range C - Low: 3, High: 5, Items: 1, 2
  • Range D - Low: 7, High: 9, Items: 3, 4

Then start picking items from the first range. When you pick an item, it could do away with an entire range, or adjust the starting number of a range and cause a re-order if inside that range. Here's the steps I see:

  1. Need an item for slot 1, pick the first range in our list (A) and take item 5. That's the last item, so remove range A. The next range low we need to worry about is 3, so no re-arranging:

    • Range B - Low: 1, High: 9, Items: 6, 7, 8, 9
    • Range C - Low: 3, High: 5, Items: 1, 2
    • Range D - Low: 7, High: 9, Items: 3, 4

  2. For slot 2 we need to pick an item, the only range available is Range B, so take 6 and remove it from Range B

    • Range B - Low: 1, High: 9, Items: 7, 8, 9
    • Range C - Low: 3, High: 5, Items: 1, 2
    • Range D - Low: 7, High: 9, Items: 3, 4

  3. For slot 3 we have a new range available, Range C. Since range C has a lower maximum slot than range B, we re-arrange to put range C first:

    • Range C - Low: 3, High: 5, Items: 1, 2
    • Range B - Low: 3, High: 9, Items: 7, 8, 9
    • Range D - Low: 7, High: 9, Items: 3, 4

And we take Item 1 from range C for slot 3 and remove it:

  • Range C - Low: 3, High: 5, Items: 2
  • Range B - Low: 3, High: 9, Items: 7, 8, 9

  • Range D - Low: 7, High: 9, Items: 3, 4

    1. for slot 4 we have no new ranges available, so keep taking from range C, which will take item 2 and remove range C:

  • Range B - Low: 3, High: 9, Items: 7, 8, 9

  • Range D - Low: 7, High: 9, Items: 3, 4

    1. The We can't add from range D until we get to slot 7, so keep taking items from range B and take and remove items 7 and 8 for slots 5 and 6:

  • Range B - Low: 3, High: 9, Items: 9

  • Range D - Low: 7, High: 9, Items: 3, 4

    1. Now at slot 7 we have a new range available, Range D. However since it's maximum slot is the same as range B, there's no need to re-order. We can finish off taking item 9 and removing range B, then taking items 3 and 4 from range D.

If the High of range B had been 10 and it had another item, we would have re-arranged putting D first because it had a lower maximum slot.

Improve this answer
$\endgroup$

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.