A | B | C | D | E | F 
 G | H | I | J | K | L | M 
 N | O | P | Q | R | S | T 
 U | V | W | X | Y | Z 

max planck institut
informatik

Homepage

Hubert Chan Max-Planck-Institut für Informatik Department 1: Algorithms & Complexity Campus E1 4, Room 309 66123 Saarbrücken Germany Email: loginID @ mpi-inf.mpg.de My Research interests are approximation algorithms, combinatorial optimization and metric spaces. I have defended my PhD thesis in September 2007 under the supervision of my advisor Anupam Gupta at Carnegie Mellon University. Starting from August 2009, I will be an assistant professor at the University of Hong Kong. Click here for my new homepage.

---

Thesis

• Approximation Algorithms for Bounded Dimensional Metric Spaces Carnegie Mellon University Technical Report CMU-CS-07-157. 2007.

---

Journal Papers

• Metric Embeddings with Relaxed Guarantees T-H. Hubert Chan, Kedar Dhamdhere, Anupam Gupta, Jon Kleinberg, and Aleksandrs Slivkins. SIAM Journal on Computing. 2009.
• Small Hop-diameter Sparse Spanners for Doubling Metrics T-H. Hubert Chan and Anupam Gupta. Discrete and Computational Geometry. 2008.

---

Conference Papers

• An SDP Primal-Dual Algorithm for Approximating the Lovasz-Theta Function T-H. Hubert Chan, Kevin L. Chang and Rajiv Raman. IEEE International Symposium on Information Theory 2009.
• Ultra-Low-Dimensional Embeddings for Doubling Metrics T-H. Hubert Chan, Anupam Gupta and Kunal Talwar. SODA 2008.
• Approximating TSP on Metrics with Bounded Global Growth T-H. Hubert Chan and Anupam Gupta. SODA 2008.
• A Theory of Loss-Leaders: Making Money by Pricing Below Cost Maria-Florina Balcan, Avrim Blum, T-H. Hubert Chan and MohammadTaghi Hajiaghayi. WINE 2007.
• Multi-dimensional Range Query over Encrypted Data Elaine Shi, John Bethencourt, T-H. Hubert Chan, Dawn Song and Adrian Perrig. IEEE Symposium on Security and Privacy 2007.
• Spanners with Slack T-H. Hubert Chan, Michael Dinitz and Anupam Gupta. ESA 2006.
• A Tight Lower Bound for the Steiner Point Removal Problem on Trees T-H. Hubert Chan, Donglin Xia, Goran Konjevod and Andrea Richa. APPROX 2006.
• Small Hop-diameter Sparse Spanners for Doubling Metrics T-H. Hubert Chan and Anupam Gupta. SODA 2006.
• A Random-Surfer Web-Graph Model Avrim Blum, T-H. Hubert Chan, and Mugizi Robert Rwebangira. ANALCO 2006.
• Metric Embeddings with Relaxed Guarantees Ittai Abraham, Yair Bartal, T-H. Hubert Chan, Kedar Dhamdhere, Anupam Gupta, Jon Kleinberg, Ofer Neiman, and Aleksandrs Slivkins. FOCS 2005.
• On Hierarchical Routing in Doubling Metrics T-H. Hubert Chan, Anupam Gupta, Bruce M. Maggs, and Shuheng Zhou. SODA 2005. (Complete proof for the bounded degree spanner construction.)

---

Manuscripts

• A QPTAS for TSP with Fat Weakly Disjoint Neighborhoods in Doubling Metrics T-H. Hubert Chan and Khaled Elbassioni. DIMACS Technical Report 2009-01.

---

• Hubert Chan:
• Thesis
• Journal Papers
• Conference Papers