Given $N=mn$ real numbers $a_i$, we seek to partition them into $n$ subsets $S_j$ ($1\le j\le n$), each containing $m$ numbers, so as to maximize $\prod_{j=1}^n \sum_{a_i\in S_j} a_i$. My questions are: (1) Can this problem be cast to a known problem? (2) Given its NP-hardness, how to design approximation algorithms with constant approximation factor?
Transforming an optimization problem to maxmin formulation
lchen
- 367
- 4
- 12