David S. Johnson


Address: David S. Johnson
         523 Computer Science Building
         Mail Code 0401
         Department of Computer Science
         Columbia University
         1214 Amsterdam Avenue
         New York, NY 10027-7003
Phone: 212-939-7053
Email: dstiflerj@gmail.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:

Publication List.
NP-Completeness Columns as .pdf files.
Other Papers that are available electronically.
Talks as .ppt files.
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.
TSP Course Materials