Thanh Nguyen's homepage

Thành Nguyen

Center for Applied Mathematics
657 Rhodes Hall, Cornell University
Ithaca, NY 14853
Tel: 607-255-4756
URL: http://www.cam.cornell.edu/~thanh
Email: thanh@cs.cornell.edu

I am a PhD student at Center for Applied Mathematics, Cornell University. My research topics are Algorithms and Game Theory. I like designing algorithms for network problems and mechanisms for large systems involving selfish agents. My advisor is Éva Tardos.

I was born and grew up in Bac Ninh, a small town in Vietnam, then went to Budapest, Hungary for my Diploma in Mathematics at Eötvös University.

Teaching

Summer 2008: Instructor for CS4820: Introduction to Analysis of Algorithms.
Spring 2008: TA for CS684 : Algorithmic Game Theory.
Spring 2006: TA for CS485 : Mathematical Foundations for the Information Age.

Research (DBLP)

Algorithmic Game Theory

The weighted proportional sharing mechanisms.
with Milan Vojnovic. Manuscript 2009.
We introduce a class of dynamic and simple mechanisms for resource allocation problems in a competitive environment, where both providers and users are strategic. We prove their performance in terms of revenue and efficiency.
Approximate Nash equilibria via Lovasz local lemma.
with Éva Tardos. WINE 2009.
We introduce a new technique using local lemma to show the existence and algorithms to find approximate Nash in graphical games.
Approximately Maximizing Efficiency and Revenue in Polyhedral Environments.
with Éva Tardos. EC 2007.
We consider a resource allocation game in convex environments. Convex environments model a wide range of problems, including bandwidth sharing, some models of Adword auctions and general resource allocation. We show a mechanism achieving approximately both revenue and efficiency.

Clustering and Labeling Problems

Parallel Imaging problem.
with Éva Tardos. ESA 2008.
We give a new technique o reconstruct images obtained by Parallel Magnetic Resonance Imaging Process. The technique involves a new graph cut construction and give a a constant approximation algorithm for the problem.

Routing, Traveling and Matching Problems

A simple LP relaxation for the Asymmetric Traveling Salesman Problem.
APPROX 08.
We give a simpler LP relaxation for the ASTP. The integrality gaps of this relaxation and of the Held-Karp relaxation are within a constant factor of each other. Our LP is simpler in the sense that its extreme solutions have at most $2n-2$ non-zero variables, improving the bound $3n-2$ proved by Vempala and Yannakakis for the extreme solutions of the Held-Karp LP relaxation.
On the disjoint paths problem.
Operation Research Letters, Vol. 35, 1, 2007.
We give a $\sqrt n +1$ approximation algorithm for the edge disjoint paths problem in undirected graphs. This is currently the best known approximation guarantee. Our combinatorial technique also leads to $O(\sqrt n)$ approximation for directed acyclic graphs and directed graphs with edge capacity greater or equal to two.
Subgraph characterization of Red/Blue-split graphs and Konig-Egervary graphs
with Ephraim Korach and Britta Peis. SODA 2006.
Konig-Egervary graphs (KEGs) are the graphs whose maximum size of a matching is equal to the minimum size of a vertex cover. We give an excluded subgraph characterization of KEGs by proving a more general result: excluded subgraph characterization of Red/Blue-split graphs. We show several consequences of this result including theorems of Demming-Sterboul, Lovasz, and Foldes-Hammer.
Disjoint paths and cuts in planar graphs.
M.Sc thesis, 2004.
We reprove theorems of Okamura-Seymour, Schrijver on disjoint paths in planar graphs using dual path method. This method also gives the results on packing disjoint cuts, some of them are known as Hurkens, Schrijver, Tardos and Gerards' theorems, some of them are new. A characterization of node-capacitated routing in a ring network is also given. The characterzation is a cut-type and a parity condition.