Monitoring the Comprehensive Nuclear-Test-Ban Treaty will require improved seismic location capability for small-magnitude events. The International Monitoring System (IMS) is well suited to locate events that are large enough to be recorded at teleseismic distances. However, small events are likely to be recorded on a sparse subset of IMS stations at regional- to upper-mantle distances (less than 30°), and sparse-network locations can be strongly effected by travel-time errors that result from path-specific velocity model inaccuracies. In an effort to improve sparse network location capability, we outline a procedure that applies empirical corrections to travel times determined with an appropriate velocity model. More specifically, Bayesian kriging and calibration events (constrained with a global network) are used to estimate epicenter-specific travel-time corrections. For a test (sparse) network of stations, we calculate travel-time residuals for the calibration events relative to the ak135 velocity model. Travel-time residuals are assigned to the respective calibration epicenter, forming a set of spatially varying travel-time correction points. The spatial set of correction points is declustered to reduce the dimension of the observations with minimal reduction in accuracy of the travel-time corrections. We then use the declustered set of calibration points and Bayesian kriging to form continuous travel-time correction surfaces for each station of the test network. The effectiveness of travel-time correction surfaces is evaluated by locating, with and without corrections, a subset of the 1991 Racha earthquake sequence (Caucasus Mountains), for which we have accurate locations that were independently determined with a dense local network. When no travel-time correction is applied, the mean horizontal distance between the local and test network locations is 42 km, and there is a distinct bias in sparse-network locations toward the north-northwest. The mean difference between local and sparse network locations is cut to 13 km when corrections are applied, and the bias in location is significantly reduced. When calibration events in the Racha vicinity are not used to make the correction surfaces, there is still a significant improvement in location, with mean mislocations of 15 km. When corrections are not applied, only one of the locally determined locations lies within the associated 90% coverage ellipse determined with the test (sparse) network. However, by using travel-time corrections and estimates of model uncertainty determined using kriging, representative error ellipses are obtained. This study demonstrates that kriging correction surfaces based on global-network-constrained calibration events can improve the ability to accurately locate lower magnitude events while providing representative coverage ellipses.