1
$\begingroup$

I have the following question:

Assume each student can borrow at most 10 books from the library, and the library has three copies of each title in its inventory. Each student submits a list of books he wishes to borrow. You have to assign books to students, so that a maximal number of volumes is checked out.

I was wondering whether this is a Max Flow problem? If so, should it be set out like this?

Directed acyclic graph

Would a greedy algorithm work here? Simply, pick a student and assign whatever books are applicable to him and then move on to the next?

$\endgroup$
1
$\begingroup$

Your characterization of the problem into a max flow problem seems correct to me: make a vertex for each student, a vertex for each book listed, and a source and a sink. Connect the source to each student with a capacity of 10, connect each student to his desired books with a capacity of 1, connect each book to the sink with a capacity of 3.

However, a greedy algorithm will not work for network flow problems. Here is a lecture explaining the Ford Fulkerson algorithm, and it gives an example where a greedy approach doesn't work: https://www.youtube.com/watch?v=G6-ljgmXE


An example of lists where a greedy algorithm won't work:

Student 1, 2, and 3 all ask for books 1 through 11. Student 4 only asks for books 1 throough 10.

A greedy algorithm gives students 1, 2, and 3 the first 10 books and none to the fourth so 30 books are checked out. It is possible to give the first 3 students books 2 through 11 and the fourth student book 1, which checks out 31 books.

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ How would you constrain the flows to be discrete values? $\endgroup$ – 200_success Jun 21 '14 at 3:26
  • $\begingroup$ 1, 10, and 3 are discrete values. $\endgroup$ – DanielV Jun 21 '14 at 3:28
  • $\begingroup$ The capacities are discrete, but does that necessarily result in discrete answers? $\endgroup$ – 200_success Jun 21 '14 at 3:29
  • $\begingroup$ The optimal answer will be an integer. All of the graph cuts will have integer capacities, so by the min-cut max-flow theorem the maximum flow will also be an integer. I'm working on an example where a greedy algorithm won't work btw, I believe the key is that the student can submit a list with more than 10 books. $\endgroup$ – DanielV Jun 21 '14 at 3:31
  • $\begingroup$ Found it: Integral Flow Theorem. $\endgroup$ – 200_success Jun 21 '14 at 3:56

Your Answer

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