The Minimum Spanning Tree Constant in Geometrical Probability and Under the Independent Model; A Unified Approach
Given n uniformly and independently points in the d dimensional cube of unit volume, it is well established that the length of the minimum spanning tree on these n points is asymptotic to /3MsT(d)n(d-l)/d,where the constant PMST(d) depends only on the dimension d. It has been a major open problem to...
| Main Authors: | , |
|---|---|
| Format: | Working Paper |
| Language: | en_US |
| Published: |
Massachusetts Institute of Technology, Operations Research Center
2004
|
| Online Access: | http://hdl.handle.net/1721.1/5189 |
| _version_ | 1826197584986767360 |
|---|---|
| author | Avram, Florin Bertsimas, Dimitris J. |
| author_facet | Avram, Florin Bertsimas, Dimitris J. |
| author_sort | Avram, Florin |
| collection | MIT |
| description | Given n uniformly and independently points in the d dimensional cube of unit volume, it is well established that the length of the minimum spanning tree on these n points is asymptotic to /3MsT(d)n(d-l)/d,where the constant PMST(d) depends only on the dimension d. It has been a major open problem to determine the constant 3MST(d). In this paper we obtain an exact expression of the constant MST(d) as a series expansion. Truncating the expansion after a finite number of terms yields a sequence of lower bounds; the first 3 terms give a lower bound which is already very close to the empirically estimated value of the constant. Our proof technique unifies the derivation for the MST asymptotic behavior for the Euclidean and the independent model. |
| first_indexed | 2024-09-23T10:50:12Z |
| format | Working Paper |
| id | mit-1721.1/5189 |
| institution | Massachusetts Institute of Technology |
| language | en_US |
| last_indexed | 2024-09-23T10:50:12Z |
| publishDate | 2004 |
| publisher | Massachusetts Institute of Technology, Operations Research Center |
| record_format | dspace |
| spelling | mit-1721.1/51892019-04-12T13:40:45Z The Minimum Spanning Tree Constant in Geometrical Probability and Under the Independent Model; A Unified Approach Avram, Florin Bertsimas, Dimitris J. Given n uniformly and independently points in the d dimensional cube of unit volume, it is well established that the length of the minimum spanning tree on these n points is asymptotic to /3MsT(d)n(d-l)/d,where the constant PMST(d) depends only on the dimension d. It has been a major open problem to determine the constant 3MST(d). In this paper we obtain an exact expression of the constant MST(d) as a series expansion. Truncating the expansion after a finite number of terms yields a sequence of lower bounds; the first 3 terms give a lower bound which is already very close to the empirically estimated value of the constant. Our proof technique unifies the derivation for the MST asymptotic behavior for the Euclidean and the independent model. 2004-05-28T19:27:12Z 2004-05-28T19:27:12Z 1990-04 Working Paper http://hdl.handle.net/1721.1/5189 en_US Operations Research Center Working Paper;OR 211-90 828803 bytes application/pdf application/pdf Massachusetts Institute of Technology, Operations Research Center |
| spellingShingle | Avram, Florin Bertsimas, Dimitris J. The Minimum Spanning Tree Constant in Geometrical Probability and Under the Independent Model; A Unified Approach |
| title | The Minimum Spanning Tree Constant in Geometrical Probability and Under the Independent Model; A Unified Approach |
| title_full | The Minimum Spanning Tree Constant in Geometrical Probability and Under the Independent Model; A Unified Approach |
| title_fullStr | The Minimum Spanning Tree Constant in Geometrical Probability and Under the Independent Model; A Unified Approach |
| title_full_unstemmed | The Minimum Spanning Tree Constant in Geometrical Probability and Under the Independent Model; A Unified Approach |
| title_short | The Minimum Spanning Tree Constant in Geometrical Probability and Under the Independent Model; A Unified Approach |
| title_sort | minimum spanning tree constant in geometrical probability and under the independent model a unified approach |
| url | http://hdl.handle.net/1721.1/5189 |
| work_keys_str_mv | AT avramflorin theminimumspanningtreeconstantingeometricalprobabilityandundertheindependentmodelaunifiedapproach AT bertsimasdimitrisj theminimumspanningtreeconstantingeometricalprobabilityandundertheindependentmodelaunifiedapproach AT avramflorin minimumspanningtreeconstantingeometricalprobabilityandundertheindependentmodelaunifiedapproach AT bertsimasdimitrisj minimumspanningtreeconstantingeometricalprobabilityandundertheindependentmodelaunifiedapproach |