Find maximum number of arrays whose sum is less than a given array

Question

Given an array x of length n, and a set of arrays S such that each array in S has length n, find a maximal size set of arrays G in S such that for all 1 <= i <= n, x[i] >= sum(g[i]) for all g in G.

e.x. if x = [3, 3] and S = {[3, 0], [1, 1], [2, 1]}, then the best set is {[1, 1], [2, 1]} because the sum is [3, 2] and the element at each index is less than the corresponding element in x. {[3, 0], [1, 1]} does not work because the sum is [4, 1], and 4 > x[0] = 3.

Is there an algorithm whose run time is polynomial in n and |S|?

Background/Context: This question arose from a question on scrabble. Given a list of tiles, and a word, can you form the word with the tiles? I extended it to given a list of tiles, and a list of words, what is the maximum number of words in the list that can be formed from the tiles?

This is multi-dimensional knapsack problem. It allows a pseudo-polynomial time algorithm only for fixed n. — Evgeny Kluev
– Evgeny Kluev, Commented Oct 17, 2012 at 19:41
The number of partitions of 9 (or whatever the number of owned tiles is) isn't that much. I'd go with brute-force. — John Dvorak
– John Dvorak, Commented Oct 17, 2012 at 19:59
Also see liv.ac.uk COMP202's NP-complete item 43 (Garey and Johnson's SP10) that may be equivalent — James Waldby - jwpat7
– James Waldby - jwpat7, Commented Oct 17, 2012 at 20:40

Evgeny Kluev · Accepted Answer · 2012-10-18 10:13:35Z

3

This is multi-dimensional knapsack problem.

To prove that there is no algorithm, polynomial-time in both n and |S| (or to prove that this is a Strongly NP-hard problem), simplify this problem, allowing only values 1 for array x and values 0 or 1 for arrays S. After this simplification we get exactly the optimization version of Set packing, which is a classical NP-complete problem.

Relation to set packing problem suggests that there is also no good approximation algorithm.

This leaves pretty limited choice of algorithms:

Branch-and-bound.
Integer linear programming.
Metaheuristic algorithms like Simulated annealing or Tabu search.

edited Oct 18, 2012 at 10:13

answered Oct 17, 2012 at 22:14

Evgeny Kluev

24.7k7 gold badges58 silver badges100 bronze badges

Sign up to request clarification or add additional context in comments.

Collectives™ on Stack Overflow

Find maximum number of arrays whose sum is less than a given array

1 Answer 1

Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

Comments

Your Answer

Sign up or log in

Post as a guest

Related