Pith. sign in

REVIEW 2 cited by

Maximum Weight Online Matching with Deadlines

Not yet reviewed by Pith; the record is open.

Re-run · record.json Download PDF Read on arXiv ↗

This paper has not been read by Pith yet. Machine review is queued; the pith claim, tier, and objections will appear here once it completes.

SPECIMEN: schema-true, not a live event

T0 review · schema-true

One-sentence machine reading of the paper's core claim.

pith:XXXXXXXX · record.json · timestamp

arxiv 1808.03526 v1 pith:HMOUZM5F submitted 2018-08-09 cs.DS

Itai Ashlagi , Maximilien Burq , Chinmoy Dutta , Patrick Jaillet , Amin Saberi , Chris Sholley This is my paper · ORCID
classification cs.DS
keywords agentsalgorithmcompetitivematchingtimearrivecasemarketplace
verification ladder T0 review T1 audit T2 compute T3 formal
0 comments
read the original abstract

We study the problem of matching agents who arrive at a marketplace over time and leave after d time periods. Agents can only be matched while they are present in the marketplace. Each pair of agents can yield a different match value, and the planner's goal is to maximize the total value over a finite time horizon. First we study the case in which vertices arrive in an adversarial order. We provide a randomized 0.25-competitive algorithm building on a result by Feldman et al. (2009) and Lehman et al. (2006). We extend the model to the case in which departure times are drawn independently from a distribution with non-decreasing hazard rate, for which we establish a 1/8-competitive algorithm. When the arrival order is chosen uniformly at random, we show that a batching algorithm, which computes a maximum-weighted matching every (d+1) periods, is 0.279-competitive.

Discussion (0). Continue with ORCID to comment.

Forward citations

Cited by 2 Pith papers

Reviewed papers in the Pith corpus that reference this work. Sorted by Pith novelty score. Full citation record

  1. Maturing Markov Decision Processes: Decision Making under Increasing Information and Shrinking Action Sets

    cs.LG 2026-06 unverdicted novelty 6.0 of 10

    The paper proposes Maturing Markov Decision Processes (MMDPs) built on information-action asymmetry, an expiring-action priority principle, and a structure-aware RL framework, with experiments showing efficiency gains...

  2. Online Fair Allocations with Binary Valuations and Beyond

    cs.GT 2025-05 reject novelty 6.0 of 10

    The paper claims optimal online EF1/MMS approximation ratios for submodular binary goods and personalized bi-valued goods/chores, with matching impossibility results, though proof gaps remain.

Pith tools