A network flow approach to the minimum common integer partition problem (Q861289)

From MaRDI portal
scientific article
Language Label Description Also known as
English
A network flow approach to the minimum common integer partition problem
scientific article

    Statements

    A network flow approach to the minimum common integer partition problem (English)
    0 references
    0 references
    0 references
    0 references
    9 January 2007
    0 references
    In the \(k\)-Minimum Common Integer Partition Problem, abbreviated as \(k\)-MCIP, we are given \(k\) multisets \(X_1,\dots,X_k\) of positive integers, the goal is to find an integer multiset \(T\) of the minimum size such that for every \(i\), we can partition each of the integers in \(X_i\) so that the disjoint (multiset) union of their partitions equals \(T\). This problem has applications in computational molecular biology, in particular, ortholog assignment and DNA hybridization fingerprint assembly. The problem is known to be NP-hard for any \(k\geq 2\). In this article, we improve the approximation ratio for \(k\)-MCIP by viewing this problem as a flow decomposition problem in some flow network. We show an efficient 0.5625\(k\)-approximation algorithm, improving upon the previously best known 0.6139\(k\)-approximation algorithm for this problem.
    0 references
    minimum common integer partition
    0 references
    approximation algorithm
    0 references
    network flow
    0 references

    Identifiers