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 ...
3
votes
1answer
189 views

Optimization problem - maximizing number of satisfied linear inequalities subject to a quadratic constraint

I am wondering what is known about optimization problems of the following type. Our control x is a unit vector in $\mathbb{R}^n$. We are given a finite number of linear inequalities $$Az≥b,$$ and we ...
2
votes
1answer
307 views

Maximizing supermodular functions

I have a real supermodular objective function which I want to maximize with constraint. The constraint is on the size, like |A|=k . I am wondering if anyone can give me more information about a ...