{"id":"4ea4f166-8171-4d3f-a5e5-104bb4f14ef3","arxiv_id":"2501.08775","paper_version":2,"verdict":"CONDITIONAL","confidence":"MODERATE","novelty_score":8.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":1,"one_line_summary":"Adaptive queue-length-based matching policies can be approximated to within (1 minus epsilon) in polynomial time for constant-size networks and for fixed-dimensional Euclidean networks with abandonment.","lead":"This paper gives the first near-optimal polynomial-time algorithms for dynamic bipartite matching when suppliers wait in queues and may abandon: a fully polynomial approximation for networks with a constant number of supplier types, and a polynomial approximation for fixed-dimensional spatial networks. The point is that policies that use real-time queue lengths can be computed efficiently, instead of settling for constant-factor static policies.","discovery_kind":"new_method","skeptic_critique":{"model":"deepseek-v4-flash","headline":"Lemma 5's intensity matrix for short queues is inconsistent with Algorithm 1, invalidating the tracking claim that underpins the network match-rate analysis.","rationale":"I read the paper in good faith and find the overall program plausible: the hybrid LP decomposition and Priority Rounding are creative, and the appendices are extensive. However, the single most load-bearing point is not Lemma 3/4 as the reader suggested, but the correctness of Lemma 5, which asserts that the short-queue process exactly tracks the NLP marginals. The intensity matrix written in B.3 has an off-by-one error in the death rate (ℓ_i+1 instead of ℓ_i). This is a concrete algebraic inconsistency, not a matter of consensus: the displayed Q does not satisfy the global balance equations with the claimed stationary distribution. Lemma 5 is used throughout Section 3.3—through equation (14) and the analysis of contentious customer types—to translate LP match rates into actual policy match rates. If the Q matrix is not corrected, the network FPTAS loses its central tracking guarantee. The issue may be a simple typo, and if so the theorem could survive after correction; but as written, the proof is incomplete. I therefore keep the conditional verdict but shift the focus to this technical gap, and I recommend the authors re-derive the transition rates from Algorithm 1 and verify Lemma 5's balance equations.","tokens_in":58374,"tokens_out":7048,"duration_ms":68099,"concrete_test":"For a single short queue with one customer type, solve the NLP for some ε and target τ*, then compute the stationary distribution of the birth-death process induced by Algorithm 1 (death rate from ℓ: match rate from the conditional distribution x^ℓ_M/∑x plus ℓ) and compare it to ∑_M x^ℓ_M; also verify whether π Q = 0 using the Q from B.3. If they differ, Lemma 5 is false and must be corrected (likely the ℓ_i+1 should be ℓ_i) before Theorem 1 can be accepted.","verdict_should_be":"CONDITIONAL","load_bearing_attack":"Lemma 5 (Appendix B.3) claims that under Priority Rounding, the short-queue process has stationary distribution π(ℓ)=∑_M x^ℓ_M given by the NLP solution. The displayed intensity matrix Q has death rate Q_{ℓ,ℓ−e_i} = [∑_M x^ℓ_M (γ(M_i)+ℓ_i+1)]/[∑_M x^ℓ_M]. But Algorithm 1's actual death rate from state ℓ for queue i is the abandonment rate ℓ_i plus the match rate ∑_M x^ℓ_M γ(M_i)/∑_M x^ℓ_M, i.e., the numerator should be (γ(M_i)+ℓ_i), not (γ(M_i)+ℓ_i+1). With the stated Q, the global balance equation for π(ℓ) is violated: the outflow to ℓ−e_i is inflated by an extra ∑_M x^ℓ_M, while the inflow from ℓ+e_i uses the correct rate (γ(M_i)+ℓ_i+1). Hence π Q ≠ 0 and Lemma 5 does not follow from equation (8). Since equation (14), Lemma 8, and the entire match-rate accounting for contentious types in §3.3 rely on this tracking, the proof of Theorem 1 is incomplete as written.","agreement_with_reader":"disagree"},"referee_report":{"model":"deepseek-v4-flash","summary":"The paper studies a continuous-time dynamic bipartite matching problem with Poisson supplier arrivals, uniform abandonment, and customers that must be matched upon arrival. The goal is a bi-criteria cost-throughput guarantee: expected long-term average cost at most c* while total match rate is at least τ*. The main result (Theorem 1) is an FPTAS for networks with a constant number of supplier queues, based on a hybrid Network LP that treats 'short' queues with state-dependent variables and 'long' queues with static variables, rounded online by the Priority Rounding policy. Corollary 1 extends this to a PTAS for Euclidean networks of fixed dimension via cell decomposition and clustering. The central technical claims are: exact single-queue Dynamic LP (Lemma 1), bounded-policy approximation for monotone policies (Lemma 3), bounded ℓ in the Network LP (Lemma 4), tracking of short queues (Lemma 5), and stability of virtual buffers (Lemma 7).","tokens_in":58662,"tokens_out":11889,"duration_ms":119468,"significance":"If the proof is completed, the result is significant: it replaces constant-factor static-policy guarantees with near-optimal adaptive policies for a natural class of matching queues with abandonment, and it gives the first (F)PTAS-type results for this model. The hybrid LP relaxation, the short/long queue decomposition, and the virtual-buffer rounding scheme are novel and likely to be influential. The paper is unusually complete in its appendices, with detailed proofs for the single-queue LP, the coupling bound in Lemma 3, the Network LP feasibility reduction, and the Euclidean cell decomposition. However, the proof as written contains a concrete inconsistency in the generator of Lemma 5, and two load-bearing auxiliary claims are either asserted without proof or delegated to an unpublished self-citation; these need to be repaired before the main theorem can be considered established.","major_comments":[{"comment":"The displayed intensity matrix has a spurious '+1' in the death rate. For the real short-queue process under Algorithm 1, the transition from ℓ to ℓ−e_i has rate ℓ_i + Σ_M x^ℓ_M γ(M_i) / Σ_M x^ℓ_M, not [Σ_M x^ℓ_M(γ(M_i)+ℓ_i+1)]/Σ_M x^ℓ_M. With the displayed generator, the measure π(ℓ)=Σ_M x^ℓ_M does not satisfy the global balance equation (8): equation (8) has outflow Σ_M x^ℓ_M(γ(M_i)+ℓ_i), not Σ_M x^ℓ_M(γ(M_i)+ℓ_i+1). Consequently the claimed stationary distribution, and therefore equation (14), do not follow as written. The lemma can be repaired by removing the '+1' from Q; with the corrected generator the conclusion does follow from (8). But as written this is a load-bearing gap, since equation (14) is used in Lemma 8, equation (17), equation (18), and the match-rate accounting in Section 3.3.","section":"Appendix B.3, Lemma 5"},{"comment":"The assertion 'By the pigeonhole principle, there exists κ… such that if we exclude every supplier type with arrival rate in (1/δ^κ, 1/δ^{κ+1}), there exists a policy π with τ(π)≥(1−ε)τ* and c(π)≤c*' is load-bearing because it defines the partition S_short ⊔ S_long and is used in Lemma 4. No proof is provided. The standard empty-interval pigeonhole would require more intervals than supplier types, but the index set has only min{1/ε,n}+1 intervals, which is smaller than n when ε>1/n. The authors should either supply a correct averaging argument over the gaps that accounts for the optimal policy's throughput contribution, or restructure the definition of the gaps so that the removal loss is manifestly O(ε).","section":"Section 3.1"},{"comment":"The proof of Claim 11 relies on the bound SLP* ≤ c(π*_fr), which is asserted by reference to AmaniHamedani et al. (2024, Claim 2.1), an arXiv self-citation. Claim 11 is needed for Lemma 4 in the small-throughput regime τ* ≤ ε²/n, and Lemma 4 is in turn used in the proof of Theorem 1. This is a load-bearing external dependency. Please provide a self-contained proof of the static-LP relaxation, or state and prove the precise version of the cited claim in the appendix.","section":"Appendix B.2, Claim 11"}],"minor_comments":[{"comment":"The transition ℓ → ℓ−e_i in the intensity matrix should be restricted to states with ℓ_i ≥ 1; as written the generator is described for all distinct states but includes invalid downward transitions from ℓ_i = 0.","section":"Appendix B.3"},{"comment":"In the sentence 'we distinguish between two types of customer types C = C^{ct} ⊔ C^{ct}', the two sets are not visually distinguishable in the text. Please use distinct symbols such as C^{ct} and C^{cr} (or C^{contentious} and C^{non-contentious}) consistently through equations (13) and Lemma 8.","section":"Section 3.1"},{"comment":"The notation λ and λ̄ for the short/long cutoff values in Section 3.1 conflicts with the use of λ_i for supplier arrival rates; consider renaming the cutoffs (for example L and ̄L) to avoid confusion.","section":"Section 1.2"}],"recommendation":"major_revision","confidential_remarks":"The central idea is promising and the appendices are extensive, but the current version has a concrete inconsistency in Lemma 5's generator that must be fixed before the tracking argument is valid. In addition, the pigeonhole assertion in Section 3.1 and the external dependency in Claim 11 are load-bearing and need to be made self-contained. These are fixable in revision, so I do not recommend rejection, but the paper should not be accepted in its present form."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"Net: a real advance, but the proof as written has a few holes that need fixing before the details can be trusted. The hybrid LP that separates short and long queues, the priority-rounding policy with virtual buffers, and the random-grid Euclidean reduction are all new ideas, and they are put together in a way that plausibly gives the advertised FPTAS/PTAS. If the main theorem is right, this is the first (1−ε) adaptive scheme for constant-size matching queues and fixed-dimension Euclidean networks, and it partially resolves the Patel–Wajc open question.\n\nThe biggest concrete problem I see is in Lemma 5 (Appendix B.3). The displayed intensity matrix for the short-queue process has death rate Q_{ℓ,ℓ−e_i} proportional to γ(M_i)+ℓ_i+1. Algorithm 1's actual death rate from queue i in state ℓ is γ(M_i)+ℓ_i (matches plus abandonments), and equation (8) is consistent with that. With the printed +1, the proposed stationary distribution π(ℓ)=∑_M x^ℓ_M does not satisfy global balance, so Lemma 5 does not follow as written. This looks like an off-by-one typo rather than a fatal flaw, because the corrected Q does match (8), but the authors need to fix it and check that nothing downstream uses the wrong rate.\n\nThere are a few other soft spots. Claim 11 leans on the validity of a static LP (SLP) from a companion paper (AmaniHamedani et al. 2024, Claim 2.1); the proof here delegates that step. Section 3.1 asserts, by pigeonhole, that deleting the supplier types in one mid-rate interval preserves attainability of (c*,τ*) up to (1−ε); no proof is given in the text. The introduction claims the bi-criteria scheme converts to a reward-maximization FPTAS, but that conversion is not proved anywhere. And Lemma 8's statement uses Ccr/Cct in a way that does not parse with the definitions. None of these by themselves sinks the main theorem, but together they make the paper not yet ready.\n\nThey are, however, all fixable, and the core idea is worth engaging with. This paper deserves a serious referee; I would send it out rather than desk-reject. Readers working on dynamic matching, stochastic online algorithms, or constrained MDPs will get real value from it.","headline":"A genuine FPTAS/PTAS advance for matching queues, with a few proof details that need fixing before publication.","tokens_in":59203,"tokens_out":6082,"would_cite":true,"duration_ms":60956,"reading_group":"yes","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":["68W25","90B22","90C40","68W27"],"pacs":[],"model":"deepseek-v4-flash","headline":"Adaptive matching policies can be computed to near-optimal accuracy in polynomial time for constant-size queue networks.","keywords":["matching markets","Markov decision process","drift analysis","online algorithms","approximation schemes","fully polynomial-time approximation scheme","dynamic bipartite matching","queueing"],"falsifier":"Exhibit a single-queue instance whose optimal policy has a conditional match rate that strictly decreases at some queue length (violating Definition 1), or a monotone policy for which every $K$-bounded approximation with $K=o(\\frac1\\varepsilon\\log\\frac{\\tau_{\\max}}{\\tau})$ loses a constant fraction of throughput—either directly contradicts Lemma 2 or Lemma 3 and would invalidate the FPTAS.","tokens_in":58144,"feed_emoji":"🤝","tokens_out":7753,"duration_ms":72097,"temperature":0.7,"pith_summary":"This paper establishes that adaptive matching policies—decisions that use current queue lengths—can be computed to any desired accuracy in polynomial time, for dynamic bipartite matching with abandonment, when the number of supplier types is fixed or the network is Euclidean in fixed dimension. The main contribution is a fully polynomial-time approximation scheme for the bi-criteria problem of minimizing long-run average cost subject to a minimum match rate. The algorithm works by a new hybrid linear program that treats 'short' queues (likely to be empty) with state-dependent variables and 'long' queues (rarely empty) with static variables, then rounds the LP solution online with a priority rule and a bounded virtual buffer. If the theorems are correct, this replaces constant-factor static-policy guarantees with (1−ε)-approximate adaptive policies for these inputs.","feed_headline":"Near-optimal adaptive matching is now polynomial-time","feed_subtitle":"Static policies left up to 2x cost on the table; hybrid LP plus priority rounding gets within (1−ε).","key_machinery":"The load-bearing object is the Network LP, a hybrid relaxation combining state-dependent occupancy variables—a dynamic LP per queue with global balance constraints—for queues whose probability of being empty is $\\Omega(\\varepsilon)$, with static per-type matching variables for queues that are rarely depleted. The companion Priority Rounding algorithm samples a matching assignment from the LP's distribution, always prioritizes short queues, and defers preempted long-queue matches into a virtual buffer; Lemmas 5–8 show the short-queue state converges to the LP's stationary distribution, long queues remain nonempty with probability $1-O(\\varepsilon)$, and the buffer remains bounded in expectation. The compression step (Lemmas 3 and 4) is what turns the infinite-dimensional LP into a polynomial-size one: monotone policies are approximated by $K$-bounded policies with $K=O(\\frac1\\varepsilon(\\log\\frac{\\tau_{\\max}}{\\tau(\\pi)}+\\log\\frac1\\varepsilon))$, by inflating or deflating birth and death rates and coupling stationary distributions.","core_discovery":"The paper's central claim is that the optimal adaptive policy for constant-size matching-queue networks is computationally tractable: for any attainable cost-throughput target $(c^*,\\tau^*)$ and any $\\varepsilon\\in(0,1)$, the algorithm returns a $(1-\\varepsilon)$-approximate policy in time $\\mathrm{poly}((n/\\varepsilon)^{n^2} m^n |I|)$, with a polynomial-time analogue for Euclidean networks of fixed dimension. The argument rests on an exact configuration LP for a single queue, whose dual reveals that optimal policies are threshold policies monotone in queue length, and on a compression lemma showing every monotone policy has a surrogate that bounds queue lengths by $O(\\frac1\\varepsilon \\log\\frac{\\tau_{\\max}}{\\tau})$ without losing more than a $(1-\\varepsilon)$ factor in throughput. For networks, a hybrid LP separates short and long queues, and the Priority Rounding policy implements its fractional solution online, matching the LP rates up to $O(\\varepsilon)$.","pith_inferences":["The short/long dichotomy suggests a transferable two-timescale design principle for stochastic control: state-dependence is only needed where scarcity can bite; abundant resources can be allocated almost statically. The authors note the multivariate birth–death machinery does not extend to non-bipartite graphs, so that transfer is not immediate.","A natural testable extension is heterogeneous abandonment rates per supplier type; the authors state the Network LP generalizes trivially, but the rounding analysis—especially the virtual-buffer drift argument—depends on uniform abandonment, so the FPTAS is not known to survive that generalization.","One could empirically stress the FPTAS on the same family of 1000 random instances used to demonstrate the adaptivity gap: the algorithm should recover the optimal adaptive DP cost to within $1\\pm\\varepsilon$, and the gap to static policies of up to 208% should shrink accordingly."],"forward_implications":["For any fixed number of supplier types, the entire cost-throughput Pareto frontier is approximable within $1\\pm\\varepsilon$ in time polynomial in the input and $1/\\varepsilon$.","The single-queue reward-maximization problem, previously known only with a 0.656-approximation, inherits a $(1-\\varepsilon)$-approximation scheme from the bi-criteria FPTAS.","Applications with a constant number of biological markers (e.g., organ allocation by blood and tissue type) or a fixed spatial dimension (e.g., ride-hailing) obtain computable near-optimal adaptive policies with a simple short/long queue prioritization rule.","Euclidean networks of fixed dimension admit an efficient PTAS, implying spatial frictions alone do not force a constant-factor gap between static and adaptive matching."],"supporting_citations":[{"why":"Provides the baseline static-threshold policy with best-known 0.656-approximation for n=1 and the counterexample showing a naive network LP relaxation has a constant gap.","marker":"Kessel et al. (2022)"},{"why":"Identifies the open question of which instances admit (F)PTASes and gives the competitive algorithm that this paper's FPTAS improves upon.","marker":"Patel and Wajc (2024)"},{"why":"Introduces the dynamic stochastic matching model under limited time and the static LP relaxation that the hybrid LP refines.","marker":"Aouad and Sarıtaş (2022)"},{"why":"Supplies the infinite-dimensional LP duality theory (transversality) used to derive the dual DLP and the threshold structure of optimal policies.","marker":"Romeijn et al. (1992)"},{"why":"Used for the separation oracle and ellipsoid-based solving of the network LP and its dual.","marker":"Bertsimas and Tsitsiklis (1997)"},{"why":"Gives the then-best competitive ratio for stationary bipartite matching that the bi-criteria FPTAS surpasses.","marker":"AmaniHamedani et al. (2024)"}],"fun_headline_variants":["Adaptive matching queues: near-optimal in polynomial time","Polynomial-time adaptive policies for matching queues","Hybrid LP yields (1−ε)-optimal adaptive matching","From static to adaptive: near-optimal matching now tractable","Adaptive matching: breaking the constant-factor barrier"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"Everything rests on the claim that optimal policies are monotone in queue length and that every monotone policy has a logarithmically bounded surrogate; if either fails, the polynomial-size LP no longer approximates the true optimum.","fun_headline_variants_meta":{"raw":{"variants":["Adaptive matching queues: near-optimal in polynomial time","Polynomial-time adaptive policies for matching queues","Hybrid LP yields (1−ε)-optimal adaptive matching","From static to adaptive: near-optimal matching now tractable","Adaptive matching: breaking the constant-factor barrier"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000179,"raw_usage":{"total_tokens":1338,"prompt_tokens":1018,"completion_tokens":320,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":634,"completion_tokens_details":{"reasoning_tokens":242}},"tokens_in":634,"tokens_out":320,"duration_ms":3354,"temperature":1.0,"reasoning_tokens":242,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-10T20:19:42.689945+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"Exhibit a single-queue instance whose optimal policy has a conditional match rate that strictly decreases at some queue length (violating Definition 1), or a monotone policy for which every $K$-bounded approximation with $K=o(\\frac1\\varepsilon\\log\\frac{\\tau_{\\max}}{\\tau})$ loses a constant fraction of throughput—either directly contradicts Lemma 2 or Lemma 3 and would invalidate the FPTAS.","supporting_citations":[{"cited_title":"E., Smith, R","cited_arxiv_id":null,"evidence_quote":"Supplies the infinite-dimensional LP duality theory (transversality) used to derive the dual DLP and the threshold structure of optimal policies."},{"cited_title":"and Tsitsiklis, J","cited_arxiv_id":null,"evidence_quote":"Used for the separation oracle and ellipsoid-based solving of the network LP and its dual."}],"review_version":1}