45 citations · 204 across the 40 of their papers we have counts for
21 papers · 1 filter
Dynamic Matching with Abandonment: Optimal Guarantees via Static Priority Policies
Nick Arnosti, Rad Niazadeh, Pranav Nuti +1
We study stochastic dynamic matching with abandonment, a fundamental model in which agents of different types arrive over time, may abandon the market while waiting, and can be mat…
Non-Exclusive Notifications for Ride-Hailing at Lyft I: Single-Cycle Approximation Algorithms
Farbod Ekbatani, Rad Niazadeh, Shruti Penumatsa +11
Ride-hailing platforms increasingly rely on non-exclusive notifications--broadcasting a single request to multiple drivers simultaneously--to mitigate inefficiencies caused by unce…
Near-Optimal Bayesian Online Assortment of Reusable Resources
Yiding Feng, Rad Niazadeh, Amin Saberi
Motivated by the applications of rental services in e-commerce, we consider revenue maximization in online assortment of reusable resources for a stream of arriving consumers with…
Robustness of Online Inventory Balancing to Inventory Shocks
Yiding Feng, Rad Niazadeh, Amin Saberi
In classic adversarial online resource allocation problems such as AdWords, customers arrive online while products are given offline with a fixed initial inventory. To ensure reven…
Robust Dynamic Staffing with Predictions
Yiding Feng, Vahideh Manshadi, Rad Niazadeh +1
We consider a natural dynamic staffing problem in which a decision-maker sequentially hires workers over a finite horizon to meet an unknown demand revealed at the end. Predictions…
Online Job Assignment
Farbod Ekbatani, Yiding Feng, Ian Kash +1
Motivated primarily by applications in cloud computing, we study a simple, yet powerful, online allocation problem in which jobs of varying durations arrive over continuous time an…
Markovian Search with Ex-Ante Constraints: Theory and Applications to Socially Aware Algorithmic Hiring
Mohammad Reza Aminian, Vahideh Manshadi, Rad Niazadeh
We develop an algorithmic framework to incorporate "ex-ante" constraints on outcomes (that hold only on average) into stateful sequential search with costly inspection. Our framewo…
Dynamic Matching with Post-allocation Service and its Application to Refugee Resettlement
Kirk Bansak, Soonbong Lee, Vahideh Manshadi +2
Motivated by our collaboration with a major refugee resettlement agency in the U.S., we study a dynamic matching problem where each new arrival (a refugee case) must be matched imm…
Prophet Inequalities with Cancellation Costs
Farbod Ekbatani, Rad Niazadeh, Pranav Nuti +1
Most of the literature on online algorithms and sequential decision-making in revenue management focuses on settings with irrevocable decisions. Motivated by modern applications su…
Batching and Optimal Multi-stage Bipartite Allocations
Yiding Feng, Rad Niazadeh
In several applications of real-time matching of demand to supply in online marketplaces, the platform allows for some latency to batch the demand and improve the efficiency. Motiv…
Two-stage Stochastic Matching and Pricing with Applications to Ride Hailing
Yiding Feng, Rad Niazadeh, Amin Saberi
Matching and pricing are two critical levers in two-sided marketplaces to connect demand and supply. The platform can produce more efficient matching and pricing decisions by batch…
Online Resource Allocation with Cancellations
Farbod Ekbatani, Yiding Feng, Rad Niazadeh
We initiate the study of two-sided online resource allocation with costly cancellations within the buyback model. Our focus is on edge-weighted online matching and several of its e…
Bernoulli Factories for Flow-Based Polytopes
Rad Niazadeh, Renato Paes Leme, Jon Schneider
We construct explicit combinatorial Bernoulli factories for the class of \emph{flow-based polytopes}; integral 0/1-polytopes defined by a set of network flow constraints. This gene…
Online Bipartite Matching with Reusable Resources
Steven Delong, Alireza Farhadi, Rad Niazadeh +2
We study the classic online bipartite matching problem with a twist: offline vertices, called resources, are . In particular, when a resource is matched to an on…
Combinatorial Bernoulli Factories
Rad Niazadeh, Renato Paes Leme, Jon Schneider
A Bernoulli factory is an algorithmic procedure for exact sampling of certain random variables having only Bernoulli access to their parameters. Bernoulli access to a parameter $p…
Hierarchical Clustering for Euclidean Data
Moses Charikar, Vaggos Chatziafratis, Rad Niazadeh +1
Recent works on Hierarchical Clustering (HC), a well-studied problem in exploratory data analysis, have focused on optimizing various objective functions for this problem under arb…
Hierarchical Clustering better than Average-Linkage
Moses Charikar, Vaggos Chatziafratis, Rad Niazadeh
Hierarchical Clustering (HC) is a widely studied problem in exploratory data analysis, usually tackled by simple agglomerative procedures like average-linkage, single-linkage or co…
Optimal Algorithms for Continuous Non-monotone Submodular and DR-Submodular Maximization
Rad Niazadeh, Tim Roughgarden, Joshua R. Wang
In this paper we study the fundamental problems of maximizing a continuous non-monotone submodular function over the hypercube, both with and without coordinate-wise concavity. Thi…
Hierarchical Clustering with Structural Constraints
Vaggos Chatziafratis, Rad Niazadeh, Moses Charikar
Hierarchical clustering is a popular unsupervised data analysis method. For many real-world applications, we would like to exploit prior information about the data that imposes con…
Secretary Problems with Non-Uniform Arrival Order
Thomas Kesselheim, Robert Kleinberg, Rad Niazadeh
For many online problems, it is known that the uniform arrival order enables the design of algorithms with much better performance guarantees than under worst-case. The quintessent…
A Unified Approach to Online Allocation Algorithms via Randomized Dual Fitting
Rad Niazadeh, Robert D. Kleinberg
We present a unified framework for designing and analyzing algorithms for online budgeted allocation problems (including online matching) and their generalization, the Online Gener…