Sylvia C. Boyd

activity

20112021

most citedA

4/3

-Approximation Algorithm for the Minimum

2

-Edge Connected Multisubgraph Problem in the Half-Integral Case

2 citations · 3 across the 5 of their papers we have counts for

collaborators

Showing cs.DMShow all

2 papers · 1 filter

cs.DM2017

The Salesman's Improved Tours for Fundamental Classes

Sylvia Boyd, András Sebö

Finding the exact integrality gap $α$ for the LP relaxation of the metric Travelling Salesman Problem (TSP) has been an open problem for over thirty years, with little progress mad…

cs.DM2016

Toward a 6/5 Bound for the Minimum Cost 2-Edge Connected Spanning Subgraph Problem

Sylvia Boyd, Philippe Legault

Given a complete graph $K_{n} = (V, E)$ with non-negative edge costs $c \in R^{E}$ , the problem $2 E C$ is that of finding a 2-edge connected spanning multi-subgraph of $K_{n}…