no. 17 · Wednesday 18 November 2026
Dynamic Service Recommendation with Congestion-Dependent Joining: Near-Optimal and Constant-Factor Approximation Algorithms
Abstract
Modern service platforms often show customers real-time congestion information, such as anticipated waiting times, before they decide whether to use a service. This creates an intertemporal tradeoff: directing a customer to a service may generate immediate value, but the resulting congestion can make that service less attractive to future customers. We study this tradeoff in a finite-horizon problem in which a platform recommends one of multiple services, each represented by a queue, and customers' joining probabilities decrease with congestion. We show that optimal recommendations generally depend on the joint congestion state and cannot be reduced to indices that depend only on each service's own state. Hence, exact dynamic programming suffers from a curse of dimensionality. We develop approximation algorithms that retain progressively less of this joint state. First, we construct a quasi-polynomial-time approximation scheme that achieves a $(1-ε)$-approximation for any $ε>0$. It rounds the model primitives and truncates the relevant queue lengths to compress the joint state into a histogram over service types, and our coupling arguments bound the resulting revenue loss. Second, under general monotone joining and service capacities, we study policies that retain only per-service information. A greedy policy, which uses only each service's current queue length, is a tight $1/2$-approximation, as it ignores the congestion externality that a customer imposes on later customers. An LP-guided algorithm that plans each service's queue-length distribution over the horizon accounts for this externality and achieves a $(1-1/e)$-approximation. Finally, monotone joining is what makes the problem tractable: with nonempty initial queues, both constant-factor guarantees hold under monotonicity, whereas without it the problem is NP-hard to approximate within any constant factor.
- fields
- Optimization and Control