pith. machine review for the scientific record. sign in

arxiv: 2605.14195 · v1 · submitted 2026-05-13 · 💻 cs.DS · cs.LG

Recognition: no theorem link

Stochastic Matching via Local Sparsification

Sara Ahmadian , Edith Cohen , Mohammad Roghani
Authors on Pith no claims yet

Pith reviewed 2026-05-15 01:33 UTC · model grok-4.3

classification 💻 cs.DS cs.LG
keywords stochastic matchinglocal sparsificationonline algorithmsride-hailingfractional matchingmaximum matchingapproximation ratiotwo-stage optimization
0
0 comments X

The pith

Local sparsification guided by fractional solutions preserves the expected size of the maximum matching when spread is sufficient.

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The paper introduces a two-stage local sparsification framework for stochastic matching problems where each arriving request must first reduce its compatibility set to a fixed budget of k edges before a central coordinator solves the global matching. A selection rule is defined using a fractional solution to the expected instance, and the approximation guarantee is expressed directly in terms of the spread of that fractional solution. If spread meets a sufficient threshold, the sparsified instance is shown to retain the expected cardinality of the maximum matching in the original stochastic graph. This setup addresses practical limits on local communication bandwidth in systems such as ride-hailing, where full compatibility information cannot be transmitted centrally yet irrevocable online decisions are also undesirable.

Core claim

We prove that under sufficient spread, our sparsifier globally preserves the expected size of the maximum matching. The local selection strategy is parametrized by a fractional solution of the expected instance, and the approximation ratio is quantified as a function of the solution's spread.

What carries the argument

Local selection strategy parametrized by a fractional solution of the expected instance that prunes each realized compatibility set to k edges while preserving spread-dependent expectations.

If this is right

  • Near-optimal global matching remains achievable even when each local node is restricted to transmitting only k edges.
  • The method outperforms standard online baselines on both real New York City ride-hailing traces and adversarial synthetic instances.
  • The two-stage model supplies a tunable middle ground between fully local irrevocable decisions and unrestricted global information exchange.
  • Empirical robustness holds across varying local budgets k without requiring changes to the central optimizer.

Where Pith is reading between the lines

These are editorial extensions of the paper, not claims the author makes directly.

  • If historical data can be used to estimate a sufficiently spread fractional solution in advance, the same sparsifier could be applied to new instances whose exact distributions are unknown at run time.
  • The spread condition may connect to existing results on fractional matching polytopes and could be tested by measuring the minimum nonzero fractional value across edges in the expected instance.
  • The framework might extend to other stochastic combinatorial problems such as stochastic set cover or stochastic packing where local filtering precedes a global solver.

Load-bearing premise

The fractional solution of the expected instance must exhibit sufficient spread.

What would settle it

Compute the spread of the fractional solution on a concrete stochastic instance and check whether the sparsified graph yields an expected matching size that deviates from the bound predicted by the spread threshold.

Figures

Figures reproduced from arXiv: 2605.14195 by Edith Cohen, Mohammad Roghani, Sara Ahmadian.

Figure 1
Figure 1. Figure 1: Empirical evaluation of stochastic matching algorithms on NYC taxi data (May 14, 2025). [PITH_FULL_IMAGE:figures/full_fig_p008_1.png] view at source ↗
read the original abstract

The classic online stochastic matching problem typically requires immediate and irrevocable matching decisions. However, in many modern decentralized systems such as real-time ride-hailing and distributed cloud computing, the primary bottleneck is often local communication bandwidth rather than the timing of the match itself. We formalize this challenge by introducing a two-stage local sparsification framework. In this setting, arriving requests must prune their realized compatibility sets to a strict budget of $k$ edges before a central coordinator optimizes the global matching. This creates a "middle ground" between local information constraints and global optimization utility. We propose a local selection strategy, parametrized by a fractional solution of the expected instance. Theoretically, we quantify the approximation ratio as a function of the solution's {\em spread}. We prove that under sufficient spread, our sparsifier globally preserves the expected size of the maximum matching. Empirically, we demonstrate the robustness of our approach using the New York City ride-hailing datasets and adversarial synthetic benchmarks. Our results show that near-optimal global matching is achievable even with highly constrained local budgets, significantly outperforming standard online baselines.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit. Tearing a paper down is the easy half of reading it; the pith above is the substance, this is the friction.

Referee Report

2 major / 1 minor

Summary. The paper introduces a two-stage local sparsification framework for the online stochastic matching problem under local communication constraints. Arriving requests prune their realized compatibility sets to a strict budget of k edges using a fractional solution x of the expected instance; the authors quantify the approximation ratio as a function of the spread of x and prove that under sufficient spread the sparsifier globally preserves the expected size of the maximum matching. Empirical results on New York City ride-hailing data and synthetic benchmarks are reported to show robustness with small k.

Significance. If the preservation theorem holds, the work supplies a principled middle ground between purely local decisions and global optimization for bandwidth-limited decentralized systems such as ride-hailing and cloud computing. The explicit dependence of the guarantee on the spread parameter is a concrete, testable contribution, and the empirical outperformance of standard online baselines is a practical strength.

major comments (2)
  1. [Main theorem] Main theorem (presumably the statement in §3 or §4 that the sparsifier preserves expected matching size): the guarantee is conditioned on the fractional solution x of the expected LP exhibiting 'sufficient spread,' yet the manuscript provides neither an explicit definition or measurement procedure for spread nor any algorithm to compute or approximate such an x under the local communication budget when the arrival distribution is unknown. This renders the central claim conditional on an external oracle that the framework itself does not supply.
  2. [Approximation ratio section] Section on the approximation ratio (where the ratio is expressed as a function of spread): because the local selection rule is itself parametrized by the same x whose spread determines the ratio, the argument risks circularity; a concrete example in which spread falls below the required threshold (or a proof that typical distributions attain it) is needed to establish that the guarantee is independently predictive rather than tautological.
minor comments (1)
  1. [Abstract] Abstract: the claim of 'near-optimal global matching' is not tied to the quantitative approximation ratio derived from spread; adding a sentence that relates the empirical performance to the theoretical bound would improve clarity.

Simulated Author's Rebuttal

2 responses · 0 unresolved

We thank the referee for the constructive and detailed comments. We address each major point below and will revise the manuscript to improve clarity on the spread parameter and its role in the guarantees.

read point-by-point responses

  1. Referee: [Main theorem] Main theorem (presumably the statement in §3 or §4 that the sparsifier preserves expected matching size): the guarantee is conditioned on the fractional solution x of the expected LP exhibiting 'sufficient spread,' yet the manuscript provides neither an explicit definition or measurement procedure for spread nor any algorithm to compute or approximate such an x under the local communication budget when the arrival distribution is unknown. This renders the central claim conditional on an external oracle that the framework itself does not supply.

    Authors: We agree that an explicit definition and measurement procedure for spread are needed. In the revised manuscript we will insert a formal definition of spread (based on the minimum positive value and support size of x) together with a simple measurement procedure directly from any given fractional solution. Our model assumes the expected instance is known or estimable from historical data, which is standard for stochastic matching; we will add a short discussion on how to obtain an approximate x via offline LP solving on sampled historical arrivals, noting that this step occurs before online operation and is compatible with the local budget. revision: yes

  2. Referee: [Approximation ratio section] Section on the approximation ratio (where the ratio is expressed as a function of spread): because the local selection rule is itself parametrized by the same x whose spread determines the ratio, the argument risks circularity; a concrete example in which spread falls below the required threshold (or a proof that typical distributions attain it) is needed to establish that the guarantee is independently predictive rather than tautological.

    Authors: The dependence is not circular: for any fixed fractional solution x the local rule is defined from x and the resulting approximation ratio is a function of the spread of that same x. This makes the bound predictive once x is chosen. To remove any ambiguity we will add, in the revised version, both a concrete low-spread counter-example (showing the ratio degrades) and an analysis of the NYC ride-hailing instances demonstrating that the spread condition holds for the natural fractional solutions obtained from the expected demand graph. revision: yes

Circularity Check

0 steps flagged

No significant circularity in the derivation chain

full rationale

The central claim is a parameterized guarantee: a local sparsification rule (parametrized by any fractional solution x to the expected LP) preserves expected maximum matching size whenever x satisfies a sufficient-spread condition. Spread is an independent, measurable property of x (e.g., a lower bound on fractional values or dispersion metric) rather than a quantity defined in terms of the preservation result itself. The proof therefore establishes a non-tautological implication (spread(x) > threshold ⇒ approximation ratio close to 1) that does not reduce to self-definition, fitted-input renaming, or load-bearing self-citation. Practical questions about obtaining x for unknown distributions lie outside the derivation and do not create circularity within the stated theorems.

Axiom & Free-Parameter Ledger

2 free parameters · 1 axioms · 0 invented entities

The central claim rests on the existence of a fractional solution with measurable spread and on standard assumptions of stochastic matching (i.i.d. arrivals, known distributions). No new entities are postulated.

free parameters (2)
  • budget k
    Strict local edge budget per request; chosen by the system designer and directly affects the approximation.
  • spread threshold
    Minimum spread value required for the preservation guarantee; appears to be a parameter of the analysis rather than derived from data.
axioms (1)
  • domain assumption Arrivals are drawn i.i.d. from a known distribution
    Standard stochastic matching assumption invoked to define the expected instance and fractional solution.

pith-pipeline@v0.9.0 · 5485 in / 1268 out tokens · 43021 ms · 2026-05-15T01:33:02.709866+00:00 · methodology

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.

Reference graph

Works this paper leans on

39 extracted references · 39 canonical work pages · 1 internal anchor

  1. [1]

    Dyer, Alan M

    Jonathan Aronson, Martin E. Dyer, Alan M. Frieze, and Stephen Suen. Randomized greedy matching II.Random Struct. Algorithms, 6(1):55–74, 1995. doi: 10.1002/RSA.3240060107. URLhttps://doi.org/10.1002/rsa.3240060107

    work page doi:10.1002/rsa.3240060107 1995

  2. [2]

    Beating two-thirds for random-order streaming match- ing

    Sepehr Assadi and Soheil Behnezhad. Beating two-thirds for random-order streaming match- ing. In Nikhil Bansal, Emanuela Merelli, and James Worrell, editors,48th International Colloquium on Automata, Languages, and Programming, ICALP 2021, Glasgow, Scot- land (Virtual Conference), July 12-16, 2021, LIPIcs, pages 19:1–19:13. Schloss Dagstuhl - Leibniz-Zent...

    work page doi:10.4230/lipics.icalp.2021.19 2021

  3. [3]

    Tight pair query lower bounds for matching and earth mover’s distance

    Amir Azarmehr, Soheil Behnezhad, Mohammad Roghani, and Aviad Rubinstein. Tight pair query lower bounds for matching and earth mover’s distance. In2025 IEEE 66th Annual Symposium on Foundations of Computer Science (FOCS), pages 2666–2693, 2025. doi: 10. 1109/FOCS63196.2025.00138

    work page arXiv 2025

  4. [4]

    Improved bounds for online stochastic matching

    Bahman Bahmani and Michael Kapralov. Improved bounds for online stochastic matching. In Proceedings of the 18th Annual European Symposium on Algorithms (ESA), pages 170–181. Springer, 2010. doi: 10.1007/978-3-642-15775-2 15. URL https://theory.epfl.ch/ kapralov/papers/stochastic-final.pdf

    work page doi:10.1007/978-3-642-15775-2 2010

  5. [5]

    Approximating maximum matching requires almost quadratic time

    Soheil Behnezhad, Mohammad Roghani, and Aviad Rubinstein. Approximating maximum matching requires almost quadratic time. InProceedings of the 56th Annual ACM Symposium on Theory of Computing, pages 444–454, 2024

    work page 2024

  6. [6]

    Improved bounds for matching in random-order streams.Theory of Computing Systems, 68(4):758–772, 2024

    Aaron Bernstein. Improved bounds for matching in random-order streams.Theory of Computing Systems, 68(4):758–772, 2024

    work page 2024

  7. [7]

    Hubert Chan, Fei Chen, Xiaowei Wu, and Zhichao Zhao

    T.-H. Hubert Chan, Fei Chen, Xiaowei Wu, and Zhichao Zhao. Ranking on arbitrary graphs: Rematch via continuous LP with monotone and boundary condition constraints. InProceedings of the Twenty-Fifth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2014, pages 1112–1122. SIAM, 2014. doi: 10.1137/1.9781611973402.82. URL https://doi.org/10. 1137/1.97816...

    work page doi:10.1137/1.9781611973402.82 2014

  8. [8]

    Analyzing node-weighted oblivious matching problem via continuous lp with jump discontinuity.ACM Transactions on Algorithms (TALG), 14(2):1–25, 2018

    T-H Hubert Chan, Fei Chen, and Xiaowei Wu. Analyzing node-weighted oblivious matching problem via continuous lp with jump discontinuity.ACM Transactions on Algorithms (TALG), 14(2):1–25, 2018

    work page 2018

  9. [9]

    A general purpose unequal probability sampling plan.Biometrika, 69(3): 653–656, 1982

    Ming-Yi Chao. A general purpose unequal probability sampling plan.Biometrika, 69(3): 653–656, 1982. doi: 10.1093/biomet/69.3.653

    work page doi:10.1093/biomet/69.3.653 1982

  10. [10]

    Efficient stream sampling for variance-optimal estimation of subset sums.SIAM Journal on Computing, 40(5): 1402–1431, 2011

    Edith Cohen, Nick Duffield, Haim Kaplan, Carsten Lund, and Mikkel Thorup. Efficient stream sampling for variance-optimal estimation of subset sums.SIAM Journal on Computing, 40(5): 1402–1431, 2011. doi: 10.1137/10079817X. URL https://doi.org/10.1137/10079817X

    work page doi:10.1137/10079817x 2011

  11. [11]

    A sublinear-time algorithm for nearly-perfect matchings in regular non-bipartite graphs

    Varsha Dani and Thomas P Hayes. A sublinear-time algorithm for nearly-perfect matchings in regular non-bipartite graphs. InProceedings of the 2025 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 4899–4913. SIAM, 2025

    work page 2025

  12. [12]

    A unified framework for analysis of randomized greedy matching algorithms

    Mahsa Derakhshan and Tao Yu. A unified framework for analysis of randomized greedy matching algorithms. InProceedings of the 58th Annual ACM Symposium on Theory of Computing (STOC). ACM, 2026

    work page 2026

  13. [13]

    A simple analysis of ranking in general graphs

    Mahsa Derakhshan, Mohammad Roghani, Mohammad Saneian, and Tao Yu. A simple analysis of ranking in general graphs. In2026 Symposium on Simplicity in Algorithms (SOSA). SIAM, 2026

    work page 2026

  14. [14]

    Improved approxi- mation for ranking on general graphs

    Mahsa Derakhshan, Mohammad Roghani, Mohammad Saneian, and Tao Yu. Improved approxi- mation for ranking on general graphs. InProceedings of the 2026 ACM-SIAM Symposium on Discrete Algorithms, SODA 2026. SIAM, 2026. to appear. 11

    work page 2026

  15. [15]

    Muthukrishnan

    Jon Feldman, Aranyak Mehta, Vahab Mirrokni, and S. Muthukrishnan. Online stochastic matching: Beating 1−1/e . InProceedings of the 50th Annual IEEE Symposium on Foundations of Computer Science (FOCS), pages 117–126. IEEE, 2009. doi: 10.1109/FOCS.2009.30. URL https://doi.org/10.1109/FOCS.2009.30

    work page doi:10.1109/focs.2009.30 2009

  16. [16]

    Online Matching with General Arrivals

    Buddhima Gamlath, Michael Kapralov, Andreas Maggiori, Ola Svensson, and David Wajc. Online matching with general arrivals. InProceedings of the 60th Annual IEEE Symposium on Foundations of Computer Science (FOCS), pages 70–87. IEEE, 2019. doi: 10.1109/FOCS.2019. 00014. URLhttps://arxiv.org/abs/1904.08255

    work page internal anchor Pith review Pith/arXiv arXiv doi:10.1109/focs.2019 2019

  17. [17]

    Perfect matchings in O(n log n) time in regular bipartite graphs

    Ashish Goel, Michael Kapralov, and Sanjeev Khanna. Perfect matchings in O(n log n) time in regular bipartite graphs. InProceedings of the Forty-second ACM Symposium on Theory of Computing, pages 39–46, 2010

    work page 2010

  18. [18]

    On the communication and streaming complexity of maximum bipartite matching

    Ashish Goel, Michael Kapralov, and Sanjeev Khanna. On the communication and streaming complexity of maximum bipartite matching. InProceedings of the twenty-third annual ACM- SIAM symposium on Discrete Algorithms, pages 468–485. SIAM, 2012

    work page 2012

  19. [19]

    Online vertex-weighted bipartite matching: Beating 1-1/e with random arrivals.ACM Transactions on Algorithms (TALG), 15(3):1–15, 2019

    Zhiyi Huang, Zhihao Gavin Tang, Xiaowei Wu, and Yuhao Zhang. Online vertex-weighted bipartite matching: Beating 1-1/e with random arrivals.ACM Transactions on Algorithms (TALG), 15(3):1–15, 2019

    work page 2019

  20. [20]

    Tight pair query lower bounds for matching and earth mover’s distance

    Zhiyi Huang, Enze Sun, Xiaowei Wu, and Jiahao Zhao. Edge-weighted matching in the dark. In66th IEEE Annual Symposium on Foundations of Computer Science, FOCS 2025, Sydney, Australia, December 14-17, 2025, pages 797–817. IEEE, 2025. doi: 10.1109/FOCS63196.2025. 00043. URLhttps://doi.org/10.1109/FOCS63196.2025.00043

    work page doi:10.1109/focs63196.2025 2025

  21. [21]

    Online stochastic matching: New algorithms with better bounds

    Patrick Jaillet and Xin Lu. Online stochastic matching: New algorithms with better bounds. Mathematics of Operations Research, 39(3):624–646, 2014

    work page 2014

  22. [22]

    Improved analysis of ranking for online vertex-weighted bipartite matching in the random order model

    Billy Jin and David P Williamson. Improved analysis of ranking for online vertex-weighted bipartite matching in the random order model. InInternational Conference on Web and Internet Economics, pages 207–225. Springer, 2021

    work page 2021

  23. [23]

    Better bounds for matchings in the streaming model

    Michael Kapralov. Better bounds for matchings in the streaming model. InProceedings of the twenty-fourth annual ACM-SIAM symposium on Discrete algorithms, pages 1679–1697. SIAM, 2013

    work page 2013

  24. [24]

    Space lower bounds for approximating maximum matching in the edge arrival model

    Michael Kapralov. Space lower bounds for approximating maximum matching in the edge arrival model. InProceedings of the 2021 ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 1874–1893. SIAM, 2021

    work page 2021

  25. [25]

    Approximating matching size from random streams

    Michael Kapralov, Sanjeev Khanna, and Madhu Sudan. Approximating matching size from random streams. InProceedings of the 25th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 734–751. SIAM, 2014. doi: 10.1137/1.9781611973402.55. URL https://doi.org/10.1137/1.9781611973402.55

    work page doi:10.1137/1.9781611973402.55 2014

  26. [26]

    Online bipartite matching with unknown distributions

    Chinmay Karande, Aranyak Mehta, and Pushkar Tripathi. Online bipartite matching with unknown distributions. In Lance Fortnow and Salil P. Vadhan, editors,Proceedings of the 43rd ACM Symposium on Theory of Computing, STOC 2011, San Jose, CA, USA, 6-8 June 2011, pages 587–596. ACM, 2011. doi: 10.1145/1993636.1993715. URL https://doi.org/10. 1145/1993636.1993715

    work page doi:10.1145/1993636.1993715 2011

  27. [27]

    Karp, Umesh V

    Richard M. Karp, Umesh V . Vazirani, and Vijay V . Vazirani. An optimal algorithm for online bipartite matching. InProceedings of the 22nd Annual ACM Symposium on Theory of Computing (STOC), pages 352–358. ACM, 1990. doi: 10.1145/100216.100262. URL https://doi.org/ 10.1145/100216.100262

    work page doi:10.1145/100216.100262 1990

  28. [28]

    Manshadi, Shayan Oveis Gharan, and Amin Saberi

    Vahideh H. Manshadi, Shayan Oveis Gharan, and Amin Saberi. Online stochastic matching: Online actions based on offline statistics. InProceedings of the 22nd Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 1265–1277. SIAM, 2011. doi: 10.1137/ 1.9781611973082.98. URL https://epubs.siam.org/doi/10.1137/1.9781611973082. 98. 12

    work page doi:10.1137/1.9781611973082 2011

  29. [29]

    Randomized distributed edge coloring via an extension of the Chernoff–Hoeffding bounds.SIAM Journal on Computing, 26(2): 350–368, 1997

    Alessandro Panconesi and Aravind Srinivasan. Randomized distributed edge coloring via an extension of the Chernoff–Hoeffding bounds.SIAM Journal on Computing, 26(2): 350–368, 1997. doi: 10.1137/S0097539793250767. URL https://doi.org/10.1137/ S0097539793250767

    work page doi:10.1137/s0097539793250767 1997

  30. [30]

    Revisiting ranking for online bipartite matching with random arrivals: the primal-dual analysis

    Bo Peng and Zhihao Gavin Tang. Revisiting ranking for online bipartite matching with random arrivals: the primal-dual analysis. InProceedings of the 26th ACM Conference on Economics and Computation, pages 820–835, 2025

    work page 2025

  31. [31]

    Randomized greedy algorithms for the maximum matching problem with new analysis

    Matthias Poloczek and Mario Szegedy. Randomized greedy algorithms for the maximum matching problem with new analysis. In53rd Annual IEEE Symposium on Foundations of Computer Science, FOCS 2012, pages 708–717. IEEE Computer Society, 2012. doi: 10.1109/ FOCS.2012.20. URLhttps://doi.org/10.1109/FOCS.2012.20

    work page doi:10.1109/focs.2012.20 2012

  32. [32]

    A comparison theorem on moment inequalities between negatively associated and independent random variables.Journal of Theoretical Probability, 13(2):343–356, April

    Qi-Man Shao. A comparison theorem on moment inequalities between negatively associated and independent random variables.Journal of Theoretical Probability, 13(2):343–356, April

    work page

  33. [33]

    URL https://ideas.repec.org/a/spr/jotpro/ v13y2000i2d10.1023_a1007849609234.html

    doi: 10.1023/A:1007849609234. URL https://ideas.repec.org/a/spr/jotpro/ v13y2000i2d10.1023_a1007849609234.html

    work page doi:10.1023/a:1007849609234

  34. [34]

    Distributions on level-sets with applications to approximation algorithms

    Aravind Srinivasan. Distributions on level-sets with applications to approximation algorithms. InProceedings of the 41st Annual Symposium on Foundations of Computer Science (FOCS), pages 588–597. IEEE, 2001. doi: 10.1109/SFCS.2001.959937. URL https://doi.org/10. 1109/SFCS.2001.959937

    work page doi:10.1109/sfcs.2001.959937 2001

  35. [35]

    micro-types

    Zhihao Gavin Tang, Xiaowei Wu, and Yuhao Zhang. Towards a better understanding of randomized greedy matching. InProceedings of the 52nd Annual ACM SIGACT Symposium on Theory of Computing, STOC 2020, pages 1097–1110. ACM, 2020. doi: 10.1145/3357713. 3384265. URLhttps://doi.org/10.1145/3357713.3384265. A Proof of Proposition 2.3 The proof is divided into tw...

    work page doi:10.1145/3357713 2020

  36. [36]

    Let R:=ρ i(w) +ρ j(w) denote the total size-wrate assigned to this pair

    Choose two residual binsi, jand a sizew∈ Wsuch that ρi(w)>0andρ j(w)>0. Let R:=ρ i(w) +ρ j(w) denote the total size-wrate assigned to this pair

    work page

  37. [37]

    Freeze all rates in bins i, j at sizes w′ ̸=w , and redistribute only the size-w rate R: assign rateato biniand rateR−ato binj

    work page

  38. [38]

    Among maximizers, choose an endpoint maximizer; by the endpoint property, such a maximizer exists

    Chooseafrom the feasible interval so as to maximize the two-bin contribution E (Y \w i +wN a −1) + +E (Y \w j +wN R−a −1) + , where Y \w i and Y \w j are the background loads generated by all sizes other than w. Among maximizers, choose an endpoint maximizer; by the endpoint property, such a maximizer exists. Thus the update can be chosen so that either o...

    work page

  39. [39]

    The process terminates when no two residual bins carry positive rate at a common sizew∈ W

    If a bin becomes full, remove it from subsequent operations. The process terminates when no two residual bins carry positive rate at a common sizew∈ W. 17 Corollary B.4(Endpoint form of a pairwise update).Consider a pairwise update on residual bins i, jand sizew, and let R:=ρ i(w) +ρ j(w). Let Λ\w i := Λi −wρ i(w),Λ \w j := Λj −wρ j(w). The feasible inter...

    work page