Finding top k which are the most different from each other

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?
• 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$. – wvxvw May 5 '16 at 13:11
• @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? – D.W. May 5 '16 at 17:29
• @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. – wvxvw May 5 '16 at 17:51
• Take a look at farthest-point first clustering; it might be a useful heuristic that could be adapted for this problem. – D.W. May 5 '16 at 18:04

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.
• 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. ​ ​ ​ ​ – user12859 May 5 '16 at 18:25