Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

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.

share|improve this question
add comment

1 Answer 1

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.

share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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