Resource Allocation Problem Solving Algorithm

Question

Hi, I am creating a program in which students sign up for an exam, which is held in several cities across the country. While signing students provide a list of three cities where they would like to take the exam in the order of their preference. Thus, the student can say that his first preference for the examination center is New York, then Chicago, then Boston.

Now, bearing in mind that since exam centers have limited capacity, they cannot accommodate each student of their first choice. However, we will try to provide as many students as possible, either their first or second choice of centers, and, as far as possible, to avoid students having a third center of choice for the student

Now any ideas for the sorting algorithm that would facilitate this process were more effective. An easy way to do this would be to first go through the list of students' first choice in order to select as many as possible, and then list the list of second options and highlight. However, this can lead to students who are first on the list to receive their first center, and last students to receive their third choice or worse none of their choices. All that could make it more efficient

Answer 1

It sounds like a variant of the classic problem of stable marriage or college problems with admission . Wikipedia lists linear time (among preferences, O (n²) algorithm in the number of persons) for the first; NRMP describes an efficient algorithm for the latter.

I suspect that if you randomly generate student test room preferences (one Fisher-Yates shuffles to the exam site) and then apply a stable marriage algorithm, you will get a fairly fair and effective solution.

Answer 2

This problem can be formulated as an example of a minimum cost stream . Let N be the number of students. Let each student be the starting vertex with capacity 1. Let each exam center be the top of the sink with capacity, well, its capacity. Make an arc from each student to his first, second and third options. Set the value of the arcs of the first choice to 0; the cost of arcs of the second choice is up to 1; and the cost of third choice tracks to N + 1.

Find the minimum cost stream that moves N units of the stream. Assuming your solver returns an integral solution (he should, the LP stream is completely unimodular), each student transfers one unit to the center assigned to him. Costs minimize the number of appointments of the third choice, interrupting the relationship by the number of appointments of the second choice.

Answer 3

Task task

You can use the original algorithm designed for this: Hungarian algorithm

Answer 4

There is a class of algorithms that consider this distribution of limited resources called auctions. Basically, in this case, each student will receive a certain amount of money (the amount that they can spend), then your software will place bets between these students. You can use a settings-based formula.

An example is training time. If you put aside your preferences, then you will actually offer more bets for those times and less for those times that you do not need. Therefore, if you do not get your preferences, you will have more “money” to bid for other study guides.