Model-based Analysis of ChIP-Seq (MACS) (2008)
Zhang, Yong, Liu, Tao, Meyer, Clifford A, Eeckhoute, Jérôme, Johnson, David S, Bernstein, Bradley E, ...
Abstract We present Model-based Analysis of ChIP-Seq data, MACS, which analyzes data generated by short read sequencers such as Solexa's Genome Analyzer. MACS empirically models the shift size of...
Systematic evaluation of variability in ChIP-chip experiments using predefined DNA targets. (2008)
Johnson, David S., Li, Wei, Gordon, D. Benjamin, Bhattacharjee, Arindam, Curry, Bo, Ghosh, Jayati, ...
The most widely used method for detecting genome-wide protein-DNA interactions is chromatin immunoprecipitation on tiling microarrays, commonly known as ChIP-chip. Here, we conducted the first...
Consumption Mobility in the United States: Evidence from Two Panel Data Sets (2006)
Fisher, Jonathan D, Johnson, David S
This paper examines inequality and mobility using measures of income and consumption. Consumption is claimed to be a better measure of permanent income and thus well-being, but most studies of...
Consumption Mobility in the United States: Evidence from Two Panel Data Sets (2006)
Fisher, Jonathan D, Johnson, David S
This paper examines inequality and mobility using measures of income and consumption. Consumption is claimed to be a better measure of permanent income and thus well-being, but most studies of...
Consumption Mobility in the United States: Evidence from Two Panel Data Sets (2006)
Fisher, Jonathan D, Johnson, David S
This paper examines inequality and mobility using measures of income and consumption. Consumption is claimed to be a better measure of permanent income and thus well-being, but most studies of...
Consumption Mobility in the United States: Evidence from Two Panel Data Sets (2006)
Fisher, Jonathan D, Johnson, David S
This paper examines inequality and mobility using measures of income and consumption. Consumption is claimed to be a better measure of permanent income and thus well-being, but most studies of...
No Place Like Home: Older Adults and Their Housing (2006)
Smeeding, Timothy, Boyle Torrey, Barbara, Fisher, Jonathan, Johnson, David S., Marchand, Joseph
Objectives: This paper employs new data on the consumption and assets of older Americans to investigate recent research findings that older adults do not convert their home equity into income that...
The Retirement Consumption Conundrum: Evidence from a Consumption Survey (2005)
Fisher, Johnathan, Johnson, David S., Marchand, Joseph, Smeeding, Timothy M., Torrey, Barbara Boyle
While the life-cycle hypothesis predicts that consumption remains smooth during the transition from work into retirement, recent studies have shown that consumption declines at retirement. This...
On the Worst-case Performance of the Sum-of-Squares Algorithm for Bin Packing (2005)
Csirik, Janos, Johnson, David S., Kenyon, Claire
The Sum of Squares algorithm for bin packing was defined in [2] and studied in great detail in [1], where it was proved that its worst case performance ratio is at most 3. In this note, we improve...
The Cutting-Stock Approach to Bin Packing: Theory and Experiments (2003)
Luciana S. Buriol, Bernard L. Dillard, David S. Johnson, Peter W. Shor
We report on an experimental study of the Gilmore-Gomory cutting-stock heuristic and related LP-based approaches to bin packing, as applied to instances generated according to discrete distributions....
On the Sum-of-Squares Algorithm for Bin Packing (2002)
Janos Csirik, David S. Johnson, Claire Kenyon, James B. Orlin, Peter W. Shor, Richard R. Weber
In this paper we present a theoretical analysis of the deterministic on-line Sum of Squares algorithm (SS) for bin packing introduced and studied experimentally in [CJK 99], along with several new...
On the Sum-of-Squares Algorithm for Bin Packing (2002)
Csirik, Janos, Johnson, David S., Kenyon, Claire, Orlin, James B., Shor, Peter W., Weber, Richard R.
In this paper we present a theoretical analysis of the deterministic on-line {\em Sum of Squares} algorithm ($SS$) for bin packing introduced and studied experimentally in \cite{CJK99}, along with...
The Geometric Maximum Traveling Salesman Problem (2002)
Alexander Barvinok, Sandor P. Fekete, David S. Johnson, Arie Tamir, Gerhard J. Woeginger, Russell Woodroofe
We consider the traveling salesman problem when the cities are points in R^d for some fixed d and distances are computed according to geometric distances, determined by some norm. We show that for...
The Cutting-Stock Approach to Bin Packing: Theory and Experiments (2002)
Luciana S. Buriol, Bernard L. Dillard, David S. Johnson, Peter W. Shor
We report on results of an experimental study of the Gilmore-Gomory cutting-stock heuristic [GG61, GG63] and related LP-based approaches to bin packing, as applied to instances generated according to...
The Geometric Maximum Traveling Salesman Problem (2002)
Barvinok, Alexander, Fekete, Sandor P., Johnson, David S., Tamir, Arie, Woeginger, Gerhard J., Woodroofe, Russ
We consider the traveling salesman problem when the cities are points in R^d for some fixed d and distances are computed according to geometric distances, determined by some norm. We show that for...
Complexity Results for Bandwidth Minimization. (2002)
Garey,Michael R., Graham,Ronald L., Johnson,David S., Knuth,D. E.
A linear-time algorithm for sparse symmetric matrices which converts a matrix into pentadiagonal form (bandwidth 2), whenever it is possible to do so using simultaneous row and column permutations is...
Experimental Analysis Of Heuristics For The ATSP (2001)
David S. Johnson, Gregory Gutin, Lyle A. Mcgeoch, Anders Yeo, Weixiong Zhang, Alexei Zverovitch
Introduction In this chapter, we consider what approaches one should take when confronting a real-world application of the asymmetric TSP, that is, the general TSP in which the distance d(c; c 0 )...
A Theoretician's Guide to the Experimental Analysis of Algorithms (2001)
This paper presents an informal discussion of issues that arise when one attempts to analyze algorithms experimentally. It is based on lessons learned by the author over the course of more than a...
Experimental Analysis Of Heuristics For The STSP (2001)
David S. Johnson, Lyle A. Mcgeoch
Introduction In this and the following chapter, we consider what approaches one should take when one is confronted with a real-world application of the TSP. What algorithms should be used under which...
The Asymmetric Traveling Salesman Problem: Algorithms, Instance Generators, and Tests (2001)
Jill Cirasella, David S. Johnson, Lyle A. Mcgeoch, Weixiong Zhang
The purpose of this paper is to provide a preliminary report on the first broad-based experimental comparison of modern heuristics for the asymmetric traveling salesmen problem (ATSP). There are...
The Asymmetric Traveling Salesman Problem: Algorithms, Instance Generators, and Tests (2001)
Jill Cirasella, David S. Johnson, Lyle A. Mcgeoch, Weixiong Zhang
. The purpose of this paper is to provide a preliminary report on the first broad-based experimental comparison of modern heuristics for the asymmetric traveling salesmen problem (ATSP). There are...
Who Are the Poor Elderly? An Examination Using Alternative Poverty Measures (2000)
Johnson, David S., Smeeding, Timothy M.
According to most accounts the past decade has brought with it tremendous gains in reducing poverty among the elderly, i.e., those persons aged 65 or older. Although official poverty rate for...
The Asymmetric Traveling Salesman Problem: Algorithms, Instance Generators, and Tests (2000)
Jill Cirasella, David S. Johnson, Lyle A. Mcgeoch, Weixiong Zhang
The purpose of this paper is to provide the first broad-based experimental comparison of modern heuristics for the asymmetric traveling salesmen problem (ATSP). There are currently three general...
On the Sum-of-Squares Algorithm for Bin Packing (2000)
Janos Csirik, David S. Johnson, Claire Kenyon, James B. Orlin, Peter W. Shor, Richard R. Weber
In this paper we present a theoretical analysis of the deterministic on-line Sum of Squares algorithm (SS) for bin packing, introduced and studied experimentally in [8], along with several new...
A Self Organizing Bin Packing Heuristic (2000)
Janos Csirik, David S. Johnson, Claire Kenyon, Peter W. Shor, Richard R. Weber
. This paper reports on experiments with a new on-line heuristic for one-dimensional bin packing whose average-case behavior is surprisingly robust. We restrict attention to the class of "discrete"...
Better Approximation Algorithms for Bin Covering (2000)
Janos Csirik, David S. Johnson, Claire Kenyon
Bin covering takes as input a list of item sizes and places them into bins of unit demand so as to maximize the number of bins whose demand is satisfied. This is in a sense a dual problem to the...
Better Approximation Algorithms for Bin Covering (2000)
Janos Csirik, David S. Johnson, Claire Kenyon
Bin covering takes as input a list of item sizes and places them into bins of unit demand so as to maximize the number of bins whose demand is satisfied. This is in a sense a dual problem to the...
On the Sum-of-Squares Algorithm for Bin Packing (2000)
Janos Csirik, David S. Johnson, Claire Kenyon, James B. Orlin, Peter W. Shor, Richard R. Weber
In this paper we present a theoretical analysis of the deterministic on-line Sum of Squares algorithm (SS) for bin packing, introduced and studied experimentally in [8], along with several new...
The Prize Collecting Steiner Tree Problem: Theory and Practice (2000)
David S. Johnson, Maria Minkoff, Steven Phillips
We consider variants on the Prize Collecting Steiner Tree problem and on the primal-dual 2-approximation algorithm devised for it by Goemans and Williamson. We introduce an improved pruning rule for...
Near-optimal Intraprocedural Branch Alignment (1999)
Cliff Young, David S. Johnson, David R. Karger, Michael D. Smith
Branch alignment reorders the basic blocks of a program to minimize pipeline penalties due to control-transfer instructions. Prior work in branch alignment has produced useful heuristic methods. We...
A Self-Organizing Bin Packing Heuristic (1999)
Janos Csirik, David S. Johnson, Claire Kenyon, Peter W. Shor, Richard R. Weber
. This paper reports on experiments with a new on-line heuristic for one-dimensional bin packing whose average-case behavior is surprisingly robust. We restrict attention to the class of "discrete"...
A Self-Organizing Bin Packing Heuristic (1999)
Janos Csirik, David S. Johnson, Claire Kenyon, Peter W. Shor, Richard R. Weber
This paper reports experiments with a new and surprisingly robust on-line heuristic for one-dimensional bin packing. This new Sum of Squares algorithm (SS) is restricted to the class of "discrete"...
A Self-Organizing Bin Packing Heuristic (1998)
Janos Csirik, David S. Johnson, Claire Kenyon, Peter W. Shor, Richard R. Weber
This paper reports experiments with a new and surprisingly robust on-line heuristic for one-dimensional bin packing. This new Sum of Squares algorithm (SS) is restricted to the class of "discrete"...
The Maximum Traveling Salesman Problem under Polyhedral Norms (1998)
Alexander Barvinok, David S. Johnson, Gerhard J. Woeginger, Russell Woodroofe
. We consider the traveling salesman problem when the cities are points in R d for some fixed d and distances are computed according to a polyhedral norm. We show that for any such norm, the problem...
Finding Maximum Length Tours Under Polyhedral Norms (1998)
Alexander Barvinok, David S. Johnson, Gerhard J. Woeginger, Russell Woodroofe
We consider the traveling salesman problem when the cities are points in IR d for some fixed d and distances are computed according to a polyhedral norm. We show that for any such norm, the problem...
Polynomial Time Algorithms for Maximization Problems in Spaces With Polyhedral Norms (1997)
Alexander Barvinok, David S. Johnson, Gerhard J. Woeginger, Russel Woodroofe
We discuss geometric special cases of optimization problems on graphs where the n vertices are represented as points in IR d and where the lengths of the edges are measured according to a norm with a...
Emerging Opportunities for Theoretical Computer Science (1996)
Alfred V. Aho, David S. Johnson, S. Rao Kosaraju, Catherine C. Mcgeoch, Christos H. Papadimitriou, ...
The principles underlying this report can be summarized as follows: 1. A strong theoretical foundation is vital to computer science. 2. Theory can be enriched by practice. 3. Practice can be enriched...
Thesis (M.A. in Architecture and Urban Planning)--University of California, Los Angeles, 1980.
Garey, Michael R, Johnson, David S
Incluye bibliografía e índice
Look-Ahead Strategies in One Person Games with Randomly Generated Game Trees (1970)
A random method for generated binary trees is presented, ad twp forms of a class of one person games called, "Tree Solitaire" which have such trees as their game trees are defined. After what "look...
Look-Ahead Strategies in One Person Games with Randomly Generated Game Trees (1970)
A random method for generated binary trees is presented, ad twp forms of a class of one person games called, "Tree Solitaire" which have such trees as their game trees are defined. After what "look...
Near-optimal Intraprocedural Branch Alignment (1970)
Cliff Young, David S. Johnson, David R. Karger, Michael D. Smith
Branch alignment reorders the basic blocks of a program to minimize pipeline penalties due to control-transfer instructions. Prior work in branch alignment has produced useful heuristic methods. We...
The gamma function and Stirling's formula (1967)
This thesis is not available electronically or by photocopy. Please contact Archives and Special Collections at archives@amherst.edu for more information.
Methods of determination of drop size and distribution in natural fogs. (1949)
Thesis (M.A.)--University of California, Los Angeles - Meteorology, 1949.
The frequency and location of interviewing stations for traffic origins and destinations / (1946)
"A thesis submitted in fulfillment of the requirements of Transportation 113 offered by the Bureau of Highway Traffic, Yale University, New Haven, Connecticut."
Transferring medical images on the world wide web for emergency clinical management: a case report
Johnson, David S, Goel, Rajinder P, Birtwistle, Paul, Hirst, Phil
CLINICAL, MORPHOLOGICAL AND BIOCHEMICAL STUDIES OF A VIRILIZING TUMOR IN THE TESTIS*
Savard, Kenneth, Dorfman, Ralph I., Baggett, Billy, Fielding, Linda L., Engel, Lewis L., McPherson, Harry T., ...
Johnson, David S., Davidson, Brad, Brown, Christopher D., Smith, William C., Sidow, Arend
We show that sequence comparisons at different levels of resolution can efficiently guide functional analyses of regulatory regions in the ascidians Ciona savignyi and Ciona intestinalis. Sequence...
De novo discovery of a tissue-specific gene regulatory module in a chordate
Johnson, David S., Zhou, Qing, Yagi, Kasumi, Satoh, Nori, Wong, Wing, Sidow, Arend
We engage the experimental and computational challenges of de novo regulatory module discovery in a complex and largely unstudied metazoan genome. Our analysis is based on the comprehensive...
Transferring medical images on the world wide web for emergency clinical management: a case report
Johnson, David S, Goel, Rajinder P, Birtwistle, Paul, Hirst, Phil
CLINICAL, MORPHOLOGICAL AND BIOCHEMICAL STUDIES OF A VIRILIZING TUMOR IN THE TESTIS*
Savard, Kenneth, Dorfman, Ralph I., Baggett, Billy, Fielding, Linda L., Engel, Lewis L., McPherson, Harry T., ...
Johnson, David S., Davidson, Brad, Brown, Christopher D., Smith, William C., Sidow, Arend
We show that sequence comparisons at different levels of resolution can efficiently guide functional analyses of regulatory regions in the ascidians Ciona savignyi and Ciona intestinalis. Sequence...
De novo discovery of a tissue-specific gene regulatory module in a chordate
Johnson, David S., Zhou, Qing, Yagi, Kasumi, Satoh, Nori, Wong, Wing, Sidow, Arend
We engage the experimental and computational challenges of de novo regulatory module discovery in a complex and largely unstudied metazoan genome. Our analysis is based on the comprehensive...
No Place Like Home: Older Adults and Their Housing
Timothy Smeeding, Barbara Boyle Torrey, Jonathon Fisher, David S. Johnson
Objectives: This paper employs new data on the consumption and assets of older Americans to investigate recent research findings that older adults do not convert their home equity into income that...
Experimental Total Midzonal Hepatic Necrosis*
Black-Schaffer, Bernard, Johnson, David S., Gobbel, Walter G.
Child Poverty in Wealthy Countries
David S. Johnson, Barbara Boyle Torrey
Review of Child Well-Being, Child Poverty and Child Policy in Modern Nations by Koen Vleminckx and Timothy M. Smeeding and The Dynamics of Child Poverty in Industrialized Countries by Bruce Bradbury,...
Household Expenditure and the Income Tax Rebates of 2001
David S. Johnson, Jonathan A. Parker, Nicholas S. Souleles
Using questions expressly added to the Consumer Expenditure Survey, we estimate the change in consumption expenditures caused by the 2001 federal income tax rebates and test the permanent income...
Household Expenditure and the Income Tax Rebates of 2001
David S. Johnson, Jonathan A. Parker, Nicholas S. Souleles
Under the Economic Growth and Tax Relief Reconciliation Act of 2001, most U.S. taxpayers received a tax rebate between July and September, 2001. The week in which the rebate was mailed was based on...
Household Expenditure and the Income Tax Rebates of 2001
David S. Johnson, Jonathan A. Parker, Nicholas S. Souleles
Under the Economic Growth and Tax Relief Reconciliation Act of 2001, most U.S. taxpayers received a tax rebate between July and September, 2001. The week in which the rebate was mailed was based on...
Systematic evaluation of variability in ChIP-chip experiments using predefined DNA targets
Johnson, David S., Li, Wei, Gordon, D. Benjamin, Bhattacharjee, Arindam, Curry, Bo, Ghosh, Jayati, ...
The most widely used method for detecting genome-wide protein–DNA interactions is chromatin immunoprecipitation on tiling microarrays, commonly known as ChIP-chip. Here, we conducted the first...
The retirement consumption conundrum: Evidence from a consumption survey
Fisher, Jonathan D., Johnson, David S., Marchand, Joseph, Smeeding, Timothy M., Torrey, Barbara Boyle
Recent studies have shown that food consumption declines at retirement. We use broader definitions of consumption from the Consumer Expenditure Survey and find that the so-called retirement...
note: Inequality and the business cycle: A consumption viewpoint
David S. Johnson, Stephanie Shipp
Using Consumer Expenditure Survey data, we obtain summary measures of the distributions of income and consumption for each quarter between 1980 and 1994. We find that the trends in the distribution...
Household Expenditure and the Income Tax Rebates of 2001
David S. Johnson, Jonathan A. Parker, Nicholas S. Souleles
Under the Economic Growth and Tax Relief Reconciliation Act of 2001, most U.S. taxpayers received a tax rebate between July and September, 2001. The week in which the rebate was mailed was based on...
The Retirement Consumption Conundrum: Evidence from a Consumption Survey
Johnathan Fisher, David S. Johnson, Joseph Marchand, Timothy M. Smeeding, Barbara Boyle Torrey
While the life-cycle hypothesis predicts that consumption remains smooth during the transition from work into retirement, recent studies have shown that consumption declines at retirement. This...