UC Riverside

We introduce a new combinatorial optimization problem in this paper, called the Minimum Common Integer Partition (MCIP) problem, which was inspired by computational biology applications including ortholog assignment and DNA fingerprint assembly. A partition of a positive integer n is a multiset of positive integers that add up to exactly n, and an integer partition of a multiset S of integers is defined as the multiset union of partitions of integers in S. Given a sequence of multisets S_1,(...),S_k of integers, where k >= 2, we say that a multiset is a common integer partition if it is an integer partition of every multiset S_i, 1 = 3.