Toward a 6/5 bound for the minimum cost 2-edge connected subgraph problem

Publication date: 17 October 2016

Abstract: Given a complete graph

K_{n} = (V, E)

with non-negative edge costs

c i n {m a t h b b R}^{E}

, the problem

2 E C

is that of finding a 2-edge connected spanning multi-subgraph of

K_{n}

of minimum cost. The integrality gap

a l p h a e x t 2 E C

of the linear programming relaxation

e x t {2 E C}^{e x t L P}

for

2 E C

has been conjectured to be

f r a c 65

, although currently we only know that

f r a c 65 l e q a l p h a e x t 2 E C l e q f r a c 32

. In this paper, we explore the idea of using the structure of solutions for

e x t {2 E C}^{e x t L P}

and the concept of convex combination to obtain improved bounds for

a l p h a e x t 2 E C

. We focus our efforts on a family

J

of half-integer solutions that appear to give the largest integrality gap for

e x t {2 E C}^{e x t L P}

. We successfully show that the conjecture

a l p h a e x t 2 E C = f r a c 65

is true for any cost functions optimized by some

x^{*} i n J

.

Recommendations

Cites Work

Cited In (4)

This page was built for publication: Toward a 6/5 bound for the minimum cost 2-edge connected subgraph problem