Thành Nguyen

Papers

1. Thành Nguyen
   A simple LP relaxation for the Asymmetric Traveling Salesman Problem. (To appear in APPROX 08)

   Abstract: A long-standing conjecture in Combinatorial Optimization is that the integrality gap of the Held-Karp LP relaxation for the Asymmetric Traveling Salesman Problem (ATSP) is a constant. In this paper, 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. Moreover, more than half of these non-zero variables can be rounded to integers while the total cost only increases by a constant factor.

2. Thành Nguyen, Éva Tardos
   Parallel Imaging problem. (To appear in ESA 08)

   Abstract: We give a constant approximation for a problem motivated by Magnetic Resonance Imaging reconstruction. Our problem combines the metric labeling problem and linear algebra.

3. Thành Nguyen, Éva Tardos
   Approximately Maximizing Efficiency and Revenue in Polyhedral Environments. (in the Proceeding of ACM EC 2007)

   Abstract: 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 extend the fair sharing mechanism for such resource allocation games, and show that our mechanism simultaneously creates approximately efficient allocations and approximately maximizes revenue.

4. Thành Nguyen
   On the disjoint paths problem. (Operation Research Letters, Volume 35, Issue 1, January 2007, pages 10-16)

   Abstract: 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.

5. Ephraim Korach, Thành Nguyen and Britta Peis
   Subgraph characterization of Red/Blue-split graphs and König-Egerváry graphs (in the Proceeding of SODA 2006)

   Abstract: König-Egerváry 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, Lovász, and Földes-Hammer. A refined result of Schrijver on the integral solution of certain systems of linear inequalities is also given.

6. Thành Nguyen
   Disjoint paths and cuts in planar graphs. (M.Sc thesis, 2004)

   Abstract: 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.