Cube versus Torus Models for Combinatorial Optimization Problems and the Euclidean Minimum Spanning Tree Constant
For a sample of points drawn uniformly from either the d-dimensional torus or the d-cube, d > 2, we define a class of random processes with the property of being asymptotically equivalent in expectation in the two models. Examples include the traveling salesman problem (TSP), the minimum spanning...
| 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/5196 |
| _version_ | 1826213196475662336 |
|---|---|
| author | Jaillet, Patrick |
| author_facet | Jaillet, Patrick |
| author_sort | Jaillet, Patrick |
| collection | MIT |
| description | For a sample of points drawn uniformly from either the d-dimensional torus or the d-cube, d > 2, we define a class of random processes with the property of being asymptotically equivalent in expectation in the two models. Examples include the traveling salesman problem (TSP), the minimum spanning tree problem (MST), etc. Application of this result helps closing down one open question: We prove that the analytical expression recently obtained by Avram and Bertsimas for the MST constant in the d-torus model is in fact valid for the traditional d-cube model. For the MST, we also extend our result and show that stronger equivalences hold. Finally we present some remarks on the possible use of the d-torus model for exploring rates of convergence for the TSP in the square. |
| first_indexed | 2024-09-23T15:44:50Z |
| format | Working Paper |
| id | mit-1721.1/5196 |
| institution | Massachusetts Institute of Technology |
| language | en_US |
| last_indexed | 2024-09-23T15:44:50Z |
| publishDate | 2004 |
| publisher | Massachusetts Institute of Technology, Operations Research Center |
| record_format | dspace |
| spelling | mit-1721.1/51962019-04-12T08:06:59Z Cube versus Torus Models for Combinatorial Optimization Problems and the Euclidean Minimum Spanning Tree Constant Jaillet, Patrick For a sample of points drawn uniformly from either the d-dimensional torus or the d-cube, d > 2, we define a class of random processes with the property of being asymptotically equivalent in expectation in the two models. Examples include the traveling salesman problem (TSP), the minimum spanning tree problem (MST), etc. Application of this result helps closing down one open question: We prove that the analytical expression recently obtained by Avram and Bertsimas for the MST constant in the d-torus model is in fact valid for the traditional d-cube model. For the MST, we also extend our result and show that stronger equivalences hold. Finally we present some remarks on the possible use of the d-torus model for exploring rates of convergence for the TSP in the square. 2004-05-28T19:27:31Z 2004-05-28T19:27:31Z 1990-11 Working Paper http://hdl.handle.net/1721.1/5196 en_US Operations Research Center Working Paper;OR 234-90 1172143 bytes application/pdf application/pdf Massachusetts Institute of Technology, Operations Research Center |
| spellingShingle | Jaillet, Patrick Cube versus Torus Models for Combinatorial Optimization Problems and the Euclidean Minimum Spanning Tree Constant |
| title | Cube versus Torus Models for Combinatorial Optimization Problems and the Euclidean Minimum Spanning Tree Constant |
| title_full | Cube versus Torus Models for Combinatorial Optimization Problems and the Euclidean Minimum Spanning Tree Constant |
| title_fullStr | Cube versus Torus Models for Combinatorial Optimization Problems and the Euclidean Minimum Spanning Tree Constant |
| title_full_unstemmed | Cube versus Torus Models for Combinatorial Optimization Problems and the Euclidean Minimum Spanning Tree Constant |
| title_short | Cube versus Torus Models for Combinatorial Optimization Problems and the Euclidean Minimum Spanning Tree Constant |
| title_sort | cube versus torus models for combinatorial optimization problems and the euclidean minimum spanning tree constant |
| url | http://hdl.handle.net/1721.1/5196 |
| work_keys_str_mv | AT jailletpatrick cubeversustorusmodelsforcombinatorialoptimizationproblemsandtheeuclideanminimumspanningtreeconstant |