| dc.contributor.advisor |
Boyd, Sylvia, |
en |
| dc.contributor.author |
Wu, Xiaolin. |
en |
| dc.date.accessioned |
2009-03-25T19:59:50Z |
|
| dc.date.available |
2009-03-25T19:59:50Z |
|
| dc.date.created |
1994 |
en |
| dc.date.issued |
2009-03-25T19:59:50Z |
|
| dc.identifier.citation |
Source: Masters Abstracts International, Volume: 33-05, page: 1583. |
en |
| dc.identifier.isbn |
9780315960077 |
en |
| dc.identifier.uri |
http://hdl.handle.net/10393/9917 |
|
| 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. |
en |
| dc.format.extent |
87 p. |
en |
| dc.publisher |
University of Ottawa (Canada). |
en |
| dc.subject.classification |
Engineering, System Science. |
en |
| dc.title |
A polyhedral approach to designing communication networks. |
en |
| dc.type |
M.Sc.Thesis (M.Sc.)--University of Ottawa (Canada), 1994. |
en |
