2
$\begingroup$

Inspired by this StackOverflow question, I am wondering if there is an efficient algorithm for the following problem:

Assume $n$ items and $n$ boxes, with all boxes numbered numerically and all items labelled alphabetically. Each item has a disallow list: there are certain boxes that item cannot be put into. Generate a mapping of items to boxes that does not violate any item's disallow list.

For bonus points, I would be interested in being able to generate all such mappings.


At first blush, the problem appears to be the inverse of the stable marriage problem, in that everyone has a strict list (rather than an ordinal ranking) of whom they don't want to get married to but will settle for anyone else (and strictly speaking the men/boxes have no preferences). Edit: it appears this problem is closer to bipartite matching.

A very naive solution is to simply generate all permutations and check which ones don't violate any disallow lists, but this grows as $O(n!)$. Are there any polynomial time solutions out there?

$\endgroup$
3
$\begingroup$

This actually has nothing to do with the stable marriage problem; it's an instance of bipartite matching. (It's not related to stable marriage, becuase you don't have an ordering on the preferences of which box each item is matched to; you just have a list of what's allowed or disallowed.)

There are efficient algorithms: use the Hungarian algorithm, or any other algorithm for finding a maximum matching in a bipartite graph. See https://en.wikipedia.org/wiki/Bipartite_matching#In_unweighted_bipartite_graphs, https://en.wikipedia.org/wiki/Hungarian_algorithm, and https://en.wikipedia.org/wiki/Assignment_problem.

$\endgroup$

Your Answer

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

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