Multiplexing PCR, an approximation combinatorial algorithm for an $NP-$complete problem

The Polymerase Chain Reaction, PCR for short, is able to amplify DNA segments several millions times. The main drawbacks of the method, its relative cost and the time necessary to perform a complete amplification, are particularly important when considering cancer therapy, where tens of PCR are often necessary for one patient. Grouping (multiplexing) PCR in few experiments would allow to decrease the costs and to save time. Starting from a biological model for the multiplexing conditions, we transform the problem to a combinatorial one, show that the problem is $NP-$complete, give an approximation algorithm, and show its quasi-optimality.