Thành Nguyen

Research (DBLP)

Algorithmic Game Theory

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

Clustering and Labeling Problems

• Parallel Imaging problem.
  with Éva Tardos. ESA 2008.
  Speeding up the scanning time of Magnetic Resonance Imaging machine is very important as it reduces the motion artifact. However the correspodning Image reconstruction problem become more complex: instead of observing the image directly, we obtain some linear transforms of the image. In this paper, we introduce the parallel imaging problem as a model of the Parallel MRI reconstruction. We give a constant approximation algorithm for the problem using a new graph cut construction.

Routing and Traveling Problems

• A simple LP relaxation for the Asymmetric Traveling Salesman Problem.
  APPROX 08.
  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.
  
  
• 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.
  
  
• 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.

Graph Theory

• 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. A refined result of Schrijver on the integral solution of certain systems of linear inequalities is also given.