Turnpike Problem: Difference between revisions

From Algorithm Wiki
Jump to navigation Jump to search
No edit summary
No edit summary
Line 28: Line 28:
[[File:Turnpike Problem - Space.png|1000px]]
[[File:Turnpike Problem - Space.png|1000px]]


== Pareto Frontier Improvements Graph ==  
== Time-Space Tradeoff ==  


[[File:Turnpike Problem - Pareto Frontier.png|1000px]]
[[File:Turnpike Problem - Pareto Frontier.png|1000px]]

Revision as of 14:47, 15 February 2023

Description

Given $n$ points and $\binom{n}{2}$ distances, find each distance's corresponding pair of points.

Parameters

n: number of points

Table of Algorithms

Name Year Time Space Approximation Factor Model Reference
Outside-In algorithm 1991 $O({2}^n nlogn)$ $O(n)$ Exact Deterministic

Time Complexity Graph

Error creating thumbnail: Unable to save thumbnail to destination

Space Complexity Graph

Error creating thumbnail: Unable to save thumbnail to destination

Time-Space Tradeoff

Error creating thumbnail: Unable to save thumbnail to destination

References/Citation

http://hariharan-ramesh.com/ppts/turnpike.pdf