Pith Number

pith:4FQPCRO7

pith:2026:4FQPCRO77KG467E3LQ2DYIC442

not attested not anchored not stored refs resolved

Stochastic Matching via Local Sparsification

Edith Cohen, Mohammad Roghani, Sara Ahmadian

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

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

Open paper page JSON Open Graph Bundle Merged state Verified badge What is a Pith Number?

Add to your LaTeX paper

\usepackage{pith}
\pithnumber{4FQPCRO77KG467E3LQ2DYIC442}

Prints a linked badge after your title and injects PDF metadata. Compiles on arXiv. Learn more · Embed verified badge

Record completeness

1 Bitcoin timestamp

2 Internet Archive

3 Author claim open · sign in to claim

4 Citations open

5 Replications open

✓ Portable graph bundle live · download bundle · merged state

The bundle contains the canonical record plus signed events. A mirror can host it anywhere and recompute the same current state with the deterministic merge algorithm.

Claims

C1strongest claim

We prove that under sufficient spread, our sparsifier globally preserves the expected size of the maximum matching.

C2weakest assumption

The fractional solution of the expected instance must exhibit sufficient spread; the paper does not specify how this spread is guaranteed or measured in practice when the instance is unknown in advance.

C3one line summary

A local selection rule based on a fractional solution of the expected instance preserves the expected maximum matching size under sufficient spread and yields near-optimal global matchings with small local budgets on ride-hailing data.

References

39 extracted · 39 resolved · 1 Pith anchors

[1] 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/r 1995 · doi:10.1002/rsa.3240060107

[2] Beating two-thirds for random-order streaming match- ing 2021 · doi:10.4230/lipics.icalp.2021.19

[3] Sign-rank of k - H amming distance is constant 2025

[4] Improved bounds for online stochastic matching 2010 · doi:10.1007/978-3-642-15775-2

[5] Approximating maximum matching requires almost quadratic time 2024

Receipt and verification

First computed	2026-05-17T23:39:11.098921Z
Builder	pith-number-builder-2026-05-17-v1
Signature	Pith Ed25519 (`pith-v1-2026-05`) · public key
Schema	pith-number/v1.0

Canonical hash

e160f145dffa8dcf7c9b5c343c205ce693294bb78c9c4d3beb15278c81f1d69d

Aliases

arxiv: 2605.14195 · arxiv_version: 2605.14195v1 · doi: 10.48550/arxiv.2605.14195 · pith_short_12: 4FQPCRO77KG4 · pith_short_16: 4FQPCRO77KG467E3 · pith_short_8: 4FQPCRO7

Agent API

Resolver JSON Graph JSON Events JSON Schema Signing key

Verify this Pith Number yourself

curl -sH 'Accept: application/ld+json' https://pith.science/pith/4FQPCRO77KG467E3LQ2DYIC442 \
  | jq -c '.canonical_record' \
  | python3 -c "import sys,json,hashlib; b=json.dumps(json.loads(sys.stdin.read()), sort_keys=True, separators=(',',':'), ensure_ascii=False).encode(); print(hashlib.sha256(b).hexdigest())"
# expect: e160f145dffa8dcf7c9b5c343c205ce693294bb78c9c4d3beb15278c81f1d69d

Canonical record JSON

{
  "metadata": {
    "abstract_canon_sha256": "890832021df4cc06d752b08b24385733d7ca790b77e4f62d8f6bb31dd16ef460",
    "cross_cats_sorted": [
      "cs.LG"
    ],
    "license": "http://creativecommons.org/licenses/by/4.0/",
    "primary_cat": "cs.DS",
    "submitted_at": "2026-05-13T23:25:15Z",
    "title_canon_sha256": "ef60f686e5c3ab4092b1d49977ceb327704e2e558499df643d2c560d79490cd7"
  },
  "schema_version": "1.0",
  "source": {
    "id": "2605.14195",
    "kind": "arxiv",
    "version": 1
  }
}