15 citations · 28 across the 13 of their papers we have counts for
18 papers
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…
Sequential Pricing with Deadlines and Correlated Buyers
Shruti Penumatsa, Rajan Udwani
We study sequential posted pricing for selling a single item under an exogenous deadline: a seller makes take-it-or-leave-it price offers to buyers one at a time, stopping when som…
Modern Primal-Dual Frameworks for Prior-Free Online Resource Allocation
Rad Niazadeh, Rajan Udwani
Linear-programming (LP)-based primal-dual methods are fundamental for designing and analyzing algorithms in adversarial (prior-free) online resource allocation. This chapter provid…
A Markovian Approach for Cross-Category Complementarity in Choice Modeling
Omar El Housni, Shuo Sun, Rajan Udwani
While single-purchase choice models have been widely studied in assortment optimization, customers in modern retail and e-commerce environments often purchase multiple items across…
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…
A Unified Algorithmic Framework for Dynamic Assortment Optimization under MNL Choice
Shuo Sun, Rajan Udwani, Zuo-Jun Max Shen
We consider assortment and inventory planning problems with dynamic stockout-based substitution effects, and without replenishment, in two different settings: (1) Customers can see…
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…
Submodular Order Functions and Assortment Optimization
Rajan Udwani
We define a new class of set functions that in addition to being monotone and subadditive, also admit a very limited form of submodularity defined over a permutation of the ground…
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\}…