A maximization problem « Idiot String Theories

A maximization problem

By Randall J. Elzinga

Suppose that $\sum_{i=1}^m s_i=s$ and $\sum_{i=1}^n t_i=t$ for some $m\leq n$ . What is

$\max_{\pi\in \Pi} \sum_{i=1}^m s_it_{\pi(i)},$

where $\Pi$ is the set of functions from $[m]$ to $[n]$ $([m]=\{1,\ldots,m\})?$

That is, if two sets of numbers (possibly multisets) sum to numbers $s$ and $t$ , what is the maximum sum of products of pairs of numbers, where each pair contains exactly one element from each set?

Is the question different if we restrict to the case where $s_i$ and $t_j$ are integral for all $i$ and $j$ ?

This entry was posted on 2007 June 19 at 3:35 pm and is filed under Maximization. You can follow any responses to this entry through the RSS 2.0 feed. You can leave a response, or trackback from your own site.

Idiot String Theories

A maximization problem

Leave a Reply