On 2Connected Subgraphs
Adrian Vetta
MIT
March 29,
4:15pm
refreshments at 3:45pm
2338
ABSTRACT

The task of finding small spanning graphs of a prescribed connectivity
is a fundamental problem in network optimization. Unfortunately, it is
also a hard probem. I will present a 4/3approximation algorithm
for the Minimum 2Edge Connected Subgraph problem in undirected graphs.
This result verifies one implication of the well known "4/3Conjecture"
regarding the subtour relaxation for the Travelling Salesman Problem.
Our main tools are techniques from matching theory and a decomposition
theorem that allows us to focus upon relatively simple graphs.
For directed graphs I will outline an approximation algorithm for the
Minimum Strongly Connected Subgraph problem with a 3/2approximation
guarantee. These factors improve upon the previously best known
values (1.42 and 1.61 resp.). This is work with Santosh Vempala.

Speaker's Contact Info: avetta(atsign)math.mit.edu
Return to seminar home page
Page loaded on February 18, 2000 at 03:23 PM.

Copyright © 199899, Sara C. Billey.
All rights reserved.

