liveBook · Manning

Approximation

As explained in Timeless Algorithms, The Foundational Ideas

Approximation is a technique for obtaining a tractable solution by accepting some deviation from an exact result.

When a dynamic programming problem becomes too large for an exact solution, approximation sacrifices some exactness to keep computation tractable. The formulation may remain valid even when its state space exceeds practical computational limits. section 6.7.1

State-space growth can come from adding independent constraints or representing a variable in finer detail. For example, tracking inventory in single-unit increments creates more states than tracking it in increments of ten. Aggregating states is one way to reduce the burden, though it gives up some exactness. section 6.7.1

How Timeless Algorithms, The Foundational Ideas covers it

How deep it goes
Explains why state spaces grow and names aggregation as an option, but does not detail approximation procedures.
Examples
Contrasts inventory states measured in single units with states measured in increments of ten.
How it connects
Links approximation to dynamic programming, state spaces, and the curse of dimensionality.

Also explained in

Compare how 2 books explain approximation →

Related concepts

This explainer was generated by Manning's knowledge graph from the text of Timeless Algorithms, The Foundational Ideas. The section links point to the parts of the book it draws on.