CODEWITHSUNDEEP
algorithmoptimizationcombinations
maplemaple
maplemaple

Reputation: 1715

Partition a list of positive integers into K subsets, want to minimize the maximum of subset sum?

Problem Statement:
Given a list of positve integers, the objective is to partition the list into K subsets such that the maximum sum among these subsets is minimized.

This problem can be contextualized within the realm of task scheduling. Imagine there are K identical workers and n tasks. Each task requires a specific, positive integer amount of time to complete. The objective is to find the optimal scheduling of tasks among the workers so as to minimize the maximum time any worker has to spend on their assigned tasks.

Example:
For example, consider the list [1, 2, 3, 4, 5] and K = 2. The minimum possible maximum subset sum is 8. This can be achieved through an optimal partition into the two subsets [1, 2, 5] and [3, 4].

Background:
I encountered this problem during an interview today. While I initially thought of solving it using a backtracking approach, the interviewer was looking for a more efficient solution. I am now wondering if there are more efficient algorithms for this, perhaps involving Dynamic Programming or Greedy Methods.

Upvotes: 1

Views: 123

Answers (1)

Orlando Rivera Letelier
Orlando Rivera Letelier

Reputation: 211

This problem is known as Scheduling parallel identical machines to minimize makespan (P||C_max), and it is NP-complete. This implies that there are not known efficient algorithm to solve large instances of the problem exactly. So any possible implementation you can think of is probably not gonna look too efficient (MIP formulations or SAT solvers are possible ways to do it for general NP-hard problems). There is a whole literature around ways to get solutions for these class of problems. You can use approximation algorithm or heuristics to find solutions, but with no guarantees of having the actual minimum. I don't think there is an obvious efficient implementation to solve it. You can look at this reference for more detail.

Upvotes: 2

Related Questions