| Hits ?▲ |
Authors |
Title |
Venue |
Year |
Link |
Author keywords |
| 1 | Lee Breslau, Ilias Diakonikolas, Nick G. Duffield, Yu Gu 0004, Mohammad Taghi Hajiaghayi, David S. Johnson, Howard J. Karloff, Mauricio G. C. Resende, Subhabrata Sen |
Disjoint-Path Facility Location: Theory and Practice.  |
ALENEX  |
2011 |
DBLP BibTeX RDF |
|
| 1 | David S. Johnson, Anuj Mehrotra, Michael A. Trick |
Special issue on computational methods for graph coloring and its generalizations. |
Discrete Applied Mathematics |
2008 |
DBLP DOI BibTeX RDF |
|
| 1 | David S. Johnson |
Bin Packing. |
Encyclopedia of Algorithms |
2008 |
DBLP DOI BibTeX RDF |
|
| 1 | Camil Demetrescu, Andrew V. Goldberg, David S. Johnson |
Implementation Challenge for Shortest Paths. |
Encyclopedia of Algorithms |
2008 |
DBLP DOI BibTeX RDF |
|
| 1 | David S. Johnson |
The NP-completeness column: Finding needles in haystacks. |
ACM Transactions on Algorithms |
2007 |
DBLP DOI BibTeX RDF |
PPAD, game theory, local search, Nash equilibrium, fixed point, PLS |
| 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 |
DBLP DOI BibTeX RDF |
|
| 1 | David S. Johnson |
What is the science in experimental computer science? |
Experimental Computer Science |
2007 |
DBLP DOI BibTeX RDF |
|
| 1 | 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 |
STOC |
2007 |
DBLP BibTeX RDF |
|
| 1 | David S. Johnson |
The NP-completeness column: The many limits on approximation. |
ACM Transactions on Algorithms |
2006 |
DBLP DOI BibTeX RDF |
label cover, Approximation algorithms, lower bounds, set cover, clique, probabilistically checkable proofs, Unique Games Conjecture |
| 1 | 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 |
2006 |
DBLP DOI BibTeX RDF |
Approximation algorithms, bin packing, average case analysis |
| 1 | David S. Johnson |
The NP-completeness column. |
ACM Transactions on Algorithms |
2005 |
DBLP DOI BibTeX RDF |
lattice bases, NP-completeness, coding theory, perfect graphs, primality testing, open problems |
| 1 | János Csirik, David S. Johnson, Claire Kenyon |
On the Worst-case Performance of the Sum-of-Squares Algorithm for Bin Packing |
CoRR |
2005 |
DBLP BibTeX RDF |
|
| 1 | 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. |
2005 |
DBLP DOI BibTeX RDF |
visibility computation, compression, levels of detail, Interactive walkthrough |
| 1 | David S. Johnson, Shankar Krishnan, Jatin Chhugani, Subodh Kumar, Suresh Venkatasubramanian |
Compressing Large Boolean Matrices using Reordering Techniques. |
VLDB |
2004 |
DBLP BibTeX RDF |
|
| 1 | 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 |
2003 |
DBLP DOI BibTeX RDF |
maximum scatter TSP, polyhedral metric, optimization, NP-hardness, Traveling salesman problem, polynomial time, Euclidean metric |
| 1 | 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 |
DBLP BibTeX RDF |
|
| 1 | 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 |
2002 |
DBLP BibTeX RDF |
|
| 1 | Alexander I. Barvinok, Sándor P. Fekete, David S. Johnson, Arie Tamir, Gerhard J. Woeginger, Russell Woodroofe |
The Geometric Maximum Traveling Salesman Problem |
CoRR |
2002 |
DBLP BibTeX RDF |
|
| 1 | János Csirik, David S. Johnson |
Bounded Space On-Line Bin Packing: Best Is Better than First. |
Algorithmica |
2001 |
DBLP DOI BibTeX RDF |
|
| 1 | János Csirik, David S. Johnson, Claire Kenyon |
Better approximation algorithms for bin covering. |
SODA |
2001 |
DBLP DOI BibTeX RDF |
|
| 1 | Jill Cirasella, David S. Johnson, Lyle A. McGeoch, Weixiong Zhang |
The Asymmetric Traveling Salesman Problem: Algorithms, Instance Generators, and Tests. |
ALENEX |
2001 |
DBLP BibTeX RDF |
|
| 1 | 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. |
2000 |
DBLP DOI BibTeX RDF |
|
| 1 | David S. Johnson, Maria Minkoff, Steven Phillips |
The prize collecting Steiner tree problem: theory and practice. |
SODA |
2000 |
DBLP DOI BibTeX RDF |
|
| 1 | 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 |
DBLP DOI BibTeX RDF |
|
| 1 | David S. Johnson, Mario Szegedy |
What are the Least Tractable Instances of max Tndependent Set? |
SODA |
1999 |
DBLP DOI BibTeX RDF |
|
| 1 | János Csirik, David S. Johnson, Claire Kenyon, Peter W. Shor, Richard R. Weber |
A Self Organizing Bin Packing Heuristic. |
ALENEX |
1999 |
DBLP DOI BibTeX RDF |
|
| 1 | Alexander I. Barvinok, David S. Johnson, Gerhard J. Woeginger, Russell Woodroofe |
The Maximum Traveling Salesman Problem Under Polyhedral Norms. |
IPCO |
1998 |
DBLP DOI BibTeX RDF |
|
| 1 | 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 |
1997 |
DBLP BibTeX RDF |
|
| 1 | 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 |
1997 |
DBLP DOI BibTeX RDF |
|
| 1 | 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 |
1997 |
DBLP DOI BibTeX RDF |
|
| 1 | Cliff Young, David S. Johnson, David R. Karger, Michael D. Smith |
Near-optimal Intraprocedural Branch Alignment. |
PLDI |
1997 |
DBLP DOI BibTeX RDF |
|
| 1 | David S. Johnson |
How to do experiments (extended advertisement). |
SIGACT News |
1996 |
DBLP DOI BibTeX RDF |
|
| 1 | David S. Johnson |
A Brief History of SIGACT News and its Editors. |
SIGACT News |
1996 |
DBLP DOI BibTeX RDF |
|
| 1 | David S. Johnson, Lyle A. McGeoch, Edward E. Rothberg |
Asymptotic Experimental Analysis for the Held-Karp Traveling Salesman Bound. |
SODA |
1996 |
DBLP DOI BibTeX RDF |
|
| 1 | Michael L. Fredman, David S. Johnson, Lyle A. McGeoch, G. Ostheimer |
Data Structures for Traveling Salesmen. |
J. Algorithms |
1995 |
DBLP DOI BibTeX RDF |
|
| 1 | Elias Dahlhaus, David S. Johnson, Christos H. Papadimitriou, Paul D. Seymour, Mihalis Yannakakis |
The Complexity of Multiterminal Cuts. |
SIAM J. Comput. |
1994 |
DBLP DOI BibTeX RDF |
|
| 1 | David S. Johnson, Andrea S. LaPaugh, Ron Y. Pinter |
Minimizing Channel Density by Lateral Shifting of Components. |
SODA |
1994 |
DBLP DOI BibTeX RDF |
|
| 1 | David S. Johnson |
The Traveling Salesman Problem: A report on the State of the Art. |
IFIP Congress |
1994 |
DBLP BibTeX RDF |
|
| 1 | David S. Johnson, Francine Berman |
Performance of the Efficient Data-Driven Evaluation Scheme. |
J. Parallel Distrib. Comput. |
1993 |
DBLP DOI BibTeX RDF |
|
| 1 | Michael L. Fredman, David S. Johnson, Lyle A. McGeoch, G. Ostheimer |
Data Structures for Traveling Salesmen. |
SODA |
1993 |
DBLP DOI BibTeX RDF |
|
| 1 | 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 |
STOC |
1993 |
DBLP BibTeX RDF |
|
| 1 | 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 |
DBLP DOI BibTeX RDF |
|
| 1 | David S. Johnson |
The NP-Completeness Column: An Ongoing Guide. |
J. Algorithms |
1992 |
DBLP DOI BibTeX RDF |
|
| 1 | Elias Dahlhaus, David S. Johnson, Christos H. Papadimitriou, Paul D. Seymour, Mihalis Yannakakis |
The Complexity of Multiway Cuts (Extended Abstract) |
STOC |
1992 |
DBLP DOI BibTeX RDF |
|
| 1 | János Csirik, David S. Johnson |
Bounded Space On-Line Bin Packing: Best is Better than First. |
SODA |
1991 |
DBLP DOI BibTeX RDF |
|
| 1 | 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 |
DBLP DOI BibTeX RDF |
|
| 1 | Brent N. Clark, Charles J. Colbourn, David S. Johnson |
Unit disk graphs. |
Discrete Mathematics |
1990 |
DBLP DOI BibTeX RDF |
|
| 1 | David S. Johnson |
The NP-Completeness Column: An Ongoing Guide. |
J. Algorithms |
1990 |
DBLP DOI BibTeX RDF |
|
| 1 | Francine Berman, David S. Johnson, Frank Thomson Leighton, Peter W. Shor, Larry Snyder |
Generalized Planar Matching. |
J. Algorithms |
1990 |
DBLP DOI BibTeX RDF |
|
| 1 | David S. Johnson |
A stoc/focs bibliography: the last progress report. |
SIGACT News |
1990 |
DBLP DOI BibTeX RDF |
|
| 1 | David S. Johnson |
A Catalog of Complexity Classes. |
Handbook of Theoretical Computer Science, Volume A: Algorithms and Complexity (A) |
1990 |
DBLP BibTeX RDF |
|
| 1 | David S. Johnson (eds.) |
Proceedings of the First Annual ACM-SIAM Symposium on Discrete Algorithms, 22-24 January 1990, San Francisco, California. |
SODA |
1990 |
DBLP BibTeX RDF |
|
| 1 | David S. Johnson |
Local Optimization and the Traveling Salesman Problem. |
ICALP |
1990 |
DBLP DOI BibTeX RDF |
|
| 1 | David S. Johnson |
Data Structures for Traveling Salesmen (Abstract). |
SWAT |
1990 |
DBLP DOI BibTeX RDF |
|
| 1 | David S. Johnson (eds.) |
Proceedings of the 21st Annual ACM Symposium on Theory of Computing, May 14-17, 1989, Seattle, Washigton, USA |
STOC |
1989 |
DBLP BibTeX RDF |
|
| 1 | David S. Johnson, Christos H. Papadimitriou, Mihalis Yannakakis |
On Generating All Maximal Independent Sets. |
Inf. Process. Lett. |
1988 |
DBLP DOI BibTeX RDF |
|
| 1 | David S. Johnson |
The NP-Completeness Column: An Ongoing Guide. |
J. Algorithms |
1988 |
DBLP DOI BibTeX RDF |
|
| 1 | Nimrod Megiddo, S. Louis Hakimi, M. R. Garey, David S. Johnson, Christos H. Papadimitriou |
The complexity of searching a graph. |
J. ACM |
1988 |
DBLP DOI BibTeX RDF |
|
| 1 | David S. Johnson, Christos H. Papadimitriou, Mihalis Yannakakis |
How Easy is Local Search? |
J. Comput. Syst. Sci. |
1988 |
DBLP DOI BibTeX RDF |
|
| 1 | Edward G. Coffman Jr., M. R. Garey, David S. Johnson |
Bin packing with divisible item sizes. |
J. Complexity |
1987 |
DBLP DOI BibTeX RDF |
|
| 1 | David S. Johnson |
The NP-Completeness Column: An Ongoing Guide. |
J. Algorithms |
1987 |
DBLP DOI BibTeX RDF |
|
| 1 | David S. Johnson |
The NP-Completeness Column: An Ongoing Guide. |
J. Algorithms |
1987 |
DBLP DOI BibTeX RDF |
|
| 1 | David S. Johnson |
The NP-Completeness Column: An Ongoing Guide. |
J. Algorithms |
1986 |
DBLP DOI BibTeX RDF |
|
| 1 | David S. Johnson |
The NP-Completeness Column: An Ongoing Guide. |
J. Algorithms |
1986 |
DBLP DOI BibTeX RDF |
|
| 1 | David S. Johnson, M. R. Garey |
A 71/60 theorem for bin packing. |
J. Complexity |
1985 |
DBLP DOI BibTeX RDF |
|
| 1 | David S. Johnson |
The NP-Completeness Column: An Ongoing Guide. |
J. Algorithms |
1985 |
DBLP DOI BibTeX RDF |
|
| 1 | David S. Johnson |
The NP-Completeness Column: An Ongoing Guide. |
J. Algorithms |
1985 |
DBLP DOI BibTeX RDF |
|
| 1 | David S. Johnson |
The NP-Completeness Column: An Ongoing Guide. |
J. Algorithms |
1985 |
DBLP DOI BibTeX RDF |
|
| 1 | Edward G. Coffman Jr., M. R. Garey, David S. Johnson, Andrea S. LaPaugh |
Scheduling File Transfers. |
SIAM J. Comput. |
1985 |
DBLP DOI BibTeX RDF |
|
| 1 | M. R. Garey, David S. Johnson |
Composing Functions to Minimize Image Size. |
SIAM J. Comput. |
1985 |
DBLP DOI BibTeX RDF |
|
| 1 | David S. Johnson, Christos H. Papadimitriou, Mihalis Yannakakis |
How Easy Is Local Search? (Extended Abstract) |
FOCS |
1985 |
DBLP DOI BibTeX RDF |
|
| 1 | David S. Johnson |
The NP-Completeness Column: An Ongoing Guide. |
J. Algorithms |
1984 |
DBLP DOI BibTeX RDF |
|
| 1 | David S. Johnson |
The NP-Completeness Column: An Ongoing Guide. |
J. Algorithms |
1984 |
DBLP DOI BibTeX RDF |
|
| 1 | David S. Johnson |
The NP-Completeness Column: An Ongoing Guide. |
J. Algorithms |
1984 |
DBLP DOI BibTeX RDF |
|
| 1 | 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 |
1984 |
DBLP DOI BibTeX RDF |
|
| 1 | David S. Johnson |
The NP-Completeness Column: An Ongoing Guide. |
J. Algorithms |
1984 |
DBLP DOI BibTeX RDF |
|
| 1 | David S. Johnson, Anthony C. Klug |
Testing Containment of Conjunctive Queries under Functional and Inclusion Dependencies. |
J. Comput. Syst. Sci. |
1984 |
DBLP DOI BibTeX RDF |
|
| 1 | 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 |
DBLP DOI BibTeX RDF |
|
| 1 | David S. Johnson |
The NP-Completeness Column: An Ongoing Guide. |
J. Algorithms |
1983 |
DBLP DOI BibTeX RDF |
|
| 1 | David S. Johnson |
The NP-Completeness Column: An Ongoing Guide. |
J. Algorithms |
1983 |
DBLP DOI BibTeX RDF |
|
| 1 | David S. Johnson |
The NP-Completeness Column: An Ongoing Guide. |
J. Algorithms |
1983 |
DBLP DOI BibTeX RDF |
|
| 1 | David S. Johnson |
The NP-Completeness Column: An Ongoing Guide. |
J. Algorithms |
1983 |
DBLP DOI BibTeX RDF |
|
| 1 | David S. Johnson, Anthony C. Klug |
Optimizing Conjunctive Queries that Contain Untyped Variables. |
SIAM J. Comput. |
1983 |
DBLP DOI BibTeX RDF |
|
| 1 | Edward G. Coffman Jr., M. R. Garey, David S. Johnson |
Dynamic Bin Packing. |
SIAM J. Comput. |
1983 |
DBLP DOI BibTeX RDF |
|
| 1 | Edward G. Coffman Jr., M. R. Garey, David S. Johnson, Andrea S. LaPaugh |
Scheduling File Transfers in a Distributed Network. |
PODC |
1983 |
DBLP DOI BibTeX RDF |
|
| 1 | 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 |
STOC |
1983 |
DBLP BibTeX RDF |
|
| 1 | David S. Johnson |
The NP-Completeness Column: An Ongoing Guide. |
J. Algorithms |
1982 |
DBLP DOI BibTeX RDF |
|
| 1 | David S. Johnson |
The NP-Completeness Column: An Ongoing Guide. |
J. Algorithms |
1982 |
DBLP DOI BibTeX RDF |
|
| 1 | David S. Johnson |
The NP-Completeness Column: An Ongoing Guide. |
J. Algorithms |
1982 |
DBLP DOI BibTeX RDF |
|
| 1 | David S. Johnson |
The NP-Completeness Column: An Ongoing Guide. |
J. Algorithms |
1982 |
DBLP DOI BibTeX RDF |
|
| 1 | M. R. Garey, David S. Johnson, Hans S. Witsenhausen |
The complexity of the generalized Lloyd - Max problem. |
IEEE Transactions on Information Theory |
1982 |
DBLP DOI BibTeX RDF |
|
| 1 | David S. Johnson, Anthony C. Klug |
Testing Containment of Conjunctive Queries Under Functional and Inclusion Dependencies. |
PODS |
1982 |
DBLP DOI BibTeX RDF |
|
| 1 | David S. Johnson |
The NP-Completeness Column: An Ongoing Guide. |
J. Algorithms |
1981 |
DBLP DOI BibTeX RDF |
|
| 1 | 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. |
1981 |
DBLP DOI BibTeX RDF |
|
| 1 | Nimrod Megiddo, S. Louis Hakimi, M. R. Garey, David S. Johnson, Christos H. Papadimitriou |
The Complexity of Searching a Graph (Preliminary Version) |
FOCS |
1981 |
DBLP DOI BibTeX RDF |
|
| 1 | David S. Johnson, Anthony C. Klug |
Optimizing Conjunctive Queries When Attribute Domains Are not Disjoint (Extended Abstract) |
FOCS |
1981 |
DBLP DOI BibTeX RDF |
|
| 1 | 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. |
1980 |
DBLP DOI BibTeX RDF |
|
| 1 | M. R. Garey, David S. Johnson |
Computers and Intractability: A Guide to the Theory of NP-Completeness. |
|
1979 |
RDF |
|
| 1 | M. R. Garey, David S. Johnson, Franco P. Preparata, Robert Endre Tarjan |
Triangulating a Simple Polygon. |
Inf. Process. Lett. |
1978 |
DBLP DOI BibTeX RDF |
|
| 1 | David S. Johnson, Franco P. Preparata |
The Densest Hemisphere Problem. |
Theor. Comput. Sci. |
1978 |
DBLP DOI BibTeX RDF |
|
![[Valid RSS]](Pics/valid-rss.png "Validate my RSS feed")