1
$\begingroup$

I'm searching for the generic name of an algorithm/method that would allow me to solve this type of problem efficiently.

I have a continuous line which I traverse, from one side to the other. Along that line are buckets, placed at various positions which have a given size. Along the line are also items that I have to pick up, and place in buckets. I want to optimise placing the items in the buckets to minimise the distance between items and buckets. The combined size of all buckets is always larger than the number of total items.

I cannot only use "shortest distance", because it may very well be that my bucket fills up too fast and the neighbouring items end up having to end in a bucket far away.

Is there a generic method to help me solve that kind of problem, or do you have some pointers in the right direction at least? I can find an algorithm by myself but I'd like to expand my knowledge list as well 😊.

Here is an illustration of what I mean :

--x----x-----x-----x-------x-x----x----x-x-x-x-----------x-x-x----x---->

[]2              []5          []3                 []9

In that case, what is an efficient way to place items in buckets to optimize "distance to buckets"?

Thanks!

Improve this question
$\endgroup$
4
  • 1
    $\begingroup$ On way to do this is via black box reduction to minimum cost flow (assignment problem). Create a bipartite graph with L=items and R= buckets with the usual s,t sentinel nodes. For each item and bucket, add their distance as a cost on the edge connecting them. Have a capacity on each (bucket,t) edge as the capacity of the bucket. Capacity of (s,item) and (item, bucket) would be 1. Then find a min cost flow from s to t with value=number of items. $\endgroup$
    – AspiringMat
    Aug 3 at 10:36
  • $\begingroup$ If the total number $n$ of items ($x_1, \ldots, x_n$) was equal to the total space in buckets ($s_1 + \ldots + s_k$), we could just sort the items ($x_1 < \ldots < x_n$), then place the first $s_1$ items into the first bucket, the next $s_2$ items into the second, and so on. The proof is: if we put item from the right earlier (in terms of buckets, seen left-to-right) than item from the left, swapping them would decrease the total distance, since it will remove some non-zero overlap of the two traveled segments. $\endgroup$
    – Gassa
    Aug 3 at 13:04
  • $\begingroup$ Without such equality, the problem seems harder, but still, the idea of looking at items and buckets left-to-right simultaneously can be useful. At least we can have $O (nk)$ dynamic programming perhaps. $\endgroup$
    – Gassa
    Aug 3 at 13:04
  • $\begingroup$ cs.stackexchange.com/tags/dynamic-programming/info $\endgroup$
    – D.W. ♦
    Aug 3 at 16:53

0

Reset to default

Your Answer

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

Browse other questions tagged or ask your own question.