Applications often demand we tackle problems that are too large to solve optimally. In this paper, our aim is to solve shortest-path problems as quickly as possible while guaranteeing that solution costs are bounded within a specified factor of optimal. We explore two approaches. First, we extend the approach taken by weighted A*, in which all expanded nodes are guaranteed to remain within the bound. We prove that a looser bound than weighted A*'s can be used and show how an arbitrary inadmissible heuristic can be employed. As an example, we show how temporal difference learning can learn a heuristic on-line. Second, we show how an optimistic search that expands nodes potentially outside the bound can be modified to ensure bounded solution quality. We test these methods on grid-world path-finding and temporal planning benchmarks, showing that these methods can surpass weighted A*'s performance.