Skip to main content

Transforming an optimization problem to maxmin formulation

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?

lchen
  • 367
  • 4
  • 12