Question: Consider the following problem that we call the min-max sum problem. The input consists of a sequence A[1..n] E R of numbers, and an integer

Consider the following problem that we call the "min-max sum" problem. The input consists of a sequence A[1..n] E R of numbers, and an integer k. The goal is to partition A[1..n) into k sets S1, ..., Sk that minimizes the maximum sum over all the sets. In other words, the goal is to partition such that max; S; is minimized, where si = Lees; e is the sum of numbers in the set Si. Decide if either: (a) A polynomial time algorithm for min-max sum implies a polynomial time algorithm for SAT. (b) There is a polynomial time algorithm for min-max sum
Step by Step Solution
There are 3 Steps involved in it
Get step-by-step solutions from verified subject matter experts
