David S. Johnson

Head, Algorithms and Optimization Department
AT&T; Labs - Research

Address: David S. Johnson
         Room C239
         AT&T; Labs - Research
         180 Park Avenue
         Florham Park, NJ 07932-0971

Phone: 973-360-8440
Fax:   973-360-8178
Email: dsj@research.att.com

Research Interests:

Combinatorial Optimization, Approximation Algorithms, NP-Completeness, Network Design, Routing and Scheduling, Facilities Location, The Traveling Salesman Problem, Bin Packing, Graph Coloring

Additional Information:

Resume.
Publication List.
NP-Completeness Columns as .pdf files.
Other Papers that are available electronically.
Instructions on how to obtain the test instances discussed in my experimental papers.
Picture Wall: Algorithms and Theoretical Computer Science at AT&T; Labs - Research.
DIMACS Implementation Challenge on the TSP, which I organized.
Challenges for Theoretical Computer Sciences - A draft report I helped prepare for the NSF.