Proceedings of the AAAI Conference on Artificial Intelligence
Bike-sharing systems are becoming increasingly prevalent in urban environments. They provide a lo... more Bike-sharing systems are becoming increasingly prevalent in urban environments. They provide a low-cost, environmentally-friendly transportation alternative for cities. The management of these systems gives rise to many optimization problems. Chief among these problems is the issue of bicycle rebalancing. Users imbalance the system by creating demand in an asymmetric pattern. This necessitates action to put the system back in balance with the requisite levels of bicycles at each station to facilitate future use. In this paper, we tackle the problem of maintaing system balance during peak rush-hour usageas well as rebalancing overnight to prepare the systemfor rush-hour usage. We provide novel problem formulationsthat have been motivated by both a close collaborationwith the New York City bike share (Citibike) and a careful analysisof system usage data. We analyze system data to discover the best placement of bikes tofacilitate usage. We solve routing problems forovernight shifts as ...
BackgroundWhile booster vaccinations clearly reduce the risk of severe COVID-19 and death, the im... more BackgroundWhile booster vaccinations clearly reduce the risk of severe COVID-19 and death, the impact of boosters on SARS-CoV-2 infection has not been fully characterized: doing so requires understanding their impact on asymptomatic and mildly symptomatic infections that often go unreported but nevertheless play an important role in spreading SARS-CoV-2. We sought to estimate the impact of COVID-19 booster doses on SARS-CoV-2 infection in a vaccinated population of young adults during an Omicron BA.1-predominant period.Methods and FindingsWe implemented a cohort study of young adults in a college environment (Cornell University’s Ithaca campus) from a period when Omicron BA.1 was the predominant SARS-CoV-2 variant on campus (December 5 to December 31, 2021). Participants included 15,800 university students who completed an initial vaccination series with a vaccine approved by the World Health Organization for emergency use, were enrolled in mandatory at-least-weekly surveillance PCR...
Proceedings of the National Academy of Sciences, 2021
Significance Decisions surrounding how to safely reopen universities directly impact 7% of the US... more Significance Decisions surrounding how to safely reopen universities directly impact 7% of the US population (students, staff) and indirectly impact tens of millions more (families, communities). After witnessing large COVID-19 outbreaks among students from August 2020 to the present, universities want to provide safety while minimizing social and financial costs, despite uncertainty about vaccine hesitancy, vaccine efficacy, more transmissible variants with the potential for immune escape, and community prevalence. When the Delta variant is dominant, we find substantial risk reduction in moving student populations from mostly (75%) to fully (100%) vaccinated, in testing vaccinated students once per week even when all students are vaccinated, and in more frequent testing targeted to the most social groups of students.
Historically, linkage mapping populations have consisted of large, randomly selected samples of p... more Historically, linkage mapping populations have consisted of large, randomly selected samples of progeny from a given pedigree or cell lines from a panel of radiation hybrids. We demonstrate that, to construct a map with high genome-wide marker density, it is neither necessary nor desirable to genotype all markers in every individual of a large mapping population. Instead, a reduced sample of individuals bearing complementary recombinational or radiation-induced breakpoints may be selected for genotyping subsequent markers from a large, but sparsely genotyped, mapping population. Choosing such a sample can be reduced to a discrete stochastic optimization problem for which the goal is a sample with breakpoints spaced evenly throughout the genome. We have developed several different methods for selecting such samples and have evaluated their performance on simulated and actual mapping populations, including the Lister and Dean Arabidopsis thaliana recombinant inbred population and the ...
We consider constrained versions of the prize-collecting traveling salesman and the prize-collect... more We consider constrained versions of the prize-collecting traveling salesman and the prize-collecting minimum spanning tree problems. The goal is to maximize the number of vertices in the returned tour/tree subject to a bound on the tour/tree cost. Rooted variants of the problems have the additional constraint that a given vertex, the root, must be contained in the tour/tree. We present a 2-approximation algorithm for the rooted and unrooted versions of both the tree and tour variants. The algorithm is based on a parameterized primal–dual approach. It relies on first finding a threshold value for the dual variable corresponding to the budget constraint in the primal and then carefully constructing a tour/tree that is, in a precise sense, just within budget. We improve upon the best-known guarantee of 2 + ε for the rooted and unrooted tour versions and 3 + ε for the rooted and unrooted tree versions. Our analysis extends to the setting with weighted vertices, in which we want to maxim...
In this paper we present a 2-approximation algorithm for the k-center problem with triangle inequ... more In this paper we present a 2-approximation algorithm for the k-center problem with triangle inequality. This result is “best possible” since for any δ < 2 the existence of δ-approximation algorithm would imply that P = NP. It should be noted that no δ-approximation algorithm, for any constant δ, has been reported to date. Linear programming duality theory provides interesting insight to the problem and enables us to derive, in O(|E| log |E|) time, a solution with value no more than twice the k-center optimal value. A by-product of the analysis is an O(|E|) algorithm that identifies a dominating set in G2, the square of a graph G, the size of which is no larger than the size of the minimum dominating set in the graph G. The key combinatorial object used is called a strong stable set, and we prove the NP-completeness of the corresponding decision problem.
Using simple protocols, it is shown how to achieve consensus in constant expected time, within a ... more Using simple protocols, it is shown how to achieve consensus in constant expected time, within a variety of fail-stop and omission failure models. Significantly, the strongest models considered are completely asynchronous. All of the results are based on distributively flipping a coin, which is usable by a significant majority of the processors. Finally, a nearly matching lower bound is also given for randomized protocols for consensus.
In this paper a powerful, and yet simple, technique for devising approximation algorithms for a w... more In this paper a powerful, and yet simple, technique for devising approximation algorithms for a wide variety of NP-complete problems in routing, location, and communication network design is investigated. Each of the algorithms presented here delivers an approximate solution guaranteed to be within a constant factor of the optimal solution. In addition, for several of these problems we can show that unless P = NP, there does not exist a polynomial-time algorithm that has a better performance guarantee.
Proceedings of the AAAI Conference on Artificial Intelligence
Bike-sharing systems are becoming increasingly prevalent in urban environments. They provide a lo... more Bike-sharing systems are becoming increasingly prevalent in urban environments. They provide a low-cost, environmentally-friendly transportation alternative for cities. The management of these systems gives rise to many optimization problems. Chief among these problems is the issue of bicycle rebalancing. Users imbalance the system by creating demand in an asymmetric pattern. This necessitates action to put the system back in balance with the requisite levels of bicycles at each station to facilitate future use. In this paper, we tackle the problem of maintaing system balance during peak rush-hour usageas well as rebalancing overnight to prepare the systemfor rush-hour usage. We provide novel problem formulationsthat have been motivated by both a close collaborationwith the New York City bike share (Citibike) and a careful analysisof system usage data. We analyze system data to discover the best placement of bikes tofacilitate usage. We solve routing problems forovernight shifts as ...
BackgroundWhile booster vaccinations clearly reduce the risk of severe COVID-19 and death, the im... more BackgroundWhile booster vaccinations clearly reduce the risk of severe COVID-19 and death, the impact of boosters on SARS-CoV-2 infection has not been fully characterized: doing so requires understanding their impact on asymptomatic and mildly symptomatic infections that often go unreported but nevertheless play an important role in spreading SARS-CoV-2. We sought to estimate the impact of COVID-19 booster doses on SARS-CoV-2 infection in a vaccinated population of young adults during an Omicron BA.1-predominant period.Methods and FindingsWe implemented a cohort study of young adults in a college environment (Cornell University’s Ithaca campus) from a period when Omicron BA.1 was the predominant SARS-CoV-2 variant on campus (December 5 to December 31, 2021). Participants included 15,800 university students who completed an initial vaccination series with a vaccine approved by the World Health Organization for emergency use, were enrolled in mandatory at-least-weekly surveillance PCR...
Proceedings of the National Academy of Sciences, 2021
Significance Decisions surrounding how to safely reopen universities directly impact 7% of the US... more Significance Decisions surrounding how to safely reopen universities directly impact 7% of the US population (students, staff) and indirectly impact tens of millions more (families, communities). After witnessing large COVID-19 outbreaks among students from August 2020 to the present, universities want to provide safety while minimizing social and financial costs, despite uncertainty about vaccine hesitancy, vaccine efficacy, more transmissible variants with the potential for immune escape, and community prevalence. When the Delta variant is dominant, we find substantial risk reduction in moving student populations from mostly (75%) to fully (100%) vaccinated, in testing vaccinated students once per week even when all students are vaccinated, and in more frequent testing targeted to the most social groups of students.
Historically, linkage mapping populations have consisted of large, randomly selected samples of p... more Historically, linkage mapping populations have consisted of large, randomly selected samples of progeny from a given pedigree or cell lines from a panel of radiation hybrids. We demonstrate that, to construct a map with high genome-wide marker density, it is neither necessary nor desirable to genotype all markers in every individual of a large mapping population. Instead, a reduced sample of individuals bearing complementary recombinational or radiation-induced breakpoints may be selected for genotyping subsequent markers from a large, but sparsely genotyped, mapping population. Choosing such a sample can be reduced to a discrete stochastic optimization problem for which the goal is a sample with breakpoints spaced evenly throughout the genome. We have developed several different methods for selecting such samples and have evaluated their performance on simulated and actual mapping populations, including the Lister and Dean Arabidopsis thaliana recombinant inbred population and the ...
We consider constrained versions of the prize-collecting traveling salesman and the prize-collect... more We consider constrained versions of the prize-collecting traveling salesman and the prize-collecting minimum spanning tree problems. The goal is to maximize the number of vertices in the returned tour/tree subject to a bound on the tour/tree cost. Rooted variants of the problems have the additional constraint that a given vertex, the root, must be contained in the tour/tree. We present a 2-approximation algorithm for the rooted and unrooted versions of both the tree and tour variants. The algorithm is based on a parameterized primal–dual approach. It relies on first finding a threshold value for the dual variable corresponding to the budget constraint in the primal and then carefully constructing a tour/tree that is, in a precise sense, just within budget. We improve upon the best-known guarantee of 2 + ε for the rooted and unrooted tour versions and 3 + ε for the rooted and unrooted tree versions. Our analysis extends to the setting with weighted vertices, in which we want to maxim...
In this paper we present a 2-approximation algorithm for the k-center problem with triangle inequ... more In this paper we present a 2-approximation algorithm for the k-center problem with triangle inequality. This result is “best possible” since for any δ < 2 the existence of δ-approximation algorithm would imply that P = NP. It should be noted that no δ-approximation algorithm, for any constant δ, has been reported to date. Linear programming duality theory provides interesting insight to the problem and enables us to derive, in O(|E| log |E|) time, a solution with value no more than twice the k-center optimal value. A by-product of the analysis is an O(|E|) algorithm that identifies a dominating set in G2, the square of a graph G, the size of which is no larger than the size of the minimum dominating set in the graph G. The key combinatorial object used is called a strong stable set, and we prove the NP-completeness of the corresponding decision problem.
Using simple protocols, it is shown how to achieve consensus in constant expected time, within a ... more Using simple protocols, it is shown how to achieve consensus in constant expected time, within a variety of fail-stop and omission failure models. Significantly, the strongest models considered are completely asynchronous. All of the results are based on distributively flipping a coin, which is usable by a significant majority of the processors. Finally, a nearly matching lower bound is also given for randomized protocols for consensus.
In this paper a powerful, and yet simple, technique for devising approximation algorithms for a w... more In this paper a powerful, and yet simple, technique for devising approximation algorithms for a wide variety of NP-complete problems in routing, location, and communication network design is investigated. Each of the algorithms presented here delivers an approximate solution guaranteed to be within a constant factor of the optimal solution. In addition, for several of these problems we can show that unless P = NP, there does not exist a polynomial-time algorithm that has a better performance guarantee.
Uploads
Papers by David Shmoys