DATE: | Wednesday, January 14th |

TIME: | 4:30 PM - 5:30 PM |

PLACE: | McConnell 320 |

TITLE: | Approximating Vertex Cover on Dense Graphs |

SPEAKER: | Kazuo Iwama (Kyoto University) |

Although many problems in MAX-SNP admit a PTAS for dense graphs, that
is not the case for Vertex Cover, which is MAX-SNP hard even for dense
graphs. This paper presents a randomized approximation algorithm for
Vertex Cover on dense graphs which is probably optimal: Let
$\varepsilon=\overline{d}/\Delta$ where $\overline{d}$ and $\Delta$
are the average and maximum degrees of a given graph $G$. $G$ is said
to be dense if its $\overline{d}$ is $\Omega(n)$. (i)~Our algorithm
achieves an approximation factor of $2 -
\frac{\varepsilon}{1+\varepsilon/2}$ for dense graphs, which improves
the best-known bound by Karpinski and Zelikovsky. For example, it
approximates within a factor of 1.334 if the graph is regular. (ii)~It
achieves the same factor for a wider range of graphs, i.e., for the
graphs whose $\Delta$ is $\Omega(n\frac{\log\log n}{\log n})$.
(iii)~It is probably optimal in the sense that if we can achieve a
better approximation factor by $\delta > 0$ for the above range of
graphs, then we can achieve a factor of $2-\delta$ for general graphs.
Joint work with Tomokazu Imamura.

Direct questions, comments, additions to and removals from the mailing list, and suggestions for speakers to us at beezer at cs.mcgill.ca.

Web Address: www.cs.mcgill.ca/~beezer/Seminars/seminar99.html