A Catalog of Steinger Tress Formulations
We present some existing and some new formulations for the Steiner tree and Steiner arborescence problems. We show the equivalence of many of these formulations. In particular, we establish the equivalence between the classical bidirected dicut relaxation and two vertex weighted undirected relaxatio...
| 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/5311 |
| _version_ | 1811070738715639808 |
|---|---|
| author | Goemans, Michel X. Myung, Young-soo |
| author_facet | Goemans, Michel X. Myung, Young-soo |
| author_sort | Goemans, Michel X. |
| collection | MIT |
| description | We present some existing and some new formulations for the Steiner tree and Steiner arborescence problems. We show the equivalence of many of these formulations. In particular, we establish the equivalence between the classical bidirected dicut relaxation and two vertex weighted undirected relaxations. The motivation behind this study is a characterization of the feasible region of the dicut relaxation in the natural space corresponding to the Steiner tree problem. |
| first_indexed | 2024-09-23T08:40:28Z |
| format | Working Paper |
| id | mit-1721.1/5311 |
| institution | Massachusetts Institute of Technology |
| language | en_US |
| last_indexed | 2024-09-23T08:40:28Z |
| publishDate | 2004 |
| publisher | Massachusetts Institute of Technology, Operations Research Center |
| record_format | dspace |
| spelling | mit-1721.1/53112019-04-09T19:09:23Z A Catalog of Steinger Tress Formulations Goemans, Michel X. Myung, Young-soo We present some existing and some new formulations for the Steiner tree and Steiner arborescence problems. We show the equivalence of many of these formulations. In particular, we establish the equivalence between the classical bidirected dicut relaxation and two vertex weighted undirected relaxations. The motivation behind this study is a characterization of the feasible region of the dicut relaxation in the natural space corresponding to the Steiner tree problem. 2004-05-28T19:33:04Z 2004-05-28T19:33:04Z 1991-05 Working Paper http://hdl.handle.net/1721.1/5311 en_US Operations Research Center Working Paper;OR 252-91 1744 bytes 1129107 bytes application/pdf application/pdf Massachusetts Institute of Technology, Operations Research Center |
| spellingShingle | Goemans, Michel X. Myung, Young-soo A Catalog of Steinger Tress Formulations |
| title | A Catalog of Steinger Tress Formulations |
| title_full | A Catalog of Steinger Tress Formulations |
| title_fullStr | A Catalog of Steinger Tress Formulations |
| title_full_unstemmed | A Catalog of Steinger Tress Formulations |
| title_short | A Catalog of Steinger Tress Formulations |
| title_sort | catalog of steinger tress formulations |
| url | http://hdl.handle.net/1721.1/5311 |
| work_keys_str_mv | AT goemansmichelx acatalogofsteingertressformulations AT myungyoungsoo acatalogofsteingertressformulations AT goemansmichelx catalogofsteingertressformulations AT myungyoungsoo catalogofsteingertressformulations |