On 2-Connected Subgraphs
refreshments at 3:45pm
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/3-approximation algorithm
for the Minimum 2-Edge Connected Subgraph problem in undirected graphs.
This result verifies one implication of the well known "4/3-Conjecture"
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/2-approximation
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(at-sign)math.mit.edu
Return to seminar home page
Page loaded on February 18, 2000 at 03:23 PM.
Copyright © 1998-99, Sara C. Billey.
All rights reserved.