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 的大作中提到】
: 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 的大作中提到】
: 这个可以变成一个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 的大作中提到】
: 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 (冰糖葫芦_爱可不可以永远幸福没有悲伤) 的大作中提到: 】
|
