Sylvia Boyd

Some Selected Publications


(NOTE: A link to my page listing vertices of the Subtour Elimination Polytope can be found here.)

 

1.     Boyd, S., Legault, P. (May, 2015), Toward a 6/5 bound for the minimum cost 2-edge connected subgraph problem

 

2.     Boyd, S., Fu, Y., Sun, Y. (October 2014), A 5/4-approximation for subcubic 2EC using circulations

 

3.     Boyd, S., Sitters, R., van der Ster, S., Stougie, L. (2014), TSP on cubic and subcubic graphs, Mathematical Programming Series A, 144, 227-245.

 

4.     Boyd, S., Iwata, S., Takazawa, K. (2013), Finding 2-factors closer to TSP in cubic graphs, SIAM Journal of Discrete Mathematics, Volume 27, Issue 2, 918-939.

 

5.     Boyd, S., Haghighi, M. (2013), Mixed and circular multichromosomal breakpoint median problem, SIAM Journal of Discrete Mathematics, Volume 27, Issue 1, 63-74.

 

6.     Boyd, S., Haghighi, M. (2012), A fast method for large-scale multichromosomal breakpoint median problems, J. of Bioinformatics and Computational Biology, 10 (1), 1-19.

 

7.     Boyd, S., Carr, R. (2011), Finding low cost TSP and 2-matching solutions using certain half-integer subtour vertices, Discrete Optimization, Vol. 8 (4), 525-539.

 

8.     Haghighi, M., Boyd, S. (2011), A fast method for large-scale multichromosomal breakpoint median problems, Proceedings of the ACM Conference on Bioinformatics, Computational Biology and Biomedicine, August 2011, Chicago (9 pages).

 

9.     Boyd, S., Sitters, R., van der Ster, S., Stougie, L. (2011), TSP on cubic and subcubic graphs, In: O. Gnlk and G.J. Woeginger, editors, Integer Programming and Combinatorial Optimization, 15th International Conference, IPCO 2011, 6655 in Lecture Notes in Computer Science, Springer, Berlin, 65-77.

 

10.  Boyd, S., Elliott-Magwood, P. (2010), Structure of the Extreme Points of the Subtour Elimination Problem of the STSP, In: S. Iwata, editor, Combinatorial Optimization and Discrete Algorithms, RIMS Kkyroku Bessatsu B23, Kyoto University, Kyoto, Japan, 33-47.

 

11.  Boyd, S., Pulleyblank, W.R. (2009), Facet generating techniques. In: W. Cook, L. Lovasz, J. Vygen, editors, Research Trends in Combinatorial Optimization, Springer, Berlin, Germany, 33-55.

 

12.  Benoit, G., Boyd, S. (2008), Finding the exact integrality gap for small traveling salesman problems, Mathematics of Operations Research, Volume 33, Number 4, 921-931.

13.  Boyd, S, Cockburn, S., Vella, D. (2007), On the domino-parity inequalities for the STSP, Mathematical Programming, Vol. 110-3:501-519.

 

14.  Boyd, S., Elliott-Magwood, P.J. (2005), Computing the integrality gap of the asymmetric travelling salesman problem, Electronic Notes in Discrete Mathematics, Volume 19, Elsevier, 241-247.

 

15.  Boyd, S., Carr, R. (1999), A new bound for the ratio between the 2-matching problem and its linear programming relaxation, Mathematical Programming, Ser. A 86: 499-514.

 

Technical Reports:

 

16.  Boyd, S., Cameron, A. (2011), The vital core connectivity problem, Technical Report TR-2011-01, School of EECS, University of Ottawa, Ottawa, Canada, 38 pages.

 

17.  Boyd, S., Cameron, A. (2009), Integrality gap and approximation algorithm for the multi-survivable network design problem, Technical Report TR-2009-03, SITE, University of Ottawa, Ottawa, Canada, 25 pages.

 

18.  Boyd, S., Elliott-Magwood, P. (2007), The cobasis structure of the extreme points of the SEP polytope, Technical Report TR-2007-06, SITE, University of Ottawa, Ottawa, Canada, 13 pages.

 

19.  Boyd, S., Elliott-Magwood, P. (2007), Feasibility of the Held-Karp LP relaxation of the TSP, Technical Report TR 2007-07, SITE, University of Ottawa, Ottawa, Canada, 7 pages.

 

20.  Boyd, S., Elliott-Magwood, P. (2007), Operations for generating SEP extreme points, Technical Report TR-2007-08, SITE, University of Ottawa, Ottawa, Canada, 16 pages.

 

21.  Alexander, T., Boyd, S., Elliott-Magwood, P. (2006), On the Integrality Gap of the 2-Edge Connected Subgraph Problem, Technical Report TR-2006-04, SITE, University of Ottawa, Ottawa, Canada, 12 pages.

 

22.  Boyd, S., Cockburn, S. (2001), A family of facet-inducing domino-parity inequalities for the STSP, Technical Report TR-2001-09, SITE, University of Ottawa, Ottawa, Canada.

 

My thesis (from long ago!)

 

Boyd, S. (1986), The Subtour Polytope of the Travelling Salesman Problem, PhD Thesis, University of Waterloo,

Waterloo, Canada.