2:00-2:25 Santosh Vempala, MIT & Georgia Tech

KLAUS AUDITORIUM ROOM 1443

Title: CORE-DENSE GRAPHS AND HYPERGRAPHS

Abstract: Core-dense graphs are a common generalization of dense graphs
and metrics. We discuss their motivation, definition and extension to
hypergraphs. The class of maximum constraint satisfaction problems with r
literals per constraint (MAX-r-CSP) corresponding to core-dense
hypergraphs has a polynomial-time approximation scheme. This unifies and
extends classes of CSP's known to have PTAS's. Our main tools are a
method for low-rank tensor approximation and a simple scaling. The
algorithm also applies to problems with a constant number of additional
global constraints, e.g., maximum weighted bisection.
This is joint work with W. Fernandez de la Vega, R. Kannan and M.
Karpinski.