In this paper, we describe an efficient method for creating mosaics from collections of videos. Our method is based on a utility maximization formulation which we optimize greedily. We employ a function for quickly estimating mosaics without computing image features that allows us to efficiently take greedy steps while still achieving user definable goals for mosaic quality. Indeed, we demonstrate using a number of single- and multi-video experiments that our approach can construct high-quality mosaics in only a fraction of the time required to perform the operations undertaken by existing video mosaicing algorithms. While we focus in this work on the application of panorama construction, our method has a wide range of applications, such as super-resolution, summary, and indexing.