输出集合A的子集以使其最大化成对的总和的算法

假设我有一套A={a_1, a_2, ..., a_n}.我还有一个f:AxA->R从A某个实际值中分配一对的函数.我想提取一个子集S_k的大小k 从A以使其最大程度地提高所有元素的整体成对总和S_k

是否有任何已知的算法可以在合理的时间内完成此操作？多项式/准多项式时间也许？

编辑:工作示例

假设A={a_1,a_2,a_3,a_4}with k=3和f定义为:

f(a_1,a_2)=0,f(a_1,a_3)=0,f(a_1,a_4)=0,f(a_2,a_3)=1,f(a_2,a_4)=5,f(a_3,a_4)=10.

然后,S_k={a_2,a_3,a_4}因为它最大化总和f(a_2,a_3)+f(a_2,a_4)+f(a_3,a_4).(即S_k中所有元素的成对总和)

不太可能 - 这个问题概括了找到k-clique(将权重设置为图的邻接矩阵)的问题,其中最着名的算法是指数的(参见强指数时间假设).