most recent 30 from http://mathoverflow.net 2013-05-22T14:28:11Z http://mathoverflow.net/feeds/question/84230 http://www.creativecommons.org/licenses/by-nc/2.5/rdf http://mathoverflow.net/questions/84230/christmas-giftgiving Per Alexandersson 2011-12-24T19:29:32Z 2011-12-24T21:00:53Z

<p>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$?</p> <p>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.</p> <p>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.</p> <p>However, what can be said in the general case? Is this equivalent to some known problem, like knapsack or max-flow?</p> <p>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.</p>

http://mathoverflow.net/questions/84230/christmas-giftgiving/84237#84237 Igor Rivin 2011-12-24T21:00:53Z 2011-12-24T21:00:53Z

<p>In the graph theoretic setting, the question is analyzed by N. Megiddo in </p> <p>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)</p> <p>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.</p>