1
$\begingroup$

I've been trying to theorize how to solve a certain type of problem for months now. Suppose you have a collection of $m$ pre-defined $(d+2)$-dimensional vectors like so:

$$(v, s, m_1, \dots, m_{d})$$

In this case $v$ represents the primary objective value, $s$ is the size of each object, each $m_i$ represents additional metadata. Also suppose we have some optimal values $m_1', \dots, m_{d}'$. The objective function is to select $k$ of these $m$ vectors to maximize

$$\sum_{i=1}^k v_i - (\overline{m_1} - m_1')^2 - (\overline{m_{d}} - m_{d}')^2$$

subject to $\sum_{i=1}^k s_i = n$. To be clear,

$$\overline{m_i} = \frac{\sum_{j=1}^k(s_j*m_{i_j})}{n}$$

In other words, the objective function is also being lowered by the squared distances between the mean of each $m_i$ selected and the "ideal" value $m_i'$. This is a special case of the knapsack problem with both an equality in place of the usual inequality and additional objective function elements. I know this is rather abstract, but is there any way to, if not find the optimal value, arrive at something close to it?

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.