David S. Johnson - Electronically Available Papers

Last Updated: 2 May 2011

NP-Completeness Columns

Experimental Methodology

  1. A Theoretician's Guide to the Experimental Analysis of Algorithms, D. S. Johnson. in Data Structures, Near Neighbor Searches, and Methodology: Fifth and Sixth DIMACS Implementation Challenges, M. H. Goldwasser, D. S. Johnson, and C. C. McGeoch, Editors, American Mathematical Society, Providence, 2002, 215-250. Postscript of final draft (36 pages). [PDF version] (This replaces previous 7-page partial draft dated 4/30/96.)

Networking Research

  1. The Complexity of Multiterminal Cuts, E. Dahlhaus, D. S. Johnson, C. H. Papadimitriou, P. D. Seymour and M. Yannakakis, SIAM J. Computing, 23 (1994), pp. 864-894. [Preliminary version: The Complexity of Multiway Cuts, Proc. 24th Ann. ACM Symp. on Theory of Computing (1992), 241-251.] Postscript of final draft (37 pages) [PDF version]

  2. The Prize Collecting Steiner Tree Problem: Theory and Practice, D. S. Johnson, M. Minkoff, and S. Phillips. Proc. 11th Ann. ACM-SIAM Symp. on Discrete Algorithms, (2000), 760-769. Postscript of final draft (10 pages) [PDF version]

  3. Efficient and robust streaming provisioning in VPNs, Z. M. Mao, D. Johnson, O. Spatscheck, J. E. van der Merwe, and J. Wang, in Proceedings WWW 2003, pp. 118-127. PDF of final draft (10 pages)

  4. Scalable and accurate identification of AS-level forwarding paths, Z. M. Mao, D. Johnson, J. Rexford, J. Wang, and R. Katz, in Proceedings INFOCOM 2004. PDF of final draft (11 pages)

  5. Compressing rectilinear pictures and minimizing access control lists, D. L. Applegate, G. Calinescu, D. S. Johnson, H. Karloff, K. Ligett, and J. Wang, Proc. 18th ACM-SIAM Symp. on Discrete Algorithms, (2007), 1066-1075. Postscript of final draft (10 pages) [PDF version] Rough draft of full version of paper (58 pages) [Postscript] [PDF]

  6. Disjoint-path facility location: Theory and practice, L. Breslau, , I. Diakonikolas, N. Duffield, Y. Gu, M. Hajiaghayi, D. S. Johnson, H. Karloff, M. G. C. Resende, and S. Sen, 2011 Proc. of the Thirteenth Workshop on Algorithm Engineering and Experimentation (ALENEX), (2011), 60-74. [PDF]. Rough (and as-yet-incomplete) draft of full version of paper (28 pages) [PDF]

Bin Packing

  1. Approximation Algorithms for Bin Packing: A Survey, E. G. Coffman, Jr., M. R. Garey, and D. S. Johnson, Approximation Algorithms for NP-Hard Problems, D. Hochbaum (editor), PWS Publishing, Boston (1997), 46-93. A survey of worst- and average-case results for the classical one-dimensional bin packing problem. Postscript of final draft (53 pages) [PDF version]

  2. Bin Packing with Discrete Item Sizes, Part I: Perfect Packing Theorems and the Average Case Behavior of Optimal Packings, E. G. Coffman, Jr., C. Courcoubetis, M. R. Garey, D. S. Johnson, P. W. Shor, R. R. Weber, and M. Yannakakis, SIAM J. Discrete Math. 13 (2000), 384-402. Postscript of final draft (25 pages) [PDF version]

  3. Bin Packing with Discrete Item Sizes, Part II: Tight Bounds on First Fit, E. G. Coffman, Jr., D. S. Johnson, P. W. Shor and R. R. Weber, Random Structures and Algorithms 10 (1997), 69-101. Postscript of final draft (38 pages) [PDF version]

  4. Bounded Space On-Line Bin Packing: Best is Better than First, J. Csirik and D. S. Johnson. Algorithmica 31:2 (2001) 115-138. Journal version of paper with same title in Proceedings 2nd Annual ACM Symp. on Discrete Algorithms (1991), 309-319. Postscript of final draft (24 pages) [PDF version]

  5. A Self-Organizing Bin Packing Heuristic, J. Csirik, D. S. Johnson, C. Kenyon, P. W. Shor, and R. R. Weber, Algorithm Engineering and Experimentation: International Workshop ALENEX '99, Springer Lecture Notes in Computer Science 1619 (1999), 246-265. Postscript of final draft (20 pages). [PDF version]

  6. On the Sum-of-Squares Algorithm for Bin Packing, J. Csirik, D. S. Johnson, C. Kenyon, J. B. Orlin, P. W. Shor, and R. R. Weber. Proc. 32nd Annual ACM Symp. on Theory of Computing (2000), 208-217. Postscript of final draft (10 pages) [PDF version]. Journal version: J.ACM 53 (2006), 1-65. Postscript of final draft (67 pages) [PDF version]

  7. Better Approximation Algorithms for Bin Covering, J. Csirik, D. S. Johnson, and C. Kenyon. Proc. 12th Ann. ACM-SIAM Symp. on Discrete Algorithms (2001), 557-566. Postscript of final draft (10 pages) [PDF version]

  8. Perfect Packing Theorems and the Average Case Behavior of Optimal and Online Bin Packing, E. G. Coffman, Jr., C. Courcoubetis, M. R. Garey, D. S. Johnson, P. W. Shor, R. R. Weber, and M. Yannakakis, SIAM Review 44 (2002), 95-108. A revised version of paper (2) above for the SIGEST reprint section of SIAM Review. Postscript of final draft (14 pages) [PDF version]

  9. The Cutting-Stock Approach to Bin Packing: Theory and Experiments, D. L. Applegate, L. S. Buriol, B. L. Dillard, D. S. Johnson, and P. W. Shor. in Proceedings of the Fifth Workshop on Algorithm Engineering and Experimentation, R.E. Ladner (Editor), SIAM, 2003, pp 1-15. Postscript (15 pages) [PDF version] An expanded version, containing results that had to be omitted because of the ALENEX page limits, should be available here soon.

  10. On the Worst-case Performance of the Sum-of-Squares Algorithm for Bin Packing, J. Csirik, D. S. Johnson, and C. Kenyon. arXiv.org E-print arXiv:cs.DS/0509031 at http://arxiv.org/archive/cs. PDF (5 pages)

The Traveling Salesman Problem

  1. Data Structures for Traveling Salesmen, M. L. Fredman, D. S. Johnson, L. A. McGeoch and G. Ostheimer, J. Algorithms, 18:3 (1995), pp. 432-479. [Preliminary version: Proc. 4th Ann. ACM-SIAM Symp. on Discrete Algorithms (1993), 145-154.] Postscript of final draft of journal version (47 pages) [PDF version]

  2. Asymptotic Experimental Analysis for the Held-Karp Traveling Salesman Bound, D. S. Johnson, L. A. McGeoch, and E. E. Rothberg, Proc. 7th Ann. ACM-SIAM Symp. on Discrete Algorithms, 1996, pp. 341-350. Postscript of final draft (10 pages) [PDF version]

  3. The Traveling Salesman Problem: A Case Study in Local Optimization, D. S. Johnson and L. A. McGeoch, Local Search in Combinatorial Optimization, E. H. L. Aarts and J. K. Lenstra (editors), John Wiley and Sons, Ltd., 1997, pp. 215-310. Covers selected tour construction heuristics, classical local optimization algorithms (2-Opt, 3-Opt, Lin-Kernighan), simulated annealing, tabu search, genetic algorithms, and neural net algorithms. Postscript of final draft (103 pages) [PDF version]

  4. Near-optimal Intraprocedural Branch Alignment, C. Young, D. S. Johnson, D. R. Karger, and M. D. Smith, Proceedings 1997 Symp. on Programming Languages, Design, and Implementation, 183-193. Covers an application of the asymmetric TSP to code optimization. Instances of the asymmetric TSP were solved using the symmetric algorithm ``Iterated 3-Opt'' by means of the NP-completeness transformation from the asymmetric to the symmetric TSP. Postscript of final draft (11 two-column pages) [PDF version]

  5. The Maximum Traveling Salesman Problem under Polyhedral Norms, A. Barvinok, G. J. Woeginger, D. S. Johnson, and R. Woodroofe. Proc. 1998 Symp. on Integer Programming and Combinatorial Optimization (IPCO 98), Springer Lecture Notes in Computer Science 1412, 1998, 195-201. Postscript of final draft (7 pages) [PDF version]

  6. The Geometric Maximum Traveling Salesman Problem, A. Barvinok, S. Fekete, D. S. Johnson, A. Tamir, G. J. Woeginger, and R. Woodroofe. Combined journal version of previous paper and Fekete's 1999 SODA paper on the maximum TSP, including a faster algorithm for arbitrary polyhedral metrics. JACM 50 2003, 641-664. Postscript of draft (23 pages) [PDF version]

  7. The Asymmetric Traveling Salesman Problem: Algorithms, Instance Generators, and Tests, J. Cirasella, D. S. Johnson, L. A. McGeoch, and W. Zhang, ALENEX 2001 Proceedings, Springer Lecture Notes in Computer Science 2153, A. L. Buchsbaum and J. Snoeyink (eds.), 32-59. Postscript of final draft (28 pages) [PDF version]

  8. Experimental Analysis of Heuristics for the STSP, D. S. Johnson and L. A. McGeoch. The Traveling Salesman Problem and its Variations, G. Gutin and A. Punnen, Editors, Kluwer Academic Publishers, Dordrecht, 2002, 369-443. Postscript of final draft (80 pages) [PDF version]

  9. Experimental Analysis of Heuristics for the ATSP, D. S. Johnson, G. Gutin, L. A. McGeoch, A. Yeo, W. Zhang, and A. Zverovich. The Traveling Salesman Problem and its Variations, G. Gutin and A. Punnen, Editors, Kluwer Academic Publishers, Dordrecht, 2002, 445-487. Postscript of final draft (45 pages) [PDF version]

  10. Compressing Large Boolean Matrices using Reordering Techniques, D. S. Johnson, S. Krishnan, J. Chhugani, S. Kumar, and S. Venkatasubramanian in Proc. 30th Int. Conf. on Very Large Databases (VLDB), 2004, 13-23. PDF of final draft (11 pages)

Miscellaneous

  1. Minimizing Channel Density by Lateral Shifting of Components, D. S. Johnson, A. S. LaPaugh, and R. Y. Pinter. Journal version (currently being refereed) of the paper of the same name that appeared in Proc. 5th Ann. ACM-SIAM Symp. on Discrete Algorithms, 1994, 122-131. Postscript (70 pages) [PDF version]

Go to David Johnson's Home Page