Algorithm to solve a maximization problem

[mathlete]

I have two sets of vectors:

A: a₁, a₂, a₃... a_n
B: b₁, b₂, b₃... b_m

n > m and n/m is an integer, p.

Each vector b_i has ranked, in order of preference, a set of vectors from A. For example, b₁ may "prefer" a₁, a₉, and a₁₀. The only constraint on this set is that each vector a_i from A appears only p total times across all these ranked sets.

The problem is to find the set of vectors, C, such that:

C_i = a_i\sum b_k

where:

- The sum of b_k is a sum of p vectors from B that listed a_i as a preferred vector
- No vector C_j would increase in value by substituting in b_k, where j is a value listed in b's preferences about i. Using the example of b₁ above, if b₁ was in C₁₀, you could not switch it to C₉ and increase its value (since 9 is ranked above 10).

The last condition is the one that's giving me a problem. This seems close to, but not exactly, a maximization problem.

Simple example (too simple because each b vector lists all c vectors as preferences which makes it somewhat trivial to solve, but gives an idea of what I'm trying to do):

a₁ = { 1, 2, 1 }
a₂ = { 2, 1, 2 }

b₁ = { 5, 1, 2} Lists preferences as: a2, a1
b₂ = { 1, 5, 2} Lists preferences as: a1, a2
b₃ = { 8, 0, 6} Lists preferences as: a2, a1
b₄ = { 0, 9, 0} Lists preferences as: a2, a1

Answer: c1: a1 paired with b1 and b3; c2: a2 paired with b2 and b4

 

[Stephen Tashi]

I don't understand your example since I don't see any a's listed in the example In the problem description you said each vector b listed a set of a' s that it preferred. But in the example, each b listed c's that it preferred.


Is it true that the lists of preferences for each the b_i contain the same number of elements?

 

[mathlete]

Sorry, you're right -- I fixed the example. And yes, each b vector has the same number of preferences listed, but we don't necessarily know how many (though we can assume it's > p and < n).

 

[Stephen Tashi]

The example doesn't explain the meaning of C_i = a_i \sum b_k
That formula seems to involve multiplying two vectors together. Is it supposed to be an inner product?

 

[mathlete]

Bad notation on my part. It's shorthand for the inner product, yes: a_i*b_{k_1}+a_i*b_{k_2} + ... + a_i*b_{k_p} where the b_k are chosen as stated above.

 

[Stephen Tashi]

What does it mean to say "no vector C_j would increase"? Are you talking about the length of C_j ? -- that would be the square root of the sum of the squares of its components.