David S. Johnson

According to our database1, David S. Johnson authored at least 134 papers between 1972 and 2018.

Collaborative distances:
  • Dijkstra number2 of three.
  • Erdős number3 of two.

Awards

ACM Fellow

ACM Fellow 1995, "For fundamental contributions to the theories of approximation algorithms and computational complexity, and for outstanding service to ACM.".

Timeline

Legend:

Book 
In proceedings 
Article 
PhD thesis 
Other 

Links

Homepages:

On csauthors.net:

Bibliography

2018
Min-Sum Bin Packing.
J. Comb. Optim., 2018

Wireless coverage prediction via parametric shortest paths.
Proceedings of the Nineteenth ACM International Symposium on Mobile Ad Hoc Networking and Computing, 2018

2016
Vector Bin Packing.
Encyclopedia of Algorithms, 2016

Bin Packing.
Encyclopedia of Algorithms, 2016

Implementation Challenge for Shortest Paths.
Encyclopedia of Algorithms, 2016

Rethinking Experimental Methods in Computing (Dagstuhl Seminar 16111).
Dagstuhl Reports, 2016

2015
A Little Honesty Goes a Long Way - The Two-Tier Model for Secure Multiparty Computation.
Proceedings of the Theory of Cryptography - 12th Theory of Cryptography Conference, 2015

2014
A Little Honesty Goes a Long Way: The Two-Tier Model for Secure Multiparty Computation.
IACR Cryptology ePrint Archive, 2014

2013
Algorithm Engineering (Dagstuhl Seminar 13391).
Dagstuhl Reports, 2013

Resource-based corruptions and the combinatorics of hidden diversity.
Proceedings of the Innovations in Theoretical Computer Science, 2013

2011
Disjoint-Path Facility Location: Theory and Practice.
Proceedings of the Thirteenth Workshop on Algorithm Engineering and Experiments, 2011

2010
10261 Executive Summary - Algorithm Engineering.
Proceedings of the Algorithm Engineering, 27.06. - 02.07.2010, 2010

10261 Abstracts Collection - Algorithm Engineering.
Proceedings of the Algorithm Engineering, 27.06. - 02.07.2010, 2010

2008
Bin Packing.
Proceedings of the Encyclopedia of Algorithms, 2008

Implementation Challenge for Shortest Paths.
Proceedings of the Encyclopedia of Algorithms, 2008

Special issue on computational methods for graph coloring and its generalizations.
Discrete Applied Mathematics, 2008

2007
The NP-completeness column: Finding needles in haystacks.
ACM Trans. Algorithms, 2007

Compressing rectilinear pictures and minimizing access control lists.
Proceedings of the Eighteenth Annual ACM-SIAM Symposium on Discrete Algorithms, 2007

What is the science in experimental computer science?
Proceedings of the Workshop on Experimental Computer Science, 2007

2006
The NP-completeness column: The many limits on approximation.
ACM Trans. Algorithms, 2006

2005
vLOD: High-Fidelity Walkthrough of Large Virtual Environments.
IEEE Trans. Vis. Comput. Graph., 2005

The NP-completeness column.
ACM Trans. Algorithms, 2005

2004
Compressing Large Boolean Matrices using Reordering Techniques.
Proceedings of the (e)Proceedings of the Thirtieth International Conference on Very Large Data Bases, Toronto, Canada, August 31, 2004

2003
The geometric maximum traveling salesman problem.
J. ACM, 2003

The Cutting-Stock Approach to Bin Packing: Theory and Experiments.
Proceedings of the Fifth Workshop on Algorithm Engineering and Experiments, 2003

2002
Perfect Packing Theorems and the Average-Case Behavior of Optimal and Online Bin Packing.
SIAM Review, 2002

2001
Better approximation algorithms for bin covering.
Proceedings of the Twelfth Annual Symposium on Discrete Algorithms, 2001

The Asymmetric Traveling Salesman Problem: Algorithms, Instance Generators, and Tests.
Proceedings of the Algorithm Engineering and Experimentation, Third International Workshop, 2001

2000
Bin Packing with Discrete Item Sizes, Part I: Perfect Packing Theorems and the Average Case Behavior of Optimal Packings.
SIAM J. Discrete Math., 2000

On the sum-of-squares algorithm for bin packing.
Proceedings of the Thirty-Second Annual ACM Symposium on Theory of Computing, 2000

The prize collecting Steiner tree problem: theory and practice.
Proceedings of the Eleventh Annual ACM-SIAM Symposium on Discrete Algorithms, 2000

1999
What are the Least Tractable Instances of max Tndependent Set?
Proceedings of the Tenth Annual ACM-SIAM Symposium on Discrete Algorithms, 1999

A theoretician's guide to the experimental analysis of algorithms.
Proceedings of the Data Structures, 1999

A Self Organizing Bin Packing Heuristic.
Proceedings of the Algorithm Engineering and Experimentation, 1999

1998
The Maximum Traveling Salesman Problem Under Polyhedral Norms.
Proceedings of the Integer Programming and Combinatorial Optimization, 1998

1997
Strategic directions in research in theory of computing.
SIGACT News, 1997

Emerging opportunities for theoretical computer science.
SIGACT News, 1997

Bin packing with discrete item sizes, part II: Tight bounds on First Fit.
Random Struct. Algorithms, 1997

Near-optimal Intraprocedural Branch Alignment.
Proceedings of the ACM SIGPLAN '97 Conference on Programming Language Design and Implementation (PLDI), 1997

1996
A Brief History of SIGACT News and its Editors.
SIGACT News, 1996

How to do experiments (extended advertisement).
SIGACT News, 1996

Asymptotic Experimental Analysis for the Held-Karp Traveling Salesman Bound.
Proceedings of the Seventh Annual ACM-SIAM Symposium on Discrete Algorithms, 1996

1994
The Complexity of Multiterminal Cuts.
SIAM J. Comput., 1994

Minimizing Channel Density by Lateral Shifting of Components.
Proceedings of the Fifth Annual ACM-SIAM Symposium on Discrete Algorithms. 23-25 January 1994, 1994

The Traveling Salesman Problem: A report on the State of the Art.
Proceedings of the Technology and Foundations - Information Processing '94, Volume 1, Proceedings of the IFIP 13th World Computer Congress, Hamburg, Germany, 28 August, 1994

1993
Performance of the Efficient Data-Driven Evaluation Scheme.
J. Parallel Distrib. Comput., 1993

Markov chains, computer proofs, and average-case analysis of best fit bin packing.
Proceedings of the Twenty-Fifth Annual ACM Symposium on Theory of Computing, 1993

Data Structures for Traveling Salesmen.
Proceedings of the Fourth Annual ACM/SIGACT-SIAM Symposium on Discrete Algorithms, 1993

Foreword xiIntroduction to the Second DIMACS Challenge: Cliques, coloring, and satisfiability.
Proceedings of the Cliques, 1993

1992
The NP-Completeness Column: An Ongoing Guide.
J. Algorithms, 1992

The Complexity of Multiway Cuts (Extended Abstract)
Proceedings of the 24th Annual ACM Symposium on Theory of Computing, 1992

1991
Optimization by Simulated Annealing: An Experimental Evaluation; Part II, Graph Coloring and Number Partitioning.
Operations Research, 1991

Fundamental Discrepancies between Average-Case Analyses under Discrete and Continuous Distributions: A Bin Packing Case Study
Proceedings of the 23rd Annual ACM Symposium on Theory of Computing, 1991

Bounded Space On-Line Bin Packing: Best is Better than First.
Proceedings of the Second Annual ACM/SIGACT-SIAM Symposium on Discrete Algorithms, 1991

Preface.
Proceedings of the Network Flows And Matching, 1991

Appendix B: Panel Discussion Highlights.
Proceedings of the Network Flows And Matching, 1991

1990
A stoc/focs bibliography: the last progress report.
SIGACT News, 1990

The NP-Completeness Column: An Ongoing Guide.
J. Algorithms, 1990

Generalized Planar Matching.
J. Algorithms, 1990

Unit disk graphs.
Discrete Mathematics, 1990

Data Structures for Traveling Salesmen (Abstract).
Proceedings of the SWAT 90, 1990

Local Optimization and the Traveling Salesman Problem.
Proceedings of the Automata, Languages and Programming, 17th International Colloquium, 1990

A Catalog of Complexity Classes.
Handbook of Theoretical Computer Science, Volume A: Algorithms and Complexity (A), 1990

1989
Optimization by Simulated Annealing: An Experimental Evaluation; Part I, Graph Partitioning.
Operations Research, 1989

1988
How Easy is Local Search?
J. Comput. Syst. Sci., 1988

The NP-Completeness Column: An Ongoing Guide.
J. Algorithms, 1988

The complexity of searching a graph.
J. ACM, 1988

On Generating All Maximal Independent Sets.
Inf. Process. Lett., 1988

1987
Hypergraph planarity and the complexity of drawing venn diagrams.
Journal of Graph Theory, 1987

Bin packing with divisible item sizes.
J. Complexity, 1987

The NP-Completeness Column: An Ongoing Guide.
J. Algorithms, 1987

The NP-Completeness Column: An Ongoing Guide.
J. Algorithms, 1987

1986
The NP-Completeness Column: An Ongoing Guide.
J. Algorithms, 1986

The NP-Completeness Column: An Ongoing Guide.
J. Algorithms, 1986

1985
Composing Functions to Minimize Image Size.
SIAM J. Comput., 1985

Scheduling File Transfers.
SIAM J. Comput., 1985

A 71/60 theorem for bin packing.
J. Complexity, 1985

The NP-Completeness Column: An Ongoing Guide.
J. Algorithms, 1985

The NP-Completeness Column: An Ongoing Guide.
J. Algorithms, 1985

The NP-Completeness Column: An Ongoing Guide.
J. Algorithms, 1985

How Easy Is Local Search? (Extended Abstract)
Proceedings of the 26th Annual Symposium on Foundations of Computer Science, 1985

1984
The NP-Completeness Column: An Ongoing Guide.
J. Algorithms, 1984

The NP-Completeness Column: An Ongoing Guide.
J. Algorithms, 1984

The NP-Completeness Column: An Ongoing Guide.
J. Algorithms, 1984

The NP-Completeness Column: An Ongoing Guide.
J. Algorithms, 1984

On a Dual Version of the One-Dimensional Bin Packing Problem.
J. Algorithms, 1984

Some Unexpected Expected Behavior Results for Bin Packing
Proceedings of the 16th Annual ACM Symposium on Theory of Computing, April 30, 1984

1983
Optimizing Conjunctive Queries that Contain Untyped Variables.
SIAM J. Comput., 1983

Dynamic Bin Packing.
SIAM J. Comput., 1983

The NP-Completeness Column: An Ongoing Guide.
J. Algorithms, 1983

The NP-Completeness Column: An Ongoing Guide.
J. Algorithms, 1983

The NP-Completeness Column: An Ongoing Guide.
J. Algorithms, 1983

The NP-Completeness Column: An Ongoing Guide.
J. Algorithms, 1983

Scheduling File Transfers in a Distributed Network.
Proceedings of the Second Annual ACM SIGACT-SIGOPS Symposium on Principles of Distributed Computing, 1983

1982
The complexity of the generalized Lloyd - Max problem.
IEEE Trans. Information Theory, 1982

The NP-Completeness Column: An Ongoing Guide.
J. Algorithms, 1982

The NP-Completeness Column: An Ongoing Guide.
J. Algorithms, 1982

The NP-Completeness Column: An Ongoing Guide.
J. Algorithms, 1982

The NP-Completeness Column: An Ongoing Guide.
J. Algorithms, 1982

Testing Containment of Conjunctive Queries Under Functional and Inclusion Dependencies.
Proceedings of the ACM Symposium on Principles of Database Systems, 1982

1981
Scheduling Unit-Time Tasks with Arbitrary Release Times and Deadlines.
SIAM J. Comput., 1981

The NP-Completeness Column: An Ongoing Guide.
J. Algorithms, 1981

The Complexity of Searching a Graph (Preliminary Version)
Proceedings of the 22nd Annual Symposium on Foundations of Computer Science, 1981

Optimizing Conjunctive Queries When Attribute Domains Are not Disjoint (Extended Abstract)
Proceedings of the 22nd Annual Symposium on Foundations of Computer Science, 1981

1980
The Complexity of Coloring Circular Arcs and Chords.
SIAM J. Matrix Analysis Applications, 1980

Performance Bounds for Level-Oriented Two-Dimensional Packing Algorithms.
SIAM J. Comput., 1980

1979
Computers and Intractability: A Guide to the Theory of NP-Completeness.
W. H. Freeman, ISBN: 0-7167-1044-7, 1979

1978
The Densest Hemisphere Problem.
Theor. Comput. Sci., 1978

An Application of Bin-Packing to Multiprocessor Scheduling.
SIAM J. Comput., 1978

The complexity of the network design problem.
Networks, 1978

A note on bisecting minimum spanning trees.
Networks, 1978

"Strong" NP-Completeness Results: Motivation, Examples, and Implications.
J. ACM, 1978

Triangulating a Simple Polygon.
Inf. Process. Lett., 1978

Performance Guarantees for Scheduling Algorithms.
Operations Research, 1978

The Complexity of Checkers on an N * N Board - Preliminary Report
Proceedings of the 19th Annual Symposium on Foundations of Computer Science, 1978

1977
Algorithms for a Set Partitioning Problem Arising in the Design of Multipurpose Units.
IEEE Trans. Computers, 1977

Two-Processor Scheduling with Start-Times and Deadlines.
SIAM J. Comput., 1977

The Rectilinear Steiner Tree Problem in NP Complete.
SIAM Journal of Applied Mathematics, 1977

Scheduling Equal-Length Tasks Under Treelike Precedence Constraints to Minimize Maximum Lateness.
Math. Oper. Res., 1977

1976
Some Simplified NP-Complete Graph Problems.
Theor. Comput. Sci., 1976

The Planar Hamiltonian Circuit Problem is NP-Complete.
SIAM J. Comput., 1976

The Complexity of Flowshop and Jobshop Scheduling.
Math. Oper. Res., 1976

Resource Constrained Scheduling as Generalized Bin Packing.
J. Comb. Theory, Ser. A, 1976

Scheduling Tasks with Nonuniform Deadlines on Two Processors.
J. ACM, 1976

The Complexity of Near-Optimal Graph Coloring.
J. ACM, 1976

Some NP-Complete Geometric Problems
Proceedings of the 8th Annual ACM Symposium on Theory of Computing, 1976

1975
Complexity Results for Multiprocessor Scheduling under Resource Constraints.
SIAM J. Comput., 1975

An Application of Graph Coloring to Printed Circuit Testing (Working Paper)
Proceedings of the 16th Annual Symposium on Foundations of Computer Science, 1975

1974
Worst-Case Performance Bounds for Simple One-Dimensional Packing Algorithms.
SIAM J. Comput., 1974

Approximation Algorithms for Combinatorial Problems.
J. Comput. Syst. Sci., 1974

Fast Algorithms for Bin Packing.
J. Comput. Syst. Sci., 1974

Some Simplified NP-Complete Problems
Proceedings of the 6th Annual ACM Symposium on Theory of Computing, April 30, 1974

1973
Approximation Algorithms for Combinatorial Problems
Proceedings of the 5th Annual ACM Symposium on Theory of Computing, April 30, 1973

1972
Fast Allocation Algorithms
Proceedings of the 13th Annual Symposium on Switching and Automata Theory, 1972


  Loading...