Radiation Hybrid Mapping (RHM) is a technique used to order a set of markers on a genome and estimating physical distances between them. RHM provides information on marker placement independent from other methods such as sequencing, and can therefore be used for example in genome sequencing to help ordering contigs. A radiation hybrid framework can be constructed by choosing a set of markers so that the chromosome coverage is good and so that the markers can be ordered with high confidence. Automatically constructing RHM frameworks is a computationally challenging problem.