0
$\begingroup$

Assume I have a set of items $A$ and each item $a \in A$ has a score $s(a)$. Also, each two items $a_1,a_2 \in A$ have variety score $var(a_1,a_2)$ which tells how different they are.

I want to optimize over these two values (say with equal weights) to find $k$ items that have both high scores and large variety (to avoid almost-repetitive items). That is, to solve the following optimization problem:

$$\arg\max_{a_1,...,a_k\in A}{(\sum_{i=1}^{k} s(a_i) + \sum_{1 \le i<j\le k} var(a_i, a_j)})$$

  1. Is this problem NP-hard?
  2. If not, can you provide a polynomial time algorithm that solves it?
  3. If yes, can you provide a polynomial time approximation algorithm that approximately solves it?
Improve this question
$\endgroup$
4
  • $\begingroup$ You can find the median using randomized-select store $var(a_i, a_{median})$ in a copy of an array, then partition the obtained array using randomized-partition around $(len[A] - k)^{th}$ order statistic. Then take all values greater than $k$ (the ones on the right). Provided I understood the requirement properly, this is $O(n)$ time algorithm, so definitely in $NP$. $\endgroup$
    – wvxvw
    May 5, 2016 at 13:11
  • $\begingroup$ @wvxvw, median of what? median of the scores? Of the variety values? How does your procedure take into account both the score and the variety values? I don't understand why your proposed algorithm is correct (also, I don't understand what exactly the proposal is, because I'm not sure what it means to partiaion around $i$ order statistic). Would you like to write an answer, with more detail? $\endgroup$
    – D.W. ♦
    May 5, 2016 at 17:29
  • $\begingroup$ @D.W. median of scores. Partitioning around k'th order statistic means: find the element that in the sorted array would be in the position k, call it e. Choose this element as a pivot, so that all elements smaller than e would be on the left, and all greater than e would be on the right. I'll write example code in an hour. What I'm not sure about is what is the result set. My solution assumes that we are looking for the subset containing pairs of the most distant elements, but they aren't necessary far from each other, they are only the farthest elements from some other element in this set. $\endgroup$
    – wvxvw
    May 5, 2016 at 17:51
  • $\begingroup$ Take a look at farthest-point first clustering; it might be a useful heuristic that could be adapted for this problem. $\endgroup$
    – D.W. ♦
    May 5, 2016 at 18:04

1 Answer 1

Reset to default
1
$\begingroup$

Your problem is NP-hard, when $k$ is part of the input. Let $G=(V,E)$ be an undirected graph. If we set all the scores to zero and $\text{var}(u,v)$ to 1 if $(u,v) \in E$ and 0 otherwise, your problem is equivalent to asking whether $G$ contains a clique of size $k$. This is a NP-hard problem.

If we set all the scores to zero and allow the variety values to be arbitrary, your problem is equivalent to the maximum edge-weighted clique problem (MEWCP), which has been studied in the literature. For instance, you can use quadratic programming or ILP to look for solutions; these can take exponential time in the worst case, but might be useful in practice if the number of items is not too large.

Obviously, when we take into account that scores can be non-zero, the problem only gets harder. You might be able to adapt methods for MEWCP to your problem, or express your problem directly as an ILP or QP.

Improve this answer
$\endgroup$
1
  • $\begingroup$ In fact, the problem is W1-hard under parameter-preserving reductions for the same reason, so an algorithm for the problem whose runtime is not ​ max$\hspace{-0.02 in}\big(\hspace{-0.03 in}$n$^Ω$$^{(k)}\hspace{-0.03 in}$,2$^Ω$$^{(n)}\hspace{-0.03 in}\big)$ ​ would hugely improve the runtime of algorithms for O(1)-SAT. ​ ​ ​ ​ $\endgroup$
    – user12859
    May 5, 2016 at 18:25

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.