Earthquake location estimates suffer from two types of errors: (1) systematic offsets caused by large scale earth structure, and (2) scatter of locations of different earthquakes relative to each other. I show that relative location errors are controlled by four separate error terms: (1) scatter caused by random, measurement error; (2) nonlinear effects; (3) mislocations caused by interaction of errors in modeling travel times with variations in the number and quality of arrivals recorded by different events; and (4) mislocations caused by variations in how errors in modeling travel times vary with position inside the real Earth. The first can be handled by conventional statistical methods. The second can be bounded using a second-order approximation, provided one can provide a reasonable estimate for an upper bound on the total spatial error that might be present in the location estimate. I demonstrate that the size of each of the two error terms related to inadequate knowledge of the Earth's velocity structure can be bounded provided we can determine an upper bound on travel-time errors as a function of distance. I describe an empirical approach for determining such a bound using differences between the sum of squared residuals of earthquakes located with all available data and the same event located with a single arrival deleted. This calculation is repeated for all arrivals and used to construct an upper bound on travel-time errors as a function of distance. The concepts developed are applied to bound errors in locations of earthquakes in the Garm region of central Asia, and they demonstrate the utility of these ideas in sorting out events with minimal relative error.