billycalc

TSP Lower Bound

Calculate TSP Lower Bound instantly with the exact formula and a worked example.

TSP Lower Bound

Minimum spanning tree weight W(MST)
Length of a tour you found (heuristic), 0 = none
Lower bound on the optimal tour length
100
OPT ≥ W(MST): removing one edge turns the tour into a spanning path, which weighs no less than the minimum spanning tree (non-negative weights)With the triangle inequality, walking the tree gives a tour ≤ 2·W(MST) and Christofides' algorithm gives ≤ 1.5·OPT; a tighter lower bound comes from Held–Karp 1-treesCalculate TSP Lower Bound instantly with the exact formula and a worked example.
Upper bound (tree walk, with the triangle inequality)
200
Your tour is worse than the optimum by at most
30%

More about: TSP Lower Bound

What it calculates

The “TSP Lower Bound” calculator computes Lower bound on the optimal tour length from 2 parameters: minimum spanning tree weight w(mst), length of a tour you found (heuristic), 0 = none.

Standard IT calculations for developers and sysadmins.

Example calculation

With parameters Minimum spanning tree weight W(MST) = 100, Length of a tour you found (heuristic), 0 = none = 130 the result is 100 (OPT ≥ W(MST): removing one edge turns the tour into a spanning path, which weighs no less than the minimum spanning tree (non-negative weights)).

How to use

  1. Enter minimum spanning tree weight w(mst) and length of a tour you found (heuristic), 0 = none — each field above is adjustable with a slider.
  2. Lower bound on the optimal tour length is calculated automatically as you type.
  3. Check the worked example below to see the formula applied to real numbers.
  4. Copy the result or bookmark this calculator.

Related calculators

FAQ

How is TSP Lower Bound calculated?
The TSP Lower Bound calculator computes Lower bound on the optimal tour length from minimum spanning tree weight w(mst), length of a tour you found (heuristic), 0 = none. Enter your values above and the exact formula is applied instantly; a worked example with real numbers is shown below.
Is the TSP Lower Bound calculator free?
Yes. It is completely free, needs no signup, runs entirely in your browser, and sends no data to any server.

More calculators in this category

Explore related free tools

3D Filament Cost3D Print Cost (DIY)Game Drop Rate ProbabilityEXP Required to LevelFalling Ball VelocityGame FPS RequiredBig-O ComplexityBinary Search StepsMargin/Padding (auto)Vigenère CipherPokemon CPMagic the Gathering Mana