15 citations · 28 across the 13 of their papers we have counts for
14 papers · 1 filter
Online Matching with Arbitrary Stochastic Rewards
Rajan Udwani
Online matching with stochastic rewards is a generalization of online bipartite matching in which an attempt to match an online arrival to an offline resource may fail with some pr…
Online Submodular Welfare Maximization: Computation is not the Bottleneck
Rajan Udwani, David Wajc
We revisit the online submodular welfare maximization problem (OSW), a vast generalization of numerous well-studied online allocation problems, including online bipartite matching,…
The Power of Flexible Budgets in Adwords
Suho Kang, Rajan Udwani
Search advertising platforms routinely spend beyond an advertiser's average daily budget on high-traffic days, so long as total spending over the month stays within the monthly bud…
A Black-Box Approach for Exogenous Replenishment in Online Resource Allocation
Suho Kang, Ziyang Liu, Rajan Udwani
In a typical online resource allocation problem, we start with a fixed inventory of resources and make online allocation decisions in response to resource requests that arrive sequ…
Optimality of Non-Adaptive Algorithms in Online Submodular Welfare Maximization with Stochastic Outcomes
Rajan Udwani
We generalize the problem of online submodular welfare maximization to incorporate various stochastic elements that have gained significant attention in recent years. We show that…
Almost Tight Bounds for Online Hypergraph Matching
Thorben Tröbst, Rajan Udwani
In the online hypergraph matching problem, hyperedges of size over a common ground set arrive online in adversarial order. The goal is to obtain a maximum matching (disjoint se…
When Location Shapes Choice: Placement Optimization of Substitutable Products
Omar El Housni, Rajan Udwani
Strategic product placement can have a strong influence on customer purchase behavior in physical stores as well as online platforms. Motivated by this, we consider the problem of…
When Stochastic Rewards Reduce to Deterministic Rewards in Online Bipartite Matching
Rajan Udwani
We study the problem of vertex-weighted online bipartite matching with stochastic rewards where matches may fail with some known probability and the decision maker has to adapt to…
Periodic Reranking for Online Matching of Reusable Resources
Rajan Udwani
We consider a generalization of the vertex weighted online bipartite matching problem where the offline vertices, called resources, are reusable. In particular, when a resource is…
Adwords with Unknown Budgets and Beyond
Rajan Udwani
In the classic Adwords problem introduced by Mehta et al.\ (2007), we have a bipartite graph between advertisers and queries. Each advertiser has a maximum budget that is known a p…
Online Allocation of Reusable Resources via Algorithms Guided by Fluid Approximations
Vineet Goyal, Garud Iyengar, Rajan Udwani
We consider the problem of online allocation (matching and assortments) of reusable resources where customers arrive sequentially in an adversarial fashion and allocated resources…
Asymptotically Optimal Competitive Ratio for Online Allocation of Reusable Resources
Vineet Goyal, Garud Iyengar, Rajan Udwani
We consider the problem of online allocation (matching, budgeted allocations, and assortments) of reusable resources where an adversarial sequence of resource requests is revealed…
Online Matching with Stochastic Rewards: Optimal Competitive Ratio via Path Based Formulation
Vineet Goyal, Rajan Udwani
The problem of online matching with stochastic rewards is a generalization of the online bipartite matching problem where each edge has a probability of success. When a match is ma…
Multi-Objective Maximization of Monotone Submodular Functions with Cardinality Constraint
Rajan Udwani
We consider the problem of multi-objective maximization of monotone submodular functions subject to cardinality constraint, often formulated as $\max_{|A|=k}\min_{i\in\{1,\dots,m\}…