The Probabilistic Minimum Spanning Tree, Part II: Probabilistic Analysis and Asymptotic Results
In this paper, which is a sequel to [3], we perform probabilistic analysis under the random Euclidean and the random length models of the probabilistic minimum spanning tree (PMST) problem and the two re-optimization strategies, in which we find the MST or the Steiner tree respectively among the poi...
| Main Author: | |
|---|---|
| Format: | Working Paper |
| Language: | en_US |
| Published: |
Massachusetts Institute of Technology, Operations Research Center
2004
|
| Online Access: | http://hdl.handle.net/1721.1/5284 |
| _version_ | 1826196709028397056 |
|---|---|
| author | Bertsimas, Dimitris J. |
| author_facet | Bertsimas, Dimitris J. |
| author_sort | Bertsimas, Dimitris J. |
| collection | MIT |
| description | In this paper, which is a sequel to [3], we perform probabilistic analysis under the random Euclidean and the random length models of the probabilistic minimum spanning tree (PMST) problem and the two re-optimization strategies, in which we find the MST or the Steiner tree respectively among the points that are present at a particular instance. Under the random Euclidean model we prove that with probability 1, as the number of points goes to infinity, the expected length of the PMST is the same with the expectation of the MST re-optimization strategy and within a constant of the Steiner re-optimization strategy. In the random length model, using a result of Frieze [6], we prove that with probability 1 the expected length of the PMST is asymptotically smaller than the expectation of the MST re-optimization strategy. These results add evidence that a priori strategies may offer a useful and practical method for resolving combinatorial optimization problems on modified instances. Key words: Probabilistic analysis, combinatorial optimization, minimum spanning tree, Steiner tree. |
| first_indexed | 2024-09-23T10:36:07Z |
| format | Working Paper |
| id | mit-1721.1/5284 |
| institution | Massachusetts Institute of Technology |
| language | en_US |
| last_indexed | 2024-09-23T10:36:07Z |
| publishDate | 2004 |
| publisher | Massachusetts Institute of Technology, Operations Research Center |
| record_format | dspace |
| spelling | mit-1721.1/52842019-04-12T08:07:38Z The Probabilistic Minimum Spanning Tree, Part II: Probabilistic Analysis and Asymptotic Results Bertsimas, Dimitris J. In this paper, which is a sequel to [3], we perform probabilistic analysis under the random Euclidean and the random length models of the probabilistic minimum spanning tree (PMST) problem and the two re-optimization strategies, in which we find the MST or the Steiner tree respectively among the points that are present at a particular instance. Under the random Euclidean model we prove that with probability 1, as the number of points goes to infinity, the expected length of the PMST is the same with the expectation of the MST re-optimization strategy and within a constant of the Steiner re-optimization strategy. In the random length model, using a result of Frieze [6], we prove that with probability 1 the expected length of the PMST is asymptotically smaller than the expectation of the MST re-optimization strategy. These results add evidence that a priori strategies may offer a useful and practical method for resolving combinatorial optimization problems on modified instances. Key words: Probabilistic analysis, combinatorial optimization, minimum spanning tree, Steiner tree. 2004-05-28T19:31:39Z 2004-05-28T19:31:39Z 1988-08 Working Paper http://hdl.handle.net/1721.1/5284 en_US Operations Research Center Working Paper;OR 184-88 1744 bytes 1000827 bytes application/pdf application/pdf Massachusetts Institute of Technology, Operations Research Center |
| spellingShingle | Bertsimas, Dimitris J. The Probabilistic Minimum Spanning Tree, Part II: Probabilistic Analysis and Asymptotic Results |
| title | The Probabilistic Minimum Spanning Tree, Part II: Probabilistic Analysis and Asymptotic Results |
| title_full | The Probabilistic Minimum Spanning Tree, Part II: Probabilistic Analysis and Asymptotic Results |
| title_fullStr | The Probabilistic Minimum Spanning Tree, Part II: Probabilistic Analysis and Asymptotic Results |
| title_full_unstemmed | The Probabilistic Minimum Spanning Tree, Part II: Probabilistic Analysis and Asymptotic Results |
| title_short | The Probabilistic Minimum Spanning Tree, Part II: Probabilistic Analysis and Asymptotic Results |
| title_sort | probabilistic minimum spanning tree part ii probabilistic analysis and asymptotic results |
| url | http://hdl.handle.net/1721.1/5284 |
| work_keys_str_mv | AT bertsimasdimitrisj theprobabilisticminimumspanningtreepartiiprobabilisticanalysisandasymptoticresults AT bertsimasdimitrisj probabilisticminimumspanningtreepartiiprobabilisticanalysisandasymptoticresults |