0
votes
0answers
136 views

k-means type clustering of binary data, under capacity constraints per cluster. Proof of NP-hardness?

Suppose you are given a set of $I$ binary vectors in ${\mathbb R}^N$, a number of clusters $k$, and positive integers $\{ c_i \}_{i=1}^k$ where $\sum_{i=1}^k c_i = I$. I am interested in finding a ...
2
votes
1answer
195 views

Does Quadratic Programming get easier when it's described by a diagonal matrix?

Generally, Quadratic Programming solves the problem $$\text{Given }Q, c, A, b,\text{ choose }x \text{ to maximize } x^TQx + c^Tx \text{ subject to } Ax \le b$$ In this form, Quadratic Programming is ...