s*******y 发帖数: 558 | 1 Given n points and an integer k, how to find k point out of these n
points, such that the sum of the pairwise distances of these k points
are the maximal?
I guess this is an NP-hard problem. Are there any approximation algorithms
in the literature with error analysis?
thanks |
A*******r 发帖数: 768 | 2 这个可以变成一个0-1 quadratic programming
【在 s*******y 的大作中提到】![](/moin_static193/solenoid/img/up.png) : Given n points and an integer k, how to find k point out of these n : points, such that the sum of the pairwise distances of these k points : are the maximal? : I guess this is an NP-hard problem. Are there any approximation algorithms : in the literature with error analysis? : thanks
|
s*******y 发帖数: 558 | 3 请问怎么变?
谢谢了
【在 A*******r 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 这个可以变成一个0-1 quadratic programming
|
A*******r 发帖数: 768 | 4 max 1/2 x^T Q x
s.t e^T x = k
x \in \{0,1\}^n
where Q =(q_{ij}) with q_{ij} = the distance b/w i and j
For more details, google
pseudo Boolean optimization.
【
在 starrysky (冰糖葫芦_爱可不可以永远幸福没有悲伤) 的大作中提到: 】 |
s*******y 发帖数: 558 | 5 oh 非常感谢
【在 A*******r 的大作中提到】![](/moin_static193/solenoid/img/up.png) : max 1/2 x^T Q x : s.t e^T x = k : x \in \{0,1\}^n : where Q =(q_{ij}) with q_{ij} = the distance b/w i and j : For more details, google : pseudo Boolean optimization. : 【 : 在 starrysky (冰糖葫芦_爱可不可以永远幸福没有悲伤) 的大作中提到: 】
|