Seminar on Oct. 21, 2011

Huzhou Normal University, Huzhou

11:00 -12:00

Titile: Approximation Algorithms and Hardness of the k-Route Cut Problem

Speaker: Yuan Zhou (Carnegie Mellon University)


We study the k-route cut problem: given an undirected edge-weighted graph G=(V,E), a collection {(s_1,t_1),(s_2,t_2),...,(s_r,t_r)} of source-sink pairs, and an integer connectivity requirement k, the goal is to find a minimum-weight subset E' of edges to remove, such that the connectivity of each pair (s_i, t_i) falls below k. Specifically, in the edge-connectivity version, EC-kRC, the requirement is that there are at most (k-1) edge-disjoint paths connecting s_i to t_i in G \ E', while in the vertex-connectivity version, VC-kRC, the same requirement is for vertex-disjoint paths. Prior to our work, poly-logarithmic approximation algorithm has been known for the special case where k=2, but no non-trivial approximation algorithms were known for any value k>2, except in the single-source setting. We show an O(k log^{3/2}r)-approximation algorithm for EC-kRC with uniform edge weights, and several polylogarithmic bi-criteria approximation algorithms for EC-kRC and VC-kRC, where the connectivity requirement k is violated by a constant factor. Our results improve the previously known result for the case k=2. We also prove that VC-kRC is hard to approximate up to a factor of k^{\epsilon} for some fixed \epsilon>0.

We then turn to study a simpler version of VC-kRC, where only one source-sink pair is present. We present a simple bi-criteria approximation algorithm for this case. Then we show evidence that even this restricted version of the problem may be hard to approximate. For example, we show that the single source-sink pair version of VC-kRC has no constant-factor approximation, assuming Feige's Random k-AND assumption.

Joint work with Julia Chuzhoy, Yury Makarychev and Aravindan Vijayaraghavan.

2:00 -3:00

Titile: Mechanism Design without Money via Stable Matching

Speaker: Pinyan Lu (Microsoft Research Asia)


Mechanism design without money has a rich history in social choice literature. Due to the strong impossibility theorem by Gibbard and Satterthwaite, exploring domains in which there exist dominant strategy mechanisms is one of the central questions in the field. We propose a general framework, called the generalized packing problem (gpp ), to study the mechanism design questions without payment. The gpp possesses a rich structure and comprises a number of well-studied models as special cases, including, e.g., matroid, matching, knapsack, independent set, and the generalized assignment problem.

We adopt the agenda of approximate mechanism design where the objective is to design a truthful (or strategyproof) mechanism without money that can be implemented in polynomial time and yields a good approximation to the socially optimal solution. We study several special cases of gpp , and give constant approximation mechanisms for matroid, matching, knapsack, and the generalized assignment problem. Our result for generalized assignment problem solves an open problem proposed by Dughmi and Ghosh.

Our main technical contribution is in exploitation of the approaches from stable matching, which is a fundamental solution concept in the context of matching marketplaces, in application to mechanism design. Stable matching, while conceptually simple, provides a set of powerful tools to manage and analyze self-interested behaviors of participating agents. Our mechanism uses a stable matching algorithm as a critical component and adopts other approaches like random sampling and online mechanisms. Our work also enriches the stable matching theory with a new knapsack constrained matching model.

Joint work with Ning Chen and Nick Gravin.

3:00 -4:00

Title: Width Parameterized SAT

Speaker: Shiteng Chen (Tsinghua University)


Width parameterizations of $\sat$, such as tree-width and path-width,enable the study of computationally more tractable and practical $\sat$ instances. We give two simple algorithms. One that runs simultaneously in time-space $\big(2^{2\tw(\phi)}|\phi|^{O(1)},\; 2^{\tw(\phi)}|\phi|^{O(1)}\big)$ and another that runs in time-space $\big(3^{\tw(\phi)\log{|\phi|}}|\phi|^{O(1)},\;|\phi|^{O(1)}\big)$, where $\tw(\phi)$ is the tree-width of a formula $\phi$ with $|\phi|$ many clauses and variables. This partially answers the question of Alekhnovitch and Razborov who also gave algorithms exponential both in time and space in $\tw(\phi)$, and asked whether the space can be made smaller. We conjecture that every algorithm for this problem that runs in time 2^{\tw(\phi)\mathbf{o(\log{|\phi|})}}|\phi|^{O(1)}$ necessarily blows up the space to exponential in $\tw(\phi)$.

We introduce a novel way to combine the two simple algorithms that allows us to trade \emph{constant} factors in the exponents, where $\tw(\phi)$ appears, between running time and space. Our technique gives rise to a family of algorithms controlled by two parameters. By fixing one parameter we obtain an algorithm that runs in time-space $\big( 3^{1.441(1-\epsilon)\tw(\phi)\log{|\phi|}}|\phi|^{O(1)},\;$ $2^{2\epsilon\tw(\phi)}|\phi|^{O(1)} \big)$, for every $0<\epsilon<1$. We systematically study the limitations of this technique, and show that these algorithmic results are the best achievable using this technique.

We also study further the computational complexity of width parameterizations of $\sat$. We prove non-sparsification lower bounds for formulas of path-width $\omega(\log|\phi|)$, and a separation between the complexity of path-width and tree-width parameterized $\sat$ modulo plausible complexity assumptions.


Title: A constant-factor approximation for weighted dominating set in unit disk graph

Speaker: Xiaofeng Gao (Shanghai Jiao Tong University)

Abstract: Introduce a (10+e)-approximation algorithm to compute minimum-weight connected dominating set (MWCDS) in unit disk graph. MWCDS is to select a vertex subset with minimum weight for a given unit disk graph, such that each vertex of the graph is contained in this subset or has a neighbor in this subset. Besides, the subgraph induced by this vertex subset is connected. The algorithm is composed of two phases: the first phase computes a dominating set, which has approximation ratio 6+e (epsilon is an arbitrary positive number), while the second phase connects the dominating sets computed in the first phase, which has approximation ratio 4.