skip to main content

Search for: All records

Award ID contains: 1918749

Note: When clicking on a Digital Object Identifier (DOI) number, you will be taken to an external site maintained by the publisher. Some full text articles may not yet be available without a charge during the embargo (administrative interval).
What is a DOI Number?

Some links on this page may take you to non-federal websites. Their policies may differ from this site.

  1. In this paper, we consider a setting inspired by spatial crowdsourcing platforms, where both workers and tasks arrive at different times, and each worker-task assignment yields a given reward. The key challenge is to address the uncertainty in the stochastic arrivals from both workers and the tasks. In this work, we consider a ubiquitous scenario where the arrival patterns of worker “types” and task “types” are not erratic but can be predicted from historical data. Specifically, we consider a finite time horizon T and assume that in each time-step the arrival of a worker and a task can be seen as an independent sample from two (different) distributions. Our model, called "Online Task Assignment with Two-Sided Arrival" (OTA-TSA), is a significant generalization of the classical online task-assignment problem when all the tasks are statically available. For the general case of OTA-TSA, we present an optimal non-adaptive algorithm (NADAP), which achieves a competitive ratio (CR) of at least 0.295. For a special case of OTA-TSA when the reward depends only on the worker type, we present two adaptive algorithms, which achieve CRs of at least 0.343 and 0.355, respectively. On the hardness side, we show that (1) no non-adaptive can achieve a CR larger than that of NADAP, establishing the optimality of NADAP among all non-adaptive algorithms; and (2) no (adaptive) algorithm can achieve a CR better than 0.581 (unconditionally) or 0.423 (conditionally on the benchmark linear program), respectively. All aforementioned negative results apply to even unweighted OTA-TSA when every assignment yields a uniform reward. At the heart of our analysis is a new technical tool, called "two-stage birth-death process", which is a refined notion of the classical birth-death process. We believe it may be of independent interest. Finally, we perform extensive numerical experiments on a real-world ride-share dataset collected in Chicago and a synthetic dataset, and results demonstrate the effectiveness of our proposed algorithms in practice. 
    more » « less
    Free, publicly-accessible full text available March 11, 2025
  2. Free, publicly-accessible full text available February 1, 2025
  3. Vidaver, Anne K. (Ed.)
    Free, publicly-accessible full text available December 19, 2024
  4. Hazen, Terry C. (Ed.)
    Climate change raises an old disease to a new level of public health threat. The causative agent,Vibrio cholerae, native to aquatic ecosystems, is influenced by climate and weather processes. The risk of cholera is elevated in vulnerable populations lacking access to safe water and sanitation infrastructure. Predictive intelligence, employing mathematical algorithms that integrate earth observations and heuristics derived from microbiological, sociological, and weather data, can provide anticipatory decision-making capabilities to reduce the burden of cholera and save human lives. An example offered here is the recent outbreak of cholera in Malawi, predicted in advance by such algorithms. 
    more » « less
    Free, publicly-accessible full text available December 19, 2024
  5. In 2022, one of its worst cholera outbreaks began in Bangladesh, and the Dhaka hospital treated more than 1300 patients and ca. 42,000 diarrheal cases from March-1 to April-10, 2022. Here, we present genomic attributes of V. cholerae O1 responsible for the 2022 Dhaka outbreak and 960 7th pandemic El Tor (7PET) strains from 88 countries. Results show strains isolated during the Dhaka outbreak cluster with 7PET wave-3 global clade strains, but comprise subclade BD-1.2, for which the most recent common ancestor appears to be that responsible for recent endemic cholera in India. BD-1.2 strains are present in Bangladesh since 2016, but not establishing dominance over BD-2 lineage strains until 2018 and predominantly associated with endemic cholera. In conclusion, the recent shift in lineage and genetic attributes, including serotype switching of BD-1.2 from Ogawa to Inaba, may explain the increasing number of cholera cases in Bangladesh. 
    more » « less
    Free, publicly-accessible full text available December 1, 2024
  6. In e-commerce, customers have an unknown patience in terms of how far down the page they are willing to scroll. In light of this, how should products be ranked? The e-commerce retailer’s problem is further complicated by the fact that the supply of each product may be limited, and that multiple customers who are interested in these products will arrive over time. In “Online Matching Frameworks Under Stochastic Rewards, Product Ranking, and Unknown Patience,” Brubach, Grammel, Ma, and Srinivasan provide a general framework for studying this complicated problem that decouples the product ranking problem for a single customer from the online matching of products to multiple customers over time. They also develop a better algorithm for the single-customer product ranking problem under well-studied cascade-click models. Finally, they introduce a model where the products are also arriving over time and cannot be included in the search rankings until they arrive. 
    more » « less
    Free, publicly-accessible full text available October 27, 2024
  7. Free, publicly-accessible full text available October 17, 2024
  8. Free, publicly-accessible full text available August 19, 2024
  9. Set Cover is a fundamental problem in combinatorial optimization which has been studied for many decades due to its various applications across multiple domains. In many of these domains, the input data consists of locations, relationships, and other sensitive information of individuals which may leaked due to the set cover output. Attempts have been made to design privacy-preserving algorithms to solve the Set Cover problem under privacy constraints. Under differential privacy, it has been proved that the Set Cover problem has strong impossibility results and no explicit forms of the output can be released to the public. In this work, we observe that these hardness results dissolve when we turn to the Partial Set Cover problem, where we only need to cover a constant fraction of the elements. We show that this relaxation enables us to avoid the impossibility results, and give the first algorithm which outputs an explicit form of set cover with non-trivial utility guarantees under differential privacy. Using our algorithm as a subroutine, we design a differentially-private bicriteria algorithm to solve a recently-proposed facility-location problem for vaccine distribution which generalizes k-supplier with outliers. Our analysis shows that relaxing the covering requirement also allows us to circumvent the inherent hardness of k-supplier and give the first nontrivial guarantees. 
    more » « less
    Free, publicly-accessible full text available August 19, 2024
  10. Free, publicly-accessible full text available August 19, 2024