In cognitive radio networks (CRNs), dynamic spectrum access has been demonstrated as an effective way to improve the spectrum utilization. Spectrum holes can be exploited not only in certain time slots or frequency bands, but also at particular locations. In relay assisted CRNs, one relay at a certain location can help to identify and provide different spectrum holes over multiple channels. In this paper, a multi-dimensional combinatorial optimization problem is formulated for joint relay selection and channel allocation. We propose a weighted bipartite graph model and a minimum weighted assignment approach to efficiently get the optimal solution of the considered problem. Simulation results show that by applying this approach, spectrum efficiency, relay selection diversity and power efficiency can be improved simultaneously for the cognitive users. Besides, only the statistical channel state information is needed and the allocation results can be computed efficiently by using the proposed approach. © 2011 IEEE.