[Lowerbounds, Upperbounds]

Speaker: Shuheng Zhou
Date: Friday, May 12
Time: 2:00-3:15pm
Place: WeH 7220

Title: Edge Disjoint Paths in Moderately Connected Graphs

Abstract:

We study the Edge Disjoint Paths (EDP) problem in undirected graphs: Given a graph $G$ with $n$ nodes and a set $\T$ of pairs of terminals, connect as many terminal pairs as possible using paths that are mutually edge disjoint. This leads to a variety of classic NP-complete problems, for which approximability is not well understood.

We show a polylogarithmic approximation algorithm for the undirected EDP problem in general graphs with a moderate restriction on graph connectivity; we require the global minimum cut of $G$ to be $\Omega(\log^5 n)$. Previously, constant or polylogarithmic approximation algorithms were known for trees with parallel edges, expanders, grids and grid-like graphs, and most recently, even-degree planar graphs. These graphs either have special structure (e.g., they exclude minors) or there are large numbers of short disjoint paths. Our algorithm extends previous techniques in that it applies to graphs with high diameters and asymptotically large minors.

This is joint work with Satish Rao.

Speaker: Katrina Ligett

Time: Wednesday 12-1pm

Place: NSH 1507

Title: Truthful, Near-Optimal Mechanism Design

Abstract:

In many situations, such as auctions, one would like to compute a function on inputs held by selfish players. The players may lie to try to influence the outcome of the algorithm in their favor. Mechanism design seeks to design a pricing scheme and algorithm that incentivize truth-telling. While there exist truthful mechanisms for a wide range of settings, the underlying problem is often NP-hard, and naive attempts at applying approximation algorithms may destroy the truthfulness of a mechanism. We will discuss a general technique, presented by Lavi and Swami in FOCS 2005, for converting approximation algorithms into truthful mechanisms.