Does w equal to 1 require an optimal solution?

Under the multiplicative minimization definition, yes, assuming a feasible optimum and the stated guarantee conditions.

Must the optimum be computed first?

No. Valid lower bounds can support certification without finding the optimum itself.

Does the bound cover safety or fairness?

Only insofar as the model and constraints represent the relevant requirements; a cost ratio alone does not establish them.

AI Glossary / Graphs and symbolic AI / Intermediate

Bounded suboptimal search

Definition

Bounded suboptimal search seeks a feasible solution whose cost is guaranteed to stay within a specified amount of the optimal cost. In the common multiplicative form, a factor w of at least 1 requires the returned cost to be no more than w times the optimum. The aim is to obtain an acceptable solution faster than proving exact optimality.

What it means

A search algorithm may spend considerable effort establishing that its best solution cannot be improved. Some applications can tolerate a controlled cost increase in exchange for a quicker answer. Bounded suboptimal search makes that tolerance explicit rather than simply returning whichever solution appears first.
For a minimization problem, a factor of 1.10 permits at most 10 percent above the true optimal cost, provided the algorithm's assumptions hold. It does not mean the result is usually 10 percent worse, or that the program runs 10 percent faster. The bound concerns the modeled solution cost, not every aspect of operational performance.

How it works

The algorithm explores states while maintaining information that justifies its cost guarantee. A common ingredient is an admissible lower bound: an estimate that does not exceed the best achievable cost. Search can favor promising or quickly reachable solutions while retaining a separate mechanism for checking whether a candidate meets the required bound.
For example, if L is a valid lower bound on the optimum and a feasible solution has cost C no greater than wL, then C is also no greater than w times the optimum. Particular algorithms differ in how they select states, maintain bounds, handle repeated states, and decide when to terminate. Their guarantees depend on those details.

Three practical examples

A route planner allows a small, specified increase in modeled travel cost to reduce the effort required to find a route.
A puzzle solver seeks a solution within a stated factor of the minimum number of moves instead of always proving the shortest solution.
A planning system accepts a controlled increase in total action cost while preserving all hard feasibility requirements.

Think of it this way

Think of accepting a delivery quote only when you can justify that it lies within an agreed margin of the cheapest feasible quote. The analogy captures the cost margin. In actual search, the algorithm often does not know the cheapest complete solution; it relies on mathematically justified bounds. An informal belief that a quote seems reasonable is not the same guarantee.

Worked example

Suppose a fictional search problem has optimal cost 100, although the searcher does not initially know this. With w equal to 1.20, any returned solution costing at most 120 meets the required relative bound.
During the search, a valid lower bound L is 90 and a feasible candidate costs 108. Since 1.20 times 90 equals 108, the candidate can be certified using that lower bound. A candidate costing 115 also happens to satisfy the true 120 limit, but the same L of 90 does not yet certify it through this test. The search would need stronger evidence or a cheaper candidate. If the lower bound rises to 96, then 1.20 times 96 equals 115.2, which certifies 115. This distinction matters: meeting a bound in hindsight and proving it during search are different tasks.

Illustrative case study

At fictional Pine Route Labs, developers compare an exact route solver with a bounded suboptimal alternative. They define the cost measure, retain vehicle and access restrictions as hard constraints, and select a tolerable cost factor for evaluation.
Their report records solution cost, computation time, and whether the guarantee was established before the deadline. An interrupted run is not automatically labeled certified. The fictional case illustrates how to communicate a controlled approximation without claiming measured speed gains or treating a cost allowance as permission to violate route restrictions.

Common misconceptions and mistakes

A bounded suboptimal algorithm need not be faster on every instance. Its guarantee normally concerns solution quality; runtime still depends on the problem and implementation. An arbitrary heuristic search is not bounded suboptimal merely because its answers look close to optimal.
An absolute cost ceiling is also different from a relative bound: staying below 200 says nothing about closeness when the optimum is 20. Some formulations use additive error instead of a multiplier, so identify the convention. Finally, the guarantee applies to the encoded costs and constraints. Incorrect travel times or missing restrictions can make a mathematically certified route unsuitable in practice.

Business use

Businesses can use this framework when exact optimization is costly and the value of a slightly better solution is limited. A useful specification names the objective, permitted factor or additive gap, assumptions, and behavior on timeout. Evaluation should report the time needed to obtain a certified result separately from the time to produce an initial feasible result. This makes the tradeoff understandable to people who must act on the recommendation.

Check your understanding

A route costs 140 and the required factor is 1.10. A valid lower bound is 100. Does that lower bound certify the route?

Answer: No. The test permits at most 110. More evidence or a better route is required.

Related terms

Heuristic search
Admissible heuristic
Bounded cost search
weighted A-star
lower bound
approximation algorithm
optimality gap

Learn next

Compare a relative cost guarantee with an absolute budget on three hypothetical optimum values. Then practice certifying candidate solutions from lower bounds. Keep the cost of the returned solution, the evidence for the guarantee, and the search runtime as three separate quantities.

Sources

Sources: Fickert, Gu, and Ruml, New Results in Bounded-Suboptimal Search, original research: https://ojs.aaai.org/index.php/AAAI/article/view/21256 . Thayer and Ruml, Bounded Suboptimal Search: A Direct Approach Using Inadmissible Estimates, author materials: https://www.cs.unh.edu/~ruml/papers/ees-ijcai-11-talk.pdf . Thayer and colleagues, bounded-cost search research: https://www.cs.unh.edu/~ruml/papers/bees-icaps-12.pdf .

Previous: Bounded rationality Next: Bounding box