David S. Johnson

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

Collaborative distances:

• Dijkstra number of three.
• Erdős number of two.

2023

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

David S. Johnson, Olya Hakobyan, Hanna Drimalla

CoRR, 2023

2021

SEC-Learn: Sensor Edge Cloud for Federated Learning - Invited Paper.

Patrick Aichroth, Christoph Antes, Pierre Gembatzka, Holger Graf, David S. Johnson, Matthias Jung, Thomas Kämpfe, Thomas Kleinberger, Thomas Köllmer, Thomas Kuhn, Christoph Kutter, Jens Krüger, Dominik Marek Loroch, Hanna M. Lukashevich, Nellie Laleni, Lei Zhang, Johannes Leugering, Rodrigo Martín Fernández, Loreto Mateu, Shaown Mojumder, Benjamin Prautsch, Ferdinand Pscheidl, Karsten Roscher, Sören Schneickert, Frank Vanselow, Paul Wallbott, Oliver Walter, Nico Weber

Proceedings of the Embedded Computer Systems: Architectures, Modeling, and Simulation, 2021

DESED-FL and URBAN-FL: Federated Learning Datasets for Sound Event Detection.

David S. Johnson, Wolfgang Lorenz, Michael Taenzer, Stylianos I. Mimilakis, Sascha Grollmisch, Jakob Abeßer, Hanna M. Lukashevich

Proceedings of the 29th European Signal Processing Conference, 2021

2020

The combinatorics of hidden diversity.

Juan A. Garay, David S. Johnson, Aggelos Kiayias, Moti Yung

Theor. Comput. Sci., 2020

Near-Optimal Disjoint-Path Facility Location Through Set Cover by Pairs.

David S. Johnson, Lee Breslau, Ilias Diakonikolas, Nick Duffield, Yu Gu, MohammadTaghi Hajiaghayi, Howard J. Karloff, Mauricio G. C. Resende, Subhabrata Sen

Oper. Res., 2020

Techniques Improving the Robustness of Deep Learning Models for Industrial Sound Analysis.

David S. Johnson, Sascha Grollmisch

Proceedings of the 28th European Signal Processing Conference, 2020

2018

Min-Sum Bin Packing.

Leah Epstein, David S. Johnson, Asaf Levin

J. Comb. Optim., 2018

Wireless coverage prediction via parametric shortest paths.

David L. Applegate, Aaron Archer, David S. Johnson, Evdokia Nikolova, Mikkel Thorup, Ger Yang

Proceedings of the Nineteenth ACM International Symposium on Mobile Ad Hoc Networking and Computing, 2018

2016

Vector Bin Packing.

David S. Johnson

Encyclopedia of Algorithms, 2016

Bin Packing.

David S. Johnson

Encyclopedia of Algorithms, 2016

Implementation Challenge for Shortest Paths.

Camil Demetrescu, Andrew V. Goldberg, David S. Johnson

Encyclopedia of Algorithms, 2016

Rethinking Experimental Methods in Computing (Dagstuhl Seminar 16111).

Daniel Delling, Camil Demetrescu, David S. Johnson, Jan Vitek

Dagstuhl Reports, 2016

2014

A Little Honesty Goes a Long Way: The Two-Tier Model for Secure Multiparty Computation.

Juan A. Garay, Ran Gelles, David S. Johnson, Aggelos Kiayias, Moti Yung

IACR Cryptol. ePrint Arch., 2014

2013

Algorithm Engineering (Dagstuhl Seminar 13391).

Andrew V. Goldberg, Giuseppe F. Italiano, David S. Johnson, Dorothea Wagner

Dagstuhl Reports, 2013

2012

Resource-based Corruptions and the Combinatorics of Hidden Diversity.

Juan A. Garay, David S. Johnson, Aggelos Kiayias, Moti Yung

IACR Cryptol. ePrint Arch., 2012

2011

Disjoint-Path Facility Location: Theory and Practice.

Lee Breslau, Ilias Diakonikolas, Nick G. Duffield, Yu Gu, Mohammad Taghi Hajiaghayi, David S. Johnson, Howard J. Karloff, Mauricio G. C. Resende, Subhabrata Sen

Proceedings of the Thirteenth Workshop on Algorithm Engineering and Experiments, 2011

2010

10261 Executive Summary - Algorithm Engineering.

Giuseppe F. Italiano, David S. Johnson, Petra Mutzel, Peter Sanders

Proceedings of the Algorithm Engineering, 27.06. - 02.07.2010, 2010

10261 Abstracts Collection - Algorithm Engineering.

Giuseppe F. Italiano, David S. Johnson, Petra Mutzel, Peter Sanders

Proceedings of the Algorithm Engineering, 27.06. - 02.07.2010, 2010

2008

Bin Packing.

David S. Johnson

Proceedings of the Encyclopedia of Algorithms - 2008 Edition, 2008

Implementation Challenge for Shortest Paths.

Camil Demetrescu, Andrew V. Goldberg, David S. Johnson

Proceedings of the Encyclopedia of Algorithms - 2008 Edition, 2008

Special issue on computational methods for graph coloring and its generalizations.

David S. Johnson, Anuj Mehrotra, Michael A. Trick

Discret. Appl. Math., 2008

2007

The NP-completeness column: Finding needles in haystacks.

David S. Johnson

ACM Trans. Algorithms, 2007

Compressing rectilinear pictures and minimizing access control lists.

David L. Applegate, Gruia Calinescu, David S. Johnson, Howard J. Karloff, Katrina Ligett, Jia Wang

Proceedings of the Eighteenth Annual ACM-SIAM Symposium on Discrete Algorithms, 2007

What is the science in experimental computer science?

David S. Johnson

Proceedings of the Workshop on Experimental Computer Science, 2007

2006

The NP-completeness column: The many limits on approximation.

David S. Johnson

ACM Trans. Algorithms, 2006

On the Sum-of-Squares algorithm for bin packing.

János Csirik, David S. Johnson, Claire Kenyon, James B. Orlin, Peter W. Shor, Richard R. Weber

J. ACM, 2006

2005

vLOD: High-Fidelity Walkthrough of Large Virtual Environments.

Jatin Chhugani, Budirijanto Purnomo, Shankar Krishnan, Jonathan D. Cohen, Suresh Venkatasubramanian, David S. Johnson, Subodh Kumar

IEEE Trans. Vis. Comput. Graph., 2005

The NP-completeness column.

David S. Johnson

ACM Trans. Algorithms, 2005

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

János Csirik, David S. Johnson, Claire Kenyon

CoRR, 2005

2004

Compressing Large Boolean Matrices using Reordering Techniques.

David S. Johnson, Shankar Krishnan, Jatin Chhugani, Subodh Kumar, Suresh Venkatasubramanian

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.

Alexander I. Barvinok, Sándor P. Fekete, David S. Johnson, Arie Tamir, Gerhard J. Woeginger, Russell Woodroofe

J. ACM, 2003

The Cutting-Stock Approach to Bin Packing: Theory and Experiments.

David L. Applegate, Luciana S. Buriol, Bernard L. Dillard, David S. Johnson, Peter W. Shor

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.

Edward G. Coffman Jr., Costas Courcoubetis, Michael R. Garey, David S. Johnson, Peter W. Shor, Richard R. Weber, Mihalis Yannakakis

SIAM Rev., 2002

2001

Bounded Space On-Line Bin Packing: Best Is Better than First.

János Csirik, David S. Johnson

Algorithmica, 2001

Better approximation algorithms for bin covering.

János Csirik, David S. Johnson, Claire Kenyon

Proceedings of the Twelfth Annual Symposium on Discrete Algorithms, 2001

The Asymmetric Traveling Salesman Problem: Algorithms, Instance Generators, and Tests.

Jill Cirasella, David S. Johnson, Lyle A. McGeoch, Weixiong Zhang

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.

Edward G. Coffman Jr., Costas Courcoubetis, M. R. Garey, David S. Johnson, Peter W. Shor, Richard R. Weber, Mihalis Yannakakis

SIAM J. Discret. Math., 2000

The prize collecting Steiner tree problem: theory and practice.

David S. Johnson, Maria Minkoff, Steven Phillips

Proceedings of the Eleventh Annual ACM-SIAM Symposium on Discrete Algorithms, 2000

1999

What are the Least Tractable Instances of max Independent Set?

David S. Johnson, Mario Szegedy

Proceedings of the Tenth Annual ACM-SIAM Symposium on Discrete Algorithms, 1999

A theoretician's guide to the experimental analysis of algorithms.

David S. Johnson

Proceedings of the Data Structures, 1999

A Self Organizing Bin Packing Heuristic.

János Csirik, David S. Johnson, Claire Kenyon, Peter W. Shor, Richard R. Weber

Proceedings of the Algorithm Engineering and Experimentation, 1999

1998

The Maximum Traveling Salesman Problem Under Polyhedral Norms.

Alexander I. Barvinok, David S. Johnson, Gerhard J. Woeginger, Russell Woodroofe

Proceedings of the Integer Programming and Combinatorial Optimization, 1998

1997

Strategic directions in research in theory of computing.

Anne Condon, Faith E. 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

SIGACT News, 1997

Emerging opportunities for theoretical computer science.

Alfred V. Aho, David S. Johnson, Richard M. Karp, S. Rao Kosaraju, Catherine C. McGeoch, Christos H. Papadimitriou, Pavel A. Pevzner

SIGACT News, 1997

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

Edward G. Coffman Jr., David S. Johnson, Peter W. Shor, Richard R. Weber

Random Struct. Algorithms, 1997

Near-optimal Intraprocedural Branch Alignment.

Cliff Young, David S. Johnson, David R. Karger, Michael D. Smith

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.

David S. Johnson

SIGACT News, 1996

How to do experiments (extended advertisement).

David S. Johnson

SIGACT News, 1996

Asymptotic Experimental Analysis for the Held-Karp Traveling Salesman Bound.

David S. Johnson, Lyle A. McGeoch, Edward E. Rothberg

Proceedings of the Seventh Annual ACM-SIAM Symposium on Discrete Algorithms, 1996

1995

Data Structures for Traveling Salesmen.

Michael L. Fredman, David S. Johnson, Lyle A. McGeoch, G. Ostheimer

J. Algorithms, 1995

1994

The Complexity of Multiterminal Cuts.

Elias Dahlhaus, David S. Johnson, Christos H. Papadimitriou, Paul D. Seymour, Mihalis Yannakakis

SIAM J. Comput., 1994

Minimizing Channel Density by Lateral Shifting of Components.

David S. Johnson, Andrea S. LaPaugh, Ron Y. Pinter

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.

Zygmunt J. Haas, Jack H. Winters, David S. Johnson

Proceedings of the 5th IEEE International Symposium on Personal, 1994

The Traveling Salesman Problem: A report on the State of the Art.

David S. Johnson

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.

David S. Johnson, Francine Berman

J. Parallel Distributed Comput., 1993

Markov chains, computer proofs, and average-case analysis of best fit bin packing.

Edward G. Coffman Jr., David S. Johnson, Peter W. Shor, Richard R. Weber

Proceedings of the Twenty-Fifth Annual ACM Symposium on Theory of Computing, 1993

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

David S. Johnson, Michael A. Trick

Proceedings of the Cliques, 1993

1992

The Complexity of Multiway Cuts (Extended Abstract)

Elias Dahlhaus, David S. Johnson, Christos H. Papadimitriou, Paul D. Seymour, Mihalis Yannakakis

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.

David S. Johnson, Cecilia R. Aragon, Lyle A. McGeoch, Catherine Schevon

Oper. Res., 1991

Fundamental Discrepancies between Average-Case Analyses under Discrete and Continuous Distributions: A Bin Packing Case Study

Edward G. Coffman Jr., Costas Courcoubetis, M. R. Garey, David S. Johnson, Lyle A. McGeoch, Peter W. Shor, Richard R. Weber, Mihalis Yannakakis

Proceedings of the 23rd Annual ACM Symposium on Theory of Computing, 1991

Preface.

David S. Johnson, Catherine C. McGeoch

Proceedings of the Network Flows And Matching, 1991

Appendix B: Panel Discussion Highlights.

David S. Johnson

Proceedings of the Network Flows And Matching, 1991

1990

A stoc/focs bibliography: the last progress report.

David S. Johnson

SIGACT News, 1990

Generalized Planar Matching.

Francine Berman, David S. Johnson, Frank Thomson Leighton, Peter W. Shor, Larry Snyder

J. Algorithms, 1990

Unit disk graphs.

Brent N. Clark, Charles J. Colbourn, David S. Johnson

Discret. Math., 1990

Data Structures for Traveling Salesmen (Abstract).

David S. Johnson

Proceedings of the SWAT 90, 1990

Local Optimization and the Traveling Salesman Problem.

David S. Johnson

Proceedings of the Automata, Languages and Programming, 17th International Colloquium, 1990

A Catalog of Complexity Classes.

David S. Johnson

Proceedings of the Handbook of Theoretical Computer Science, 1990

1989

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

David S. Johnson, Cecilia R. Aragon, Lyle A. McGeoch, Catherine Schevon

Oper. Res., 1989

Application of VLSI for image processing.

Richard C. Jaffe, David S. Johnson, Wen-Tai Lin, Chung-Yin Ho

Proceedings of the IEEE International Conference on Acoustics, 1989

1988

How Easy is Local Search?

David S. Johnson, Christos H. Papadimitriou, Mihalis Yannakakis

J. Comput. Syst. Sci., 1988

The complexity of searching a graph.

Nimrod Megiddo, S. Louis Hakimi, M. R. Garey, David S. Johnson, Christos H. Papadimitriou

J. ACM, 1988

On Generating All Maximal Independent Sets.

David S. Johnson, Christos H. Papadimitriou, Mihalis Yannakakis

Inf. Process. Lett., 1988

1987

Hypergraph planarity and the complexity of drawing venn diagrams.

David S. Johnson, Henry O. Pollak

J. Graph Theory, 1987

Bin packing with divisible item sizes.

Edward G. Coffman Jr., M. R. Garey, David S. Johnson

J. Complex., 1987

1985

Composing Functions to Minimize Image Size.

M. R. Garey, David S. Johnson

SIAM J. Comput., 1985

Scheduling File Transfers.

Edward G. Coffman Jr., M. R. Garey, David S. Johnson, Andrea S. LaPaugh

SIAM J. Comput., 1985

A 71/60 theorem for bin packing.

David S. Johnson, M. R. Garey

J. Complex., 1985

How Easy Is Local Search? (Extended Abstract)

David S. Johnson, Christos H. Papadimitriou, Mihalis Yannakakis

Proceedings of the 26th Annual Symposium on Foundations of Computer Science, 1985

1984

The genealogy of theoretical computer science: a preliminary report.

David S. Johnson

SIGACT News, 1984

Testing Containment of Conjunctive Queries under Functional and Inclusion Dependencies.

David S. Johnson, Anthony C. Klug

J. Comput. Syst. Sci., 1984

The NP-Completeness Column: An Ongoing Guide.

David S. Johnson

J. Algorithms, 1984

On a Dual Version of the One-Dimensional Bin Packing Problem.

Susan F. Assmann, David S. Johnson, Daniel J. Kleitman, Joseph Y.-T. Leung

J. Algorithms, 1984

Some Unexpected Expected Behavior Results for Bin Packing

Jon Louis Bentley, David S. Johnson, Frank Thomson Leighton, Catherine C. McGeoch, Lyle A. McGeoch

Proceedings of the 16th Annual ACM Symposium on Theory of Computing, April 30, 1984

1983

Optimizing Conjunctive Queries that Contain Untyped Variables.

David S. Johnson, Anthony C. Klug

SIAM J. Comput., 1983

Dynamic Bin Packing.

Edward G. Coffman Jr., M. R. Garey, David S. Johnson

SIAM J. Comput., 1983

Scheduling File Transfers in a Distributed Network.

Edward G. Coffman Jr., M. R. Garey, David S. Johnson, Andrea S. LaPaugh

Proceedings of the Second Annual ACM Symposium on Principles of Distributed Computing, 1983

1982

The complexity of the generalized Lloyd - Max problem.

M. R. Garey, David S. Johnson, Hans S. Witsenhausen

IEEE Trans. Inf. Theory, 1982

1981

Scheduling Unit-Time Tasks with Arbitrary Release Times and Deadlines.

M. R. Garey, David S. Johnson, Barbara B. Simons, Robert Endre Tarjan

SIAM J. Comput., 1981

The Complexity of Searching a Graph (Preliminary Version)

Nimrod Megiddo, S. Louis Hakimi, M. R. Garey, David S. Johnson, Christos H. Papadimitriou

Proceedings of the 22nd Annual Symposium on Foundations of Computer Science, 1981

Optimizing Conjunctive Queries When Attribute Domains Are not Disjoint (Extended Abstract)

David S. Johnson, Anthony C. Klug

Proceedings of the 22nd Annual Symposium on Foundations of Computer Science, 1981

1980

The Complexity of Coloring Circular Arcs and Chords.

M. R. Garey, David S. Johnson, Gerald L. Miller, Christos H. Papadimitriou

SIAM J. Algebraic Discret. Methods, 1980

Performance Bounds for Level-Oriented Two-Dimensional Packing Algorithms.

Edward G. Coffman Jr., M. R. Garey, David S. Johnson, Robert Endre Tarjan

SIAM J. Comput., 1980

1979

Computers and Intractability: A Guide to the Theory of NP-Completeness.

M. R. Garey, David S. Johnson

W. H. Freeman, ISBN: 0-7167-1044-7, 1979

1978

The Densest Hemisphere Problem.

David S. Johnson, Franco P. Preparata

Theor. Comput. Sci., 1978

A note on "A note on 'Some simplified NP-complete graph problems'".

Michael R. Garey, David S. Johnson

SIGACT News, 1978

An Application of Bin-Packing to Multiprocessor Scheduling.

Edward G. Coffman Jr., M. R. Garey, David S. Johnson

SIAM J. Comput., 1978

The complexity of the network design problem.

David S. Johnson, Jan Karel Lenstra, A. H. G. Rinnooy Kan

Networks, 1978

A note on bisecting minimum spanning trees.

William M. Boyce, M. R. Garey, David S. Johnson

Networks, 1978

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

M. R. Garey, David S. Johnson

J. ACM, 1978

Triangulating a Simple Polygon.

M. R. Garey, David S. Johnson, Franco P. Preparata, Robert Endre Tarjan

Inf. Process. Lett., 1978

Performance Guarantees for Scheduling Algorithms.

M. R. Garey, Ronald L. Graham, David S. Johnson

Oper. Res., 1978

The Complexity of Checkers on an N * N Board - Preliminary Report

Aviezri S. Fraenkel, M. R. Garey, David S. Johnson, T. Schaefer, Yaacov Yesha

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.

M. R. Garey, Frank K. Hwang, David S. Johnson

IEEE Trans. Computers, 1977

Two-Processor Scheduling with Start-Times and Deadlines.

M. R. Garey, David S. Johnson

SIAM J. Comput., 1977

The Rectilinear Steiner Tree Problem is NP Complete.

M. R. Garey, David S. Johnson

SIAM Journal of Applied Mathematics, 1977

Scheduling Equal-Length Tasks Under Treelike Precedence Constraints to Minimize Maximum Lateness.

Peter Brucker, Michael R. Garey, David S. Johnson

Math. Oper. Res., 1977

1976

Some Simplified NP-Complete Graph Problems.

M. R. Garey, David S. Johnson, Larry J. Stockmeyer

Theor. Comput. Sci., 1976

The Planar Hamiltonian Circuit Problem is NP-Complete.

M. R. Garey, David S. Johnson, Robert Endre Tarjan

SIAM J. Comput., 1976

The Complexity of Flowshop and Jobshop Scheduling.

Michael R. Garey, David S. Johnson, Ravi Sethi

Math. Oper. Res., 1976

Resource Constrained Scheduling as Generalized Bin Packing.

M. R. Garey, Ronald L. Graham, David S. Johnson, Andrew Chi-Chih Yao

J. Comb. Theory A, 1976

Scheduling Tasks with Nonuniform Deadlines on Two Processors.

M. R. Garey, David S. Johnson

J. ACM, 1976

The Complexity of Near-Optimal Graph Coloring.

M. R. Garey, David S. Johnson

J. ACM, 1976

Some NP-Complete Geometric Problems

M. R. Garey, Ronald L. Graham, David S. Johnson

Proceedings of the 8th Annual ACM Symposium on Theory of Computing, 1976

1975

Complexity Results for Multiprocessor Scheduling under Resource Constraints.

M. R. Garey, David S. Johnson

SIAM J. Comput., 1975

An Application of Graph Coloring to Printed Circuit Testing (Working Paper)

M. R. Garey, David S. Johnson, H. C. So

Proceedings of the 16th Annual Symposium on Foundations of Computer Science, 1975

1974

Worst-Case Performance Bounds for Simple One-Dimensional Packing Algorithms.

David S. Johnson, Alan J. Demers, Jeffrey D. Ullman, M. R. Garey, Ronald L. Graham

SIAM J. Comput., 1974

Approximation Algorithms for Combinatorial Problems.

David S. Johnson

J. Comput. Syst. Sci., 1974

Fast Algorithms for Bin Packing.

David S. Johnson

J. Comput. Syst. Sci., 1974

Some Simplified NP-Complete Problems

M. R. Garey, David S. Johnson, Larry J. Stockmeyer

Proceedings of the 6th Annual ACM Symposium on Theory of Computing, April 30, 1974

1972

Fast Allocation Algorithms

David S. Johnson

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