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$. –  brom 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? –  brom 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

 
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.