David S. Johnson
Publication record assembled from the DBLP archive of ranked conferences.
Papers indexed
37
Venues
15
Active years
1972–2024
Best venue rank
A*
Where they publish
Papers
37 indexed papers, newest first.
| Year | Venue | Title | Authors |
|---|---|---|---|
| 2024 | ACII | A Paradigm to Investigate Social Signals of Understanding and Their Susceptibility to Stress. | Jonas Paletschek, Jan Bleimling, David S. Johnson, Hanna Drimalla |
| 2018 | MOBIHOC | Wireless coverage prediction via parametric shortest paths. | David L. Applegate, Aaron Archer, David S. Johnson, Evdokia Nikolova, Mikkel Thorup, Ger Yang |
| 2015 | TCC | 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 |
| 2011 | ALENEX | 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 |
| 2007 | SODA | Compressing rectilinear pictures and minimizing access control lists. | David L. Applegate, Gruia Calinescu, David S. Johnson, Howard J. Karloff, Katrina Ligett, Jia Wang |
| 2004 | VLDB | Compressing Large Boolean Matrices using Reordering Techniques. | David S. Johnson, Shankar Krishnan, Jatin Chhugani, Subodh Kumar, Suresh Venkatasubramanian |
| 2003 | ALENEX | 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 |
| 2001 | ALENEX | The Asymmetric Traveling Salesman Problem: Algorithms, Instance Generators, and Tests. | Jill Cirasella, David S. Johnson, Lyle A. McGeoch, Weixiong Zhang |
| 2001 | SODA | Better approximation algorithms for bin covering. | Jnos Csirik, David S. Johnson, Claire Kenyon |
| 2000 | SODA | The prize collecting Steiner tree problem: theory and practice. | David S. Johnson, Maria Minkoff, Steven Phillips |
| 2000 | STOC | On the sum-of-squares algorithm for bin packing. | Jnos Csirik, David S. Johnson, Claire Kenyon, James B. Orlin, Peter W. Shor, Richard R. Weber |
| 1999 | ALENEX | A Self Organizing Bin Packing Heuristic. | Jnos Csirik, David S. Johnson, Claire Kenyon, Peter W. Shor, Richard R. Weber |
| 1999 | SODA | What are the Least Tractable Instances of max Independent Set? | David S. Johnson, Mario Szegedy |
| 1998 | IPCO | The Maximum Traveling Salesman Problem Under Polyhedral Norms. | Alexander I. Barvinok, David S. Johnson, Gerhard J. Woeginger, Russell Woodroofe |
| 1997 | PLDI | Near-optimal Intraprocedural Branch Alignment. | Cliff Young, David S. Johnson, David R. Karger, Michael D. Smith |
| 1996 | SODA | Asymptotic Experimental Analysis for the Held-Karp Traveling Salesman Bound. | David S. Johnson, Lyle A. McGeoch, Edward E. Rothberg |
| 1994 | PIMRC | Simulation study of the capacity bounds in cellular systems. | Zygmunt J. Haas, Jack H. Winters, David S. Johnson |
| 1994 | SODA | Minimizing Channel Density by Lateral Shifting of Components. | David S. Johnson, Andrea S. LaPaugh, Ron Y. Pinter |
| 1993 | SODA | Data Structures for Traveling Salesmen. | Michael L. Fredman, David S. Johnson, Lyle A. McGeoch, G. Ostheimer |
| 1993 | STOC | 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 |
| 1992 | STOC | The Complexity of Multiway Cuts (Extended Abstract) | Elias Dahlhaus, David S. Johnson, Christos H. Papadimitriou, Paul D. Seymour, Mihalis Yannakakis |
| 1991 | SODA | Bounded Space On-Line Bin Packing: Best is Better than First. | Jnos Csirik, David S. Johnson |
| 1991 | STOC | 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 |
| 1990 | ICALP | Local Optimization and the Traveling Salesman Problem. | David S. Johnson |
| 1989 | ICASSP | Application of VLSI for image processing. | Richard C. Jaffe, David S. Johnson, Wen-Tai Lin, Chung-Yin Ho |
| 1985 | FOCS | How Easy Is Local Search? (Extended Abstract) | David S. Johnson, Christos H. Papadimitriou, Mihalis Yannakakis |
| 1984 | STOC | Some Unexpected Expected Behavior Results for Bin Packing | Jon Louis Bentley, David S. Johnson, Frank Thomson Leighton, Catherine C. McGeoch, Lyle A. McGeoch |
| 1983 | PODC | Scheduling File Transfers in a Distributed Network. | Edward G. Coffman Jr., M. R. Garey, David S. Johnson, Andrea S. LaPaugh |
| 1982 | PODS | Testing Containment of Conjunctive Queries Under Functional and Inclusion Dependencies. | David S. Johnson, Anthony C. Klug |
| 1981 | FOCS | Optimizing Conjunctive Queries When Attribute Domains Are not Disjoint (Extended Abstract) | David S. Johnson, Anthony C. Klug |
| 1981 | FOCS | The Complexity of Searching a Graph (Preliminary Version) | Nimrod Megiddo, S. Louis Hakimi, M. R. Garey, David S. Johnson, Christos H. Papadimitriou |
| 1978 | FOCS | The Complexity of Checkers on an N * N Board - Preliminary Report | Aviezri S. Fraenkel, M. R. Garey, David S. Johnson, T. Schaefer, Yaacov Yesha |
| 1976 | STOC | Some NP-Complete Geometric Problems | M. R. Garey, Ronald L. Graham, David S. Johnson |
| 1975 | FOCS | An Application of Graph Coloring to Printed Circuit Testing (Working Paper) | M. R. Garey, David S. Johnson, Hing C. So |
| 1974 | STOC | Some Simplified NP-Complete Problems | M. R. Garey, David S. Johnson, Larry J. Stockmeyer |
| 1973 | STOC | Approximation Algorithms for Combinatorial Problems | David S. Johnson |
| 1972 | FOCS | Fast Allocation Algorithms | David S. Johnson |