Dynamic Service Recommendation with Congestion-Dependent Joining: Near-Optimal and Constant-Factor Approximation Algorithms
Listen
Radio episode about this paper
Transcript
Introduction to the show: ident: Mathematics. The day in mathematics: new theorems, new proofs, and what they open.
Ada: We're looking at the paper: "Dynamic Service Recommendation with Congestion-Dependent Joining".
Title and authors: Ada: So, looking at the title again, "Dynamic Service Recommendation with Congestion-Dependent Joining: Near-Optimal and Constant-Factor Approximation Algorithms," it really tells you what the paper is about—they aren't just looking for *any* policy that works; they are aiming for two different levels of performance guarantee.
Emmy: It means they have an algorithm that gets you very close to the absolute best possible outcome, near-optimal, and another one that gives you a reliable constant factor approximation under different assumptions.
Kolya: I wonder if the "near-optimal" result is achievable in practice, or if it just holds up theoretically because of some specific mathematical structure they've found.
Ada: That’s a good question for Kolya. The paper suggests that this near-optimality comes from using a quasi polynomial time approximation scheme, which means the runtime depends on something like epsilon raised to the power of n, which is manageable when you have many services.
Emmy: And the constant factor algorithm uses something different—it relies on looking at marginal information about each service individually rather than tracking every single queue length together.
Kolya: That sounds like a practical trade-off: you can get very close to the best result, but maybe you have to deal with more complex setup for that near-optimal version.
The paper's summary: Ada: So, what the paper summarizes is that they formulate this as a finite horizon, discrete time stochastic optimization problem where the platform makes recommendations over T periods and tries to maximize its expected net revenue.
Emmy: They set up n parallel services, indexed by j, with queues Q j representing how many customers are waiting at each service at the beginning of a period. The key constraint is that customer joining probabilities change based on the current congestion levels in all services.
Kolya: The paper points out that because of this joint congestion state, tracking everything becomes computationally impossible, which is the big hurdle they're addressing with their approximation methods.
Ada: To summarize the core problem: we have a system where your decision today impacts future customers' chances of joining, and you need to make decisions over time to maximize revenue.
Emmy: They then introduce two ways to solve this: first, a quasi polynomial time scheme that compresses the joint state into something manageable using histograms and rounding, and second, an LP guided algorithm that uses marginal service information.
Kolya: The LP guided approach sounds interesting because it bypasses tracking every single queue length by using auxiliary virtual queues to bridge the gap between the linear program solution and the real system dynamics.
The paper's improvements: Ada: Regarding improvements, they focus on making these two approaches more usable. The quasi polynomial time scheme compresses the state space by rounding parameters and using a histogram of queue lengths for each service type, which cuts down the exponential dependence on the number of services.
Emmy: And that histogram approach is crucial because it exploits a structural insight: customers become less likely to join as a service gets more congested, which is what they call monotone joining behavior.
Kolya: That monotonicity part seems critical; the paper explicitly states that without this joining behavior, the problem becomes NP-hard to approximate within any constant factor. So this structure is what makes it tractable in the first place.
Ada: And then there’s the LP guided algorithm, which uses marginal occupancy linear programming with these virtual queues to get a one minus one over e approximation guarantee under much more general assumptions than what the quasi polynomial scheme needs.
Emmy: So, you have this near-optimal scheme exploiting the specific structure of their model primitives, and then you have this constant factor version that works under broader conditions, as long as that monotonicity holds.
Conclusion: Ada: To wrap up, the paper shows that endogenous customer responses to congestion introduce tractability when they have an economically natural structure like monotonicity. That's the big structural finding here.
Emmy: And they provide two distinct tools to handle the computational burden: one for near-optimality by exploiting those structural details, and another for a constant factor approximation using service-level marginal data.
Kolya: I think the takeaway is that if you can't assume that joining behavior is monotone, then approximating this problem within any constant factor becomes NP-hard, which really sets a boundary on what we can expect to find easily.
Ada: So we have two powerful algorithms now: QPTAS for near-optimality and LPGA for a constant factor guarantee when the system dynamics are more general but still monotone.
Emmy: It’s a very clear way to approach these complex intertemporal problems by either exploiting deep structure or using clever linear programming techniques to manage the state space.
Kolya: It’s interesting how they built that reduction from maximum independent set to show the inapproximability when monotonicity is lost, because it really connects this service recommendation problem to other hard problems.
Ada: That connection shows why understanding those underlying constraints, like customer joining behavior, is so important for designing scalable AI systems for real-world services.
University College London · Mitch Daniels School of Business, Purdue University
math.OC
Submitted: 2026-09-25
Updated: 2026-11-16
License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
Importance score: 99/100
The gist: Modern service platforms face an intertemporal tradeoff when recommending services, as directing a customer to a service might yield immediate value but increase congestion…
Key concepts
- Markov Decision Process (MDP)
- An MDP is a mathematical framework used to model decision-making processes where the future state depends only on the current state. In this study, it models how a platform chooses which service to recommend based on current congestion levels, aiming to maximize total expected revenue over time.
- Quasi-Polynomial-Time Approximation Scheme (QPTAS)
- This algorithm finds a near-optimal policy by simplifying the complex joint state of all services into a manageable histogram. It achieves this by truncating queue lengths and rounding parameters, allowing it to run in time that is quasi-polynomial relative to the number of services and the planning horizon.
- LP-Guided Algorithm (LPGA)
- This method avoids tracking every possible joint state by focusing on service-level marginal information. It uses Linear Programming (LP) solutions combined with auxiliary virtual queues to construct a feasible policy, providing a robust constant-factor approximation guarantee even under more general system assumptions.
Terminology
Summary
Modern service platforms face an intertemporal tradeoff when recommending services, as directing a customer to a service might yield immediate value but increase congestion, thereby reducing future attractiveness for subsequent customers. p. 0 This study addresses this using a finite-horizon stochastic optimization problem formulated as a Markov Decision Process (MDP), where the platform dynamically recommends among multiple services represented by queues whose joining probabilities decrease with congestion. p. 0 The optimal policy generally depends on the joint congestion state across all services, leading to a prohibitively large state space of size O(T n). p. 0
To tackle this curse of dimensionality, two complementary approximation algorithms are developed:
-
Quasi-Polynomial-Time Approximation Scheme (QPTAS): This scheme compresses the joint congestion state into a histogram representation by using truncation and rounding of model primitives. The resulting algorithm has a runtime of O(T times n O(epsilon-1)) and achieves an expected net revenue of at least (1 - epsilon)OPT. p. 4
-
Polynomial-Time LP-Guided Algorithm (LPGA): This algorithm avoids the joint-state representation by utilizing service-level marginal information. It constructs a feasible policy using auxiliary virtual queues that bridge the gap between the Linear Programming (LP) solution and actual system dynamics, achieving a (1 - 1/e) -approximation guarantee under substantially more general service and joining dynamics. p. 0
The study establishes that monotone joining behavior—where customers become less likely to join as a service becomes more congested—is fundamental to tractability. Without this monotonicity, the problem is NP-hard to approximate within any constant factor. p. 0 The LPGA maintains its (1 - 1/e) approximation guarantee under general monotone joining probabilities and discrete service-capacity distributions. p. 5
The QPTAS achieves compression by rounding parameters, truncating queue lengths, and employing a histogram of queue lengths for each service type. p. 5 The LPGA constructs a policy via marginal occupancy linear programming using auxiliary virtual queues to achieve an expected net revenue of at least 1 - 1/e OPT. p. 4 These two algorithms offer complementary approaches: QPTAS exploits structure in model primitives for near-optimality, while LPGA uses service-level marginal information for a constant-factor approximation under more general assumptions. p. 6
The proof structure involves several key components:
-
Policy Transfer and Comparison: A section proves that the optimal deterministic policy for a fully rounded system is bounded below by beta times the optimal policy for the original system, establishing bounds on expected revenue. This involves constructing a policy for the original system by maintaining a virtual copy of the fully rounded system and coupling it with an auxiliary partially rounded system using independent uniform random variables to establish queue-length ordering results. p. 5
-
Inapproximability Results: Theorem 3 demonstrates that for any fixed epsilon > 0, the problem is NP-hard to approximate within a factor of O(n 1-epsilon) when joining probabilities are allowed to be nonmonotone. This highlights monotonicity as a crucial structural property enabling tractability. p. 0
-
Reduction from Max-IS: The proof of Theorem 3 utilizes an approximation-preserving mapping between the Maximum Independent Set (Max-IS) problem and the general Dynamic Service Recommendation (DSR) problem. A reduction is constructed where an instance of Max-IS maps to a DSR instance with n services and horizon T = m + nL. p. 9 The proof shows that any approximation algorithm for DSR would yield a polynomial-time n 1-epsilon/2-approximation for Max-IS, contradicting known inapproximability results. p. 6 This reduction relies on specific constructions for the joining probability function and policy (pi S) based on an independent set S. p. 6
In summary, the paper concludes that endogenous customer responses to congestion introduce computational tractability when they possess an economically natural structure, such as monotonicity. p. 1 The QPTAS and LPGA provide distinct methods to overcome the state-space complexity: QPTAS for near-optimality exploiting structure, and LPGA for a constant-factor approximation under broader conditions. p. 6
Green — the paper says it, and the page is printed. Red — no passage carries it, so treat that sentence as unverified. The same check runs on your own text: check a summary against its source, $5.
Improvements for AI systems
-
Quasi-polynomial-time approximation scheme (QPTAS) for Dynamic Service Recommendation (DSR) allows an AI system to find a policy whose expected net revenue is at least one minus epsilon times the optimal value, achieving this in time quasi-polynomial in both the number of services and the planning horizon.
-
A polynomial-time approximation algorithm based on linear programming can be used to compute a policy with a one minus one over e approximation guarantee under substantially more general modeling assumptions than those required for QPTAS.
-
The system can leverage structural insights from service parameters by compressing the state space into a histogram of queue lengths for each service type, reducing the exponential dependence on the number of services to quasi-polynomial time.
-
The LP-guided algorithm can implement a policy that utilizes marginal queue-state information and constructs virtual queues whose marginal occupancy distributions exactly reproduce the optimal linear program solution.
-
The system can utilize a contention resolution mechanism to convert fractional matching probabilities from the LP solution into feasible online decisions, ensuring at most one service is recommended per period while maintaining approximation quality.
-
The AI system can be designed to exploit monotonicity in customer joining behavior; without this property, the problem becomes NP-hard to approximate within any constant factor.
-
The system can implement a policy that uses a virtual copy of the original system coupled with the actual rounded-down system, allowing for comparison of queue lengths and service completion rates under different model primitives.
-
By employing parameter rounding, truncation, and joining probability adjustments, the AI can transform an instance into a modified DSR problem where an optimal deterministic Markov policy can be computed in quasi-polynomial time.
Sources
- Improved Approximations for Stationary Bipartite Matching: Beyond Probabilistic Independence
- Constant-Factor Algorithms for Revenue Management with Consecutive Stays
- Sequential Selection with Expirations
Related papers
- An Accelerated Proximal Gradient Method for Bures-Wasserstein Space
- FOMTools: Development and AI-Assisted Code Generation for First-Order Methods
- Lions and Muons: Optimization via Stochastic Frank-Wolfe under Heavy-Tailed Noise
- Integrating Learning and Optimization for Open Transport Capacity Pooling under Disruption
- Zeroth-Order Gradient Estimators under Decision-Dependent Noise
- Breaking the Stochasticity Barrier: An Adaptive Variance-Reduced Method for Variational Inequalities