CODEWITHSUNDEEP
arraysalgorithm
xan
xan

Reputation: 1053

Segment packing algorithm

I came up with an interesting (I think) problem and can't find a solution. Is this NP-Complete maybe (like some other packing problems)? If so, how would the reduction go?

We are given an array 1..n with some elements occupied and list of lengths of segments. The question is, can we pack those segments into this array so that no segments overlap with each other and occupied elements?

Example, array: |_ _ _ _ x _ _ _ _ _ _| (x - occupied, and the underscore means it's free) and lengths: 3, 3, 4. The answer in this case is YES, because in fact we have two containers in this array: 4, 6 and we can pack first two segments in container with capacity 6 and the last one to the first container.

Upvotes: 2

Views: 285

Answers (1)

sascha
sascha

Reputation: 33532

Let's try to formulate the reduction with the partition-problem as base-problem.

Partition-problem

The partition problem is the task of deciding whether a given multiset S of positive integers can be partitioned into two subsets S1 and S2 such that the sum of the numbers in S1 equals the sum of the numbers in S2. (from wiki-link above).

Example:

  • Given S = {3,1,1,2,2,1}
  • Valid solution to the partition problem is the two sets S1 = {1,1,1,2} and S2 = {2,3}
  • Both sets sum to 5, and they partition S.

Reduction

  • Given: a partition-problem instance like S = {3,1,1,2,2,1}
  • Sum up the values: n = sum(X)
  • Create the array |+++...x***...| where |+| = n/2; |*| = n/2 (cardinalities)
    • |+++++x*****| (the gap acts as class-split)
  • Add the segments equal to the integer-sizes
    • segments = {###, #, #, ##, ##, #}
  • Solve the problem with some algorithm for the problem above
    • Valid solution: |### # # x ## ## #| (white-space only introduced for visualization) This reduction is doable in polynomial-time (and it's clear that the original problem is in NP). This means, the original problem is NP-complete.

Upvotes: 5

Related Questions