David S. Johnson

Affiliations:
  • Columbia University, Computer Science Department, New York, NY, USA
  • AT&T Labs, Florham Park, NJ, USA
  • AT&T Bell Labs, Murray Hill, NJ, USA


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

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 
Dataset
Other 

Links

Online presence:

On csauthors.net:

Bibliography

2023
Towards Interpretability in Audio and Visual Affective Machine Learning: A Review.
CoRR, 2023

2021

DESED-FL and URBAN-FL: Federated Learning Datasets for Sound Event Detection.
Proceedings of the 29th European Signal Processing Conference, 2021

2020
The combinatorics of hidden diversity.
Theor. Comput. Sci., 2020

Near-Optimal Disjoint-Path Facility Location Through Set Cover by Pairs.
Oper. Res., 2020

Techniques Improving the Robustness of Deep Learning Models for Industrial Sound Analysis.
Proceedings of the 28th European Signal Processing Conference, 2020

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

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

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

2012
Resource-based Corruptions and the Combinatorics of Hidden Diversity.
IACR Cryptol. ePrint Arch., 2012

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 Edition, 2008

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

Special issue on computational methods for graph coloring and its generalizations.
Discret. Appl. Math., 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

On the Sum-of-Squares algorithm for bin packing.
J. ACM, 2006

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

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

On the Worst-case Performance of the Sum-of-Squares Algorithm for Bin Packing
CoRR, 2005

2004
Compressing Large Boolean Matrices using Reordering Techniques.
Proceedings of the (e)Proceedings of the Thirtieth International Conference on Very Large Data Bases, VLDB 2004, 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 Rev., 2002

2001
Bounded Space On-Line Bin Packing: Best Is Better than First.
Algorithmica, 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. Discret. Math., 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 Independent 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

1995
Data Structures for Traveling Salesmen.
J. Algorithms, 1995

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

Simulation study of the capacity bounds in cellular systems.
Proceedings of the 5th IEEE International Symposium on Personal, 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 Distributed 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

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

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.
Oper. Res., 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

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

Generalized Planar Matching.
J. Algorithms, 1990

Unit disk graphs.
Discret. Math., 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.
Proceedings of the Handbook of Theoretical Computer Science, 1990

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

Application of VLSI for image processing.
Proceedings of the IEEE International Conference on Acoustics, 1989

1988
How Easy is Local Search?
J. Comput. Syst. Sci., 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.
J. Graph Theory, 1987

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

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. Complex., 1985

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

1984
The genealogy of theoretical computer science: a preliminary report.
SIGACT News, 1984

Testing Containment of Conjunctive Queries under Functional and Inclusion Dependencies.
J. Comput. Syst. Sci., 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

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

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

1981
Scheduling Unit-Time Tasks with Arbitrary Release Times and Deadlines.
SIAM J. Comput., 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. Algebraic Discret. Methods, 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

A note on "A note on 'Some simplified NP-complete graph problems'".
SIGACT News, 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.
Oper. Res., 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 is 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

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


  Loading...