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 nonfederal websites. Their policies may differ from this site.

In this paper, we consider a setting inspired by spatial crowdsourcing platforms, where both workers and tasks arrive at different times, and each workertask 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 timestep 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 TwoSided Arrival" (OTATSA), is a significant generalization of the classical online taskassignment problem when all the tasks are statically available. For the general case of OTATSA, we present an optimal nonadaptive algorithm (NADAP), which achieves a competitive ratio (CR) of at least 0.295. For a special case of OTATSA 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 nonadaptive can achieve a CR larger than that of NADAP, establishing the optimality of NADAP among all nonadaptive 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 OTATSA when every assignment yields a uniform reward. At the heart of our analysis is a new technical tool, called "twostage birthdeath process", which is a refined notion of the classical birthdeath process. We believe it may be of independent interest. Finally, we perform extensive numerical experiments on a realworld rideshare dataset collected in Chicago and a synthetic dataset, and results demonstrate the effectiveness of our proposed algorithms in practice.more » « lessFree, publiclyaccessible full text available March 11, 2025

Bipartitematching markets pair agents on one side of a market with agents, items, or contracts on the opposing side. Prior work addresses online bipartitematching markets, where agents arrive over time and are dynamically matched to a known set of disposable resources. In this article, we propose a new model, Online Matching with (offline) Reusable Resources under Known Adversarial Distributions ( OMRRKAD ) , in which resources on the offline side are reusable instead of disposable; that is, once matched, resources become available again at some point in the future. We show that our model is tractable by presenting an LPbased nonadaptive algorithm that achieves an online competitive ratio of ½ϵ for any given constant ϵ > 0. We also show that no adaptive algorithm can achieve a ratio of ½ + o (1) based on the same benchmark LP. Through a datadriven analysis on a massive openly available dataset, we show our model is robust enough to capture the application of taxi dispatching services and ridesharing systems. We also present heuristics that perform well in practice.more » « less

This paper studies how neural network architecture affects the speed of training. We introduce a simple concept called gradient confusion to help formally analyze this. When gradient confusion is high, stochastic gradients produced by different data samples may be negatively correlated, slowing down convergence. But when gradient confusion is low, data samples interact harmoniously, and training proceeds quickly. Through theoretical and experimental results, we demonstrate how the neural network architecture affects gradient confusion, and thus the efficiency of training. Our results show that, for popular initialization techniques, increasing the width of neural networks leads to lower gradient confusion, and thus faster model training. On the other hand, increasing the depth of neural networks has the opposite effect. Our results indicate that alternate initialization techniques or networks using both batch normalization and skip connections help reduce the training burden of very deep networks.more » « less

Efficient allocation of tasks to workers is a central problem in crowdsourcing. In this paper, we consider a special setting inspired by spatial crowdsourcing platforms where both workers and tasks arrive dynamically. Additionally, we assume all tasks are heterogeneous and each workertask assignment brings a known reward. The natural challenge lies in how to incorporate the uncertainty in the arrivals from both workers and tasks into our online allocation policy such that the total expected reward is maximized. To formulate this, we assume the arrival patterns of worker “types” and task “types” can be predicted from historical data. Specifically, we consider a finite time horizon T and assume that in each timestep, a single worker and task are sampled (i.e., “arrive”) from two respective distributions independently, and that this sampling process repeats identically and independently for the entire T online timesteps. Our model, called Online Task Assignment with TwoSided Arrival (OTATSA), is a significant generalization of the classical online task assignment where the set of tasks is assumed to be available offline. For the general version of OTATSA, we present an optimal nonadaptive algorithm which achieves an online competitive ratio of 0.295. For the special case of OTATSA where the reward is a function of just the worker type, we present an improved algorithm (which is adaptive) and achieves a competitive ratio of at least 0.343. On the hardness side, along with showing that the ratio obtained by our nonadaptive algorithm is the best possible among all nonadaptive algorithms, we further show that no (adaptive) algorithm can achieve a ratio better than 0.581 (unconditionally), even for the special case of OTATSA with homogenous tasks (i.e., all rewards are the same). At the heart of our analysis lies a new technical tool (which is a refined notion of the birthdeath process), called the twostage birthdeath process, which may be of independent interest. Finally, we perform numerical experiments on two realworld datasets obtained from crowdsourcing platforms to complement our theoretical results.more » « less

Columnsparse packing problems arise in several contexts in both deterministic and stochastic discrete optimization. We present two unifying ideas, (nonuniform) attenuation and multiplechance algorithms, to obtain improved approximation algorithms for some wellknown families of such problems. As three main examples, we attain the integrality gap, up to lowerorder terms, for known LP relaxations for kcolumn sparse packing integer programs (Bansal et al., Theory of Computing, 2012) and stochastic kset packing (Bansal et al., Algorithmica, 2012), and go “half the remaining distance” to optimal for a major integralitygap conjecture of Furedi, Kahn and Seymour on hypergraph matching (Combinatorica, 1993).more » « less