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?
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?
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.