A polyhedral approach to designing communication networks.
| dc.contributor.advisor | Boyd, Sylvia, | |
| dc.contributor.author | Wu, Xiaolin. | |
| dc.date.accessioned | 2009-03-25T19:59:50Z | |
| dc.date.available | 2009-03-25T19:59:50Z | |
| dc.date.created | 1994 | |
| dc.date.issued | 1994 | |
| dc.degree.level | Masters | |
| dc.degree.name | M.Sc. | |
| dc.description.abstract | Polytopes $Q\sbsp{2E}{n}$ and $Q\sbsp{2N}{n}$, which are associated with the minimum cost 2-edge-connected subgraph problem and the minimum cost 2-node-connected subgraph problem, respectively, are studied in this thesis, and some new classes of facet-inducing inequalities are introduced for these polytopes. These classes of inequalities are related to the so-called clique tree inequalities for the travelling salesman polytope ($Q\sbsp{T}{n}$), and the relationships between $Q\sbsp{T}{n}$ and $Q\sbsp{2E}{n}, Q\sbsp{2N}{n}$ are exploited in obtaining these new classes of facets. Due to the use of problem specific facet-inducing inequalities instead of dominant cutting-planes, the linear programming cutting-plane method has proven to be quite successful for solving some NP-hard combinatorial optimization problems. We believe that our new classes of facet-inducing inequalities can be used to further improve the cutting-plane procedure for designing minimum cost survivable communication networks. | |
| dc.format.extent | 87 p. | |
| dc.identifier.citation | Source: Masters Abstracts International, Volume: 33-05, page: 1583. | |
| dc.identifier.isbn | 9780315960077 | |
| dc.identifier.uri | http://hdl.handle.net/10393/9917 | |
| dc.identifier.uri | http://dx.doi.org/10.20381/ruor-8034 | |
| dc.publisher | University of Ottawa (Canada) | |
| dc.subject.classification | Engineering, System Science. | |
| dc.title | A polyhedral approach to designing communication networks. | |
| dc.type | Thesis |
Files
Original bundle
1 - 1 of 1
