2
$\begingroup$

Consider some tuple $x = (x_1, ..., x_k) \in \mathbb{N}^k$ of $k$ non-negative integers such that $x_1 > x_1 > ... > x_k$ and suppose that $A \subset \mathbb{N}^k$ is such that there exists a fixed $n \in \mathbb{N}$ with the property that $a_1 + ... +a_k = n$ for all $a \in A$.

Is there an efficient method/algorithm to find an $a \in A$ which maximizes the quantity $\langle x, a \rangle = x_1a_1 + ... + x_ka_k$?

EDIT: So after reading Robert Israel's answer and comments, it seems that the problem is not very feasible without additional constraints. Here are two additional assumptions I would be willing to accept. The first concerns $x$.

  • Let's assume that $x$ is of the form $x = (x_1, x_1 - 1, x_1 - 2, ..., x_1 - (k-1))$

The second concerns the set $A$, although I'm not sure it will be of much use. Define $A(n) = \{a \in \mathbb{N}^k: a_1 + ... + a_k = n\}$. The point of the question is to design an algorithm which enumerates the members of $A(n)$ as $a_1, ..., a_m$ in such a way that $\langle x, a_i \rangle \geq \langle x, a_j \rangle$ if $i < j$. The idea then is to

  1. Find an element $a$ which maximizes $\langle x, a \rangle$

  2. Write this element down and remove if from the set

  3. Repeat steps 1 and 2 until all the elements have been removed

So I guess what this tell us about $A$ in the original question is that it is not completely arbitrary, but chosen in such a way that if $a \in A$ and $\langle x, a \rangle = l$ then $A$ contains all elements $b \in A(n)$ such that $\langle x, b \rangle \le l$.

As has been pointed out, in some cases the maximizing element is obvious. For example, at the first step, the maximizing element will always be $(n, 0, ..., 0)$.

  • 0
    @RobertIsrael I've edited some more information into the post. Is there any chance these additional assumptions about $x$ and $A$ make solving the problem more realistic?2012-09-06

1 Answers 1

3

If you just want to maximize $x_1 a_1 + \ldots + x_k a_k$ subject to $a_1 + \ldots + a_k = n$, all $a_i \in \mathbb N$ (which for convenience I'll assume includes $0$), then the solution is rather obvious: just take $a_1 = n$, $a_i = 0$ otherwise. If there are other linear constraints on $a_1, \ldots, a_n$, what you have is an integer linear programming problem, which may or may not be difficult to solve (in general it's NP-complete). If there are nonlinear constraints, it's nonlinear integer programming.