Skip to main content
Notice removed Authoritative reference needed by CommunityBot
Bounty Ended with no winning answer by CommunityBot
Notice added Authoritative reference needed by lchen
Bounty Started worth 50 reputation by lchen
added 66 characters in body
Source Link
lchen
  • 367
  • 4
  • 12

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 we transform this problem be cast to thea known problem of maximizing? $\min_{1\le j\le n} \sum_{a_i\in S_j} a_i$(2) Given its NP-hardness, how to design approximation algorithms with constant approximation factor?

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$. Can we transform this problem to the problem of maximizing $\min_{1\le j\le n} \sum_{a_i\in S_j} a_i$?

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?

Source Link
lchen
  • 367
  • 4
  • 12
Loading