5
$\begingroup$

Say, that there is a group of $n$ people who decides to share Christmas gifts. Each person has a budged, he/she will spend at most $m_i \in \mathbb{Q}$ coins on gifts. Each person must give, exactly $1\leq g\leq n-1$ gifts, and each person must receive $g$ gifts. Furthermore, the total worth $w$ of gifts received must be equal for each person. How do one maximize $w$?

Clearly, if $g=n-1$ then each person $i$ will give a gift of value $m_i/(n-1)$ to every other person. Thus, $w$ is the arithmetic mean of the $m_i$:s. However, if $g=1,$ then every person cannot give more than $\min_i m_i$ so $w=\min_i m_i$ in this case.

The case when all $m_i$ are equal is also simple, just give $g$ gifts of value $w=m_i/g$ so that everyone receives $g$ gifts, and $w$ is maximized.

However, what can be said in the general case? Is this equivalent to some known problem, like knapsack or max-flow?

As a graph-theoretical problem, one may view this as a directed 2g-regular graph, on $n$ vertices, where each vertex has out-degree g. Each vertex is a source and a sink, and one wants to maximize the flow so that all sinks receive the same amount.

$\endgroup$

1 Answer 1

10
$\begingroup$

In the graph theoretic setting, the question is analyzed by N. Megiddo in

Optimal flows in networks with multiple sources and sinks (1973) (google will give you the pdf). Gives an algorithm, does not seem to discuss complexity)

More recently this is discussed (in a more general setting) in the classic Ahuja/Mananti/Orlin, chapter 17. They do discuss complexity, but you have to hunt around a bit.

$\endgroup$

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.