David S. Johnson

Juan A. Garay, David S. Johnson, Aggelos Kiayias, Moti Yung: Resource-based corruptions and the combinatorics of hidden diversity. ITCS 2013: 415-428

Juan A. Garay, David S. Johnson, Aggelos Kiayias, Moti Yung: Resource-based Corruptions and the Combinatorics of Hidden Diversity. IACR Cryptology ePrint Archive 2012: 556 (2012)

Lee Breslau, Ilias Diakonikolas, Nick G. Duffield, Yu Gu, Mohammad Taghi Hajiaghayi, David S. Johnson, Howard J. Karloff, Mauricio G. C. Resende, Subhabrata Sen: Disjoint-Path Facility Location: Theory and Practice. ALENEX 2011: 60-74

David S. Johnson, Anuj Mehrotra, Michael A. Trick: Special issue on computational methods for graph coloring and its generalizations. Discrete Applied Mathematics 156(2): 145-146 (2008)

Camil Demetrescu, Andrew V. Goldberg, David S. Johnson: Implementation Challenge for Shortest Paths. Encyclopedia of Algorithms 2008

David S. Johnson: Bin Packing. Encyclopedia of Algorithms 2008

David S. Johnson: The NP-completeness column: Finding needles in haystacks. ACM Transactions on Algorithms 3(2) (2007)

David S. Johnson: What is the science in experimental computer science? Experimental Computer Science 2007: 1

David Applegate, Gruia Calinescu, David S. Johnson, Howard J. Karloff, Katrina Ligett, Jia Wang: Compressing rectilinear pictures and minimizing access control lists. SODA 2007: 1066-1075

David S. Johnson, Uriel Feige (Eds.): Proceedings of the 39th Annual ACM Symposium on Theory of Computing, San Diego, California, USA, June 11-13, 2007. ACM 2007, isbn 978-1-59593-631-8

János Csirik, David S. Johnson, Claire Kenyon, James B. Orlin, Peter W. Shor, Richard R. Weber: On the Sum-of-Squares algorithm for bin packing. J. ACM 53(1): 1-65 (2006)

David S. Johnson: The NP-completeness column: The many limits on approximation. ACM Transactions on Algorithms 2(3): 473-489 (2006)

David S. Johnson: The NP-completeness column. ACM Transactions on Algorithms 1(1): 160-176 (2005)

Jatin Chhugani, Budirijanto Purnomo, Shankar Krishnan, Jonathan D. Cohen, Suresh Venkatasubramanian, David S. Johnson, Subodh Kumar: vLOD: High-Fidelity Walkthrough of Large Virtual Environments. IEEE Trans. Vis. Comput. Graph. 11(1): 35-47 (2005)

János Csirik, David S. Johnson, Claire Kenyon: On the Worst-case Performance of the Sum-of-Squares Algorithm for Bin Packing. CoRR abs/cs/0509031 (2005)

David S. Johnson, Shankar Krishnan, Jatin Chhugani, Subodh Kumar, Suresh Venkatasubramanian: Compressing Large Boolean Matrices using Reordering Techniques. VLDB 2004: 13-23

Alexander I. Barvinok, Sándor P. Fekete, David S. Johnson, Arie Tamir, Gerhard J. Woeginger, Russell Woodroofe: The geometric maximum traveling salesman problem. J. ACM 50(5): 641-664 (2003)

David Applegate, Luciana S. Buriol, Bernard L. Dillard, David S. Johnson, Peter W. Shor: The Cutting-Stock Approach to Bin Packing: Theory and Experiments. ALENEX 2003: 1-15

Alexander I. Barvinok, Sándor P. Fekete, David S. Johnson, Arie Tamir, Gerhard J. Woeginger, Russell Woodroofe: The Geometric Maximum Traveling Salesman Problem. CoRR cs.DS/0204024 (2002)

János Csirik, David S. Johnson, Claire Kenyon, James B. Orlin, Peter W. Shor, Richard R. Weber: On the Sum-of-Squares Algorithm for Bin Packing. CoRR cs.DS/0210013 (2002)

János Csirik, David S. Johnson: Bounded Space On-Line Bin Packing: Best Is Better than First. Algorithmica 31(2): 115-138 (2001)

Jill Cirasella, David S. Johnson, Lyle A. McGeoch, Weixiong Zhang: The Asymmetric Traveling Salesman Problem: Algorithms, Instance Generators, and Tests. ALENEX 2001: 32-59

János Csirik, David S. Johnson, Claire Kenyon: Better approximation algorithms for bin covering. SODA 2001: 557-566

Edward G. Coffman Jr., Costas Courcoubetis, M. R. Garey, David S. Johnson, Peter W. Shor, Richard R. Weber, Mihalis Yannakakis: Bin Packing with Discrete Item Sizes, Part I: Perfect Packing Theorems and the Average Case Behavior of Optimal Packings. SIAM J. Discrete Math. 13(3): 384-402 (2000)

David S. Johnson, Maria Minkoff, Steven Phillips: The prize collecting Steiner tree problem: theory and practice. SODA 2000: 760-769

János Csirik, David S. Johnson, Claire Kenyon, James B. Orlin, Peter W. Shor, Richard R. Weber: On the sum-of-squares algorithm for bin packing. STOC 2000: 208-217

János Csirik, David S. Johnson, Claire Kenyon, Peter W. Shor, Richard R. Weber: A Self Organizing Bin Packing Heuristic. ALENEX 1999: 246-265

David S. Johnson, Mario Szegedy: What are the Least Tractable Instances of max Tndependent Set? SODA 1999: 927-928

Alexander I. Barvinok, David S. Johnson, Gerhard J. Woeginger, Russell Woodroofe: The Maximum Traveling Salesman Problem Under Polyhedral Norms. IPCO 1998: 195-201

Edward G. Coffman Jr., David S. Johnson, Peter W. Shor, Richard R. Weber: Bin packing with discrete item sizes, part II: Tight bounds on First Fit. Random Struct. Algorithms 10(1-2): 69-101 (1997)

Alfred V. Aho, David S. Johnson, Richard M. Karp, S. Rao Kosaraju, Catherine C. McGeoch, Christos H. Papadimitriou, Pavel A. Pevzner: Emerging opportunities for theoretical computer science. SIGACT News 28(3): 65-74 (1997)

Anne Condon, Faith Fich, Greg N. Frederickson, Andrew V. Goldberg, David S. Johnson, Michael C. Loui, Steven Mahaney, Prabhakar Raghavan, John E. Savage, Alan L. Selman, David B. Shmoys: Strategic directions in research in theory of computing. SIGACT News 28(3): 75-93 (1997)

Cliff Young, David S. Johnson, David R. Karger, Michael D. Smith: Near-optimal Intraprocedural Branch Alignment. PLDI 1997: 183-193

David S. Johnson: How to do experiments (extended advertisement). SIGACT News 27(2): 87 (1996)

David S. Johnson: A Brief History of SIGACT News and its Editors. SIGACT News 27(3): 125 (1996)

David S. Johnson, Lyle A. McGeoch, Edward E. Rothberg: Asymptotic Experimental Analysis for the Held-Karp Traveling Salesman Bound. SODA 1996: 341-350

Michael L. Fredman, David S. Johnson, Lyle A. McGeoch, G. Ostheimer: Data Structures for Traveling Salesmen. J. Algorithms 18(3): 432-479 (1995)

Elias Dahlhaus, David S. Johnson, Christos H. Papadimitriou, Paul D. Seymour, Mihalis Yannakakis: The Complexity of Multiterminal Cuts. SIAM J. Comput. 23(4): 864-894 (1994)

David S. Johnson: The Traveling Salesman Problem: A report on the State of the Art. IFIP Congress (1) 1994: 221-222

David S. Johnson, Andrea S. LaPaugh, Ron Y. Pinter: Minimizing Channel Density by Lateral Shifting of Components. SODA 1994: 122-131

David S. Johnson, Francine Berman: Performance of the Efficient Data-Driven Evaluation Scheme. J. Parallel Distrib. Comput. 18(3): 340-346 (1993)

Michael L. Fredman, David S. Johnson, Lyle A. McGeoch, G. Ostheimer: Data Structures for Traveling Salesmen. SODA 1993: 145-154

Edward G. Coffman Jr., David S. Johnson, Peter W. Shor, Richard R. Weber: Markov chains, computer proofs, and average-case analysis of best fit bin packing. STOC 1993: 412-421

S. Rao Kosaraju, David S. Johnson, Alok Aggarwal (Eds.): Proceedings of the Twenty-Fifth Annual ACM Symposium on Theory of Computing, May 16-18, 1993, San Diego, CA, USA. ACM 1993, isbn 0-89791-591-7

David S. Johnson: The NP-Completeness Column: An Ongoing Guide. J. Algorithms 13(3): 502-524 (1992)

Elias Dahlhaus, David S. Johnson, Christos H. Papadimitriou, Paul D. Seymour, Mihalis Yannakakis: The Complexity of Multiway Cuts (Extended Abstract). STOC 1992: 241-251

János Csirik, David S. Johnson: Bounded Space On-Line Bin Packing: Best is Better than First. SODA 1991: 309-319

Edward G. Coffman Jr., Costas Courcoubetis, M. R. Garey, David S. Johnson, Lyle A. McGeoch, Peter W. Shor, Richard R. Weber, Mihalis Yannakakis: Fundamental Discrepancies between Average-Case Analyses under Discrete and Continuous Distributions: A Bin Packing Case Study. STOC 1991: 230-240

Brent N. Clark, Charles J. Colbourn, David S. Johnson: Unit disk graphs. Discrete Mathematics 86(1-3): 165-177 (1990)

David S. Johnson: The NP-Completeness Column: An Ongoing Guide. J. Algorithms 11(1): 144-151 (1990)

Francine Berman, David S. Johnson, Frank Thomson Leighton, Peter W. Shor, Larry Snyder: Generalized Planar Matching. J. Algorithms 11(2): 153-184 (1990)

David S. Johnson: A stoc/focs bibliography: the last progress report. SIGACT News 21(2): 4 (1990)

David S. Johnson: A Catalog of Complexity Classes. Handbook of Theoretical Computer Science, Volume A: Algorithms and Complexity (A) 1990: 67-161

David S. Johnson: Local Optimization and the Traveling Salesman Problem. ICALP 1990: 446-461

David S. Johnson: Data Structures for Traveling Salesmen (Abstract). SWAT 1990: 287

David S. Johnson (Ed.): Proceedings of the First Annual ACM-SIAM Symposium on Discrete Algorithms, 22-24 January 1990, San Francisco, California. SIAM 1990, isbn 0-89871-251-3

David S. Johnson (Ed.): Proceedings of the 21st Annual ACM Symposium on Theory of Computing, May 14-17, 1989, Seattle, Washigton, USA. ACM 1989, isbn 0-89791-307-8

David S. Johnson, Christos H. Papadimitriou, Mihalis Yannakakis: On Generating All Maximal Independent Sets. Inf. Process. Lett. 27(3): 119-123 (1988)

Nimrod Megiddo, S. Louis Hakimi, M. R. Garey, David S. Johnson, Christos H. Papadimitriou: The complexity of searching a graph. J. ACM 35(1): 18-44 (1988)

David S. Johnson: The NP-Completeness Column: An Ongoing Guide. J. Algorithms 9(3): 426-444 (1988)

David S. Johnson, Christos H. Papadimitriou, Mihalis Yannakakis: How Easy is Local Search? J. Comput. Syst. Sci. 37(1): 79-100 (1988)

David S. Johnson: The NP-Completeness Column: An Ongoing Guide. J. Algorithms 8(2): 285-303 (1987)

David S. Johnson: The NP-Completeness Column: An Ongoing Guide. J. Algorithms 8(3): 438-448 (1987)

Edward G. Coffman Jr., M. R. Garey, David S. Johnson: Bin packing with divisible item sizes. J. Complexity 3(4): 406-428 (1987)

David S. Johnson: The NP-Completeness Column: An Ongoing Guide. J. Algorithms 7(2): 289-305 (1986)

David S. Johnson: The NP-Completeness Column: An Ongoing Guide. J. Algorithms 7(4): 584-601 (1986)

David S. Johnson: The NP-Completeness Column: An Ongoing Guide. J. Algorithms 6(1): 145-159 (1985)

David S. Johnson: The NP-Completeness Column: An Ongoing Guide. J. Algorithms 6(2): 291-305 (1985)

David S. Johnson: The NP-Completeness Column: An Ongoing Guide. J. Algorithms 6(3): 434-451 (1985)

David S. Johnson, M. R. Garey: A 71/60 theorem for bin packing. J. Complexity 1(1): 65-106 (1985)

M. R. Garey, David S. Johnson: Composing Functions to Minimize Image Size. SIAM J. Comput. 14(2): 500-503 (1985)

Edward G. Coffman Jr., M. R. Garey, David S. Johnson, Andrea S. LaPaugh: Scheduling File Transfers. SIAM J. Comput. 14(3): 744-780 (1985)

David S. Johnson, Christos H. Papadimitriou, Mihalis Yannakakis: How Easy Is Local Search? (Extended Abstract). FOCS 1985: 39-42

David S. Johnson: The NP-Completeness Column: An Ongoing Guide. J. Algorithms 5(1): 147-160 (1984)

David S. Johnson: The NP-Completeness Column: An Ongoing Guide. J. Algorithms 5(2): 284-299 (1984)

David S. Johnson: The NP-Completeness Column: An Ongoing Guide. J. Algorithms 5(3): 433-447 (1984)

S. F. Assmann, David S. Johnson, Daniel J. Kleitman, Joseph Y.-T. Leung: On a Dual Version of the One-Dimensional Bin Packing Problem. J. Algorithms 5(4): 502-525 (1984)

David S. Johnson: The NP-Completeness Column: An Ongoing Guide. J. Algorithms 5(4): 595-609 (1984)

David S. Johnson, Anthony C. Klug: Testing Containment of Conjunctive Queries under Functional and Inclusion Dependencies. J. Comput. Syst. Sci. 28(1): 167-189 (1984)

Jon Louis Bentley, David S. Johnson, Frank Thomson Leighton, Catherine C. McGeoch, Lyle A. McGeoch: Some Unexpected Expected Behavior Results for Bin Packing. STOC 1984: 279-288

David S. Johnson: The NP-Completeness Column: An Ongoing Guide. J. Algorithms 4(1): 87-100 (1983)

David S. Johnson: The NP-Completeness Column: An Ongoing Guide. J. Algorithms 4(2): 189-203 (1983)

David S. Johnson: The NP-Completeness Column: An Ongoing Guide. J. Algorithms 4(3): 286-300 (1983)

David S. Johnson: The NP-Completeness Column: An Ongoing Guide. J. Algorithms 4(4): 397-411 (1983)

Edward G. Coffman Jr., M. R. Garey, David S. Johnson: Dynamic Bin Packing. SIAM J. Comput. 12(2): 227-258 (1983)

David S. Johnson, Anthony C. Klug: Optimizing Conjunctive Queries that Contain Untyped Variables. SIAM J. Comput. 12(4): 616-640 (1983)

Edward G. Coffman Jr., M. R. Garey, David S. Johnson, Andrea S. LaPaugh: Scheduling File Transfers in a Distributed Network. PODC 1983: 254-266

David S. Johnson, Ronald Fagin, Michael L. Fredman, David Harel, Richard M. Karp, Nancy A. Lynch, Christos H. Papadimitriou, Ronald L. Rivest, Walter L. Ruzzo, Joel I. Seiferas (Eds.): Proceedings of the 15th Annual ACM Symposium on Theory of Computing, 25-27 April, 1983, Boston, Massachusetts, USA. ACM 1983

David S. Johnson: The NP-Completeness Column: An Ongoing Guide. J. Algorithms 3(1): 89-99 (1982)

David S. Johnson: The NP-Completeness Column: An Ongoing Guide. J. Algorithms 3(2): 182-195 (1982)

David S. Johnson: The NP-Completeness Column: An Ongoing Guide. J. Algorithms 3(3): 288-300 (1982)

David S. Johnson: The NP-Completeness Column: An Ongoing Guide. J. Algorithms 3(4): 381-395 (1982)

M. R. Garey, David S. Johnson, Hans S. Witsenhausen: The complexity of the generalized Lloyd - Max problem. IEEE Transactions on Information Theory 28(2): 255-256 (1982)

David S. Johnson, Anthony C. Klug: Testing Containment of Conjunctive Queries Under Functional and Inclusion Dependencies. PODS 1982: 164-169

David S. Johnson: The NP-Completeness Column: An Ongoing Guide. J. Algorithms 2(4): 393-405 (1981)

M. R. Garey, David S. Johnson, Barbara B. Simons, Robert Endre Tarjan: Scheduling Unit-Time Tasks with Arbitrary Release Times and Deadlines. SIAM J. Comput. 10(2): 256-269 (1981)

David S. Johnson, Anthony C. Klug: Optimizing Conjunctive Queries When Attribute Domains Are not Disjoint (Extended Abstract). FOCS 1981: 203-211

Nimrod Megiddo, S. Louis Hakimi, M. R. Garey, David S. Johnson, Christos H. Papadimitriou: The Complexity of Searching a Graph (Preliminary Version). FOCS 1981: 376-385

Edward G. Coffman Jr., M. R. Garey, David S. Johnson, Robert Endre Tarjan: Performance Bounds for Level-Oriented Two-Dimensional Packing Algorithms. SIAM J. Comput. 9(4): 808-826 (1980)

M. R. Garey, David S. Johnson: Computers and Intractability: A Guide to the Theory of NP-Completeness. W. H. Freeman 1979, isbn 0-7167-1044-7

M. R. Garey, David S. Johnson, Franco P. Preparata, Robert Endre Tarjan: Triangulating a Simple Polygon. Inf. Process. Lett. 7(4): 175-179 (1978)

M. R. Garey, David S. Johnson: ``Strong'' NP-Completeness Results: Motivation, Examples, and Implications. J. ACM 25(3): 499-508 (1978)

William M. Boyce, M. R. Garey, David S. Johnson: A note on bisecting minimum spanning trees. Networks 8(3): 187-192 (1978)

David S. Johnson, Jan Karel Lenstra, A. H. G. Rinnooy Kan: The complexity of the network design problem. Networks 8(4): 279-285 (1978)

Edward G. Coffman Jr., M. R. Garey, David S. Johnson: An Application of Bin-Packing to Multiprocessor Scheduling. SIAM J. Comput. 7(1): 1-17 (1978)

David S. Johnson, Franco P. Preparata: The Densest Hemisphere Problem. Theor. Comput. Sci. 6: 93-107 (1978)

Aviezri S. Fraenkel, M. R. Garey, David S. Johnson, T. Schaefer, Yaacov Yesha: The Complexity of Checkers on an N * N Board - Preliminary Report. FOCS 1978: 55-64

M. R. Garey, David S. Johnson: The Rectilinear Steiner Tree Problem in NP Complete. SIAM Journal of Applied Mathematics 32: 826-834 (1977)

M. R. Garey, David S. Johnson: Two-Processor Scheduling with Start-Times and Deadlines. SIAM J. Comput. 6(3): 416-426 (1977)

M. R. Garey, Frank K. Hwang, David S. Johnson: Algorithms for a Set Partitioning Problem Arising in the Design of Multipurpose Units. IEEE Trans. Computers 26(4): 321-328 (1977)

M. R. Garey, David S. Johnson: The Complexity of Near-Optimal Graph Coloring. J. ACM 23(1): 43-49 (1976)

M. R. Garey, David S. Johnson: Scheduling Tasks with Nonuniform Deadlines on Two Processors. J. ACM 23(3): 461-467 (1976)

M. R. Garey, Ronald L. Graham, David S. Johnson: Resource Constrained Scheduling as Generalized Bin Packing. J. Comb. Theory, Ser. A 21(3): 257-298 (1976)

M. R. Garey, David S. Johnson, Robert Endre Tarjan: The Planar Hamiltonian Circuit Problem is NP-Complete. SIAM J. Comput. 5(4): 704-714 (1976)

M. R. Garey, David S. Johnson, Larry J. Stockmeyer: Some Simplified NP-Complete Graph Problems. Theor. Comput. Sci. 1(3): 237-267 (1976)

M. R. Garey, Ronald L. Graham, David S. Johnson: Some NP-Complete Geometric Problems. STOC 1976: 10-22

M. R. Garey, David S. Johnson: Complexity Results for Multiprocessor Scheduling under Resource Constraints. SIAM J. Comput. 4(4): 397-411 (1975)

M. R. Garey, David S. Johnson, H. C. So: An Application of Graph Coloring to Printed Circuit Testing (Working Paper). FOCS 1975: 178-183

David S. Johnson: Fast Algorithms for Bin Packing. J. Comput. Syst. Sci. 8(3): 272-314 (1974)

David S. Johnson: Approximation Algorithms for Combinatorial Problems. J. Comput. Syst. Sci. 9(3): 256-278 (1974)

David S. Johnson, Alan J. Demers, Jeffrey D. Ullman, M. R. Garey, Ronald L. Graham: Worst-Case Performance Bounds for Simple One-Dimensional Packing Algorithms. SIAM J. Comput. 3(4): 299-325 (1974)

M. R. Garey, David S. Johnson, Larry J. Stockmeyer: Some Simplified NP-Complete Problems. STOC 1974: 47-63

David S. Johnson: Approximation Algorithms for Combinatorial Problems. STOC 1973: 38-49

David S. Johnson: Fast Allocation Algorithms. SWAT (FOCS) 1972: 144-154