Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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)$.

share|improve this question
Is $a_1 + \ldots + a_k = n$ the only constraint defining $A$? If there are others, are they linear constraints? –  Robert Israel Sep 6 '12 at 2:55
@RobertIsrael No, the fact that $a_1 + ... + a_k = n$ for all $a \in A$ just happens to be true for the sets I'm dealing with. It might be the case that $A$ does not contain all possible $a$ satisfying that constraint but just some of them. In particular the $a = (n, 0,...,0)$ you mention in your answer might not be in $A$. –  user38355 Sep 6 '12 at 3:43
Then you need to tell us more about $A$. –  Robert Israel Sep 6 '12 at 6:42
@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? –  user38355 Sep 6 '12 at 7:32

1 Answer 1

up vote 3 down vote accepted

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.

share|improve this answer

Your Answer


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