0
$\begingroup$

I am looking for an algorithm for the following problem:

I have a set of users and a set of books.

Every user has their own set of favorite books, which may be empty, and is a subset the set of books.

We can assume that every book is a favorite book of at least one user.

Ideally I want to distribute ONE book to every user that has at least one favorite book.

A user may only receive one of its favorite books.

Sometimes it's not possible to distribute one book to every user, because there are more users than books, or because a user has no favorite books, or due to the specific details of users, books and favorite books.

One book cannot be distributed to more than one user.

Distribution A is better than distribution B if A distributes more books than B.

An "acceptable distribution" is one that follows the rules above, and cannot be improved without reallocating a book, i.e. taking a book away from a user that already got a book.

An "optimal distribution" is an acceptable distribution that distributes a maximum number of books.

I do not have a formal analysis whether this problem can be accurately solved in a polynomial time. So maybe the best polynomial-time alternative there is out there is something such as a probabilistic algorithm.

Ideally I would like to have a polynomial-time algorithm that would always find an optimal distribution.

If it's not possible to have such an algorithm, then I would like to have an alternative polynomial-time algorithm that would find an acceptable distribution that in high probability is quite close to an optimal distribution.

$\endgroup$
4
  • $\begingroup$ I suspect that some constraints are missing. The preferred books play no role other than limiting the set of recipients. In the problem as stated you can just assign the books arbitrarily to the users that have at least one preferred book (a user does not necessarily receive one of its favorite books). This distribution is does not violate any rule. Moreover, according to your definition, it is acceptable as it cannot be improved by taking away a book from a user (b.t.w. reallocating seems a weird name for such an action). Finally, it is optimal as it maximizes the number of assigned books. $\endgroup$
    – Steven
    Aug 25, 2022 at 12:08
  • $\begingroup$ To clarify, a user may only receive one of its favorite books. $\endgroup$
    – rapt
    Aug 25, 2022 at 12:14
  • $\begingroup$ You can refer to "acceptable distribution" as a synonym for valid distribution. It's supposed to avoid distributions such as "do nothing" or "stop after only distributing one book when you can easily distribute more books". I.e. even if you just naively go book after book and give it to a random user who still has none, until no books are left or you have no user who can accept one of the remaining books - this is an acceptable distribution, but it is possibly not an optimal one. $\endgroup$
    – rapt
    Aug 25, 2022 at 12:35
  • $\begingroup$ I apologize, I misread "without reallocating" as "by allocating". $\endgroup$
    – Steven
    Aug 25, 2022 at 12:51

1 Answer 1

1
$\begingroup$

Create a bipartite graph $G = (B+U, E)$, where $B$ is the set of books and $U$ is the set of users. The set $E$ contains an edge $(b,u)$ for every pair $(b,u) \in B \times U$ such that $b$ is one of the favorite books of $u$.

To find an optimal solution, you just need to find a maximum cardinality matching of $G$.

A way to do this is to modify $G$ as follows: direct the edges of $G$ towards $B$, add two new vertices $s,t$, add all edges $(s,b)$ for $b \in B$, and finally add all edges $(u,t)$ for $u \in U$. Now you can find a maximum flow $f$ between $s$ and $t$ using any polynomial-time algorithm and unitary edge capacities. An optimal matching contains all edges $(b,u) \in E$ such that $f(b,u)=1$.

$\endgroup$
1
  • $\begingroup$ Great! That's the algorithm I was looking for. Thank you! $\endgroup$
    – rapt
    Aug 25, 2022 at 13:59

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.