An optimal deterministic algorithm for online \(b\)-matching

DOI10.1016/S0304-3975(99)00140-1zbMath0951.68116OpenAlexW2085938855WikidataQ127580350 ScholiaQ127580350MaRDI QIDQ1575950

Kirk R. Pruhs, Bala Kalyanasundaram

Publication date: 23 August 2000

Published in: Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/s0304-3975(99)00140-1

zbMATH Keywords

BALANCE

Mathematics Subject Classification ID

Nonnumerical algorithms (68W05) Graph theory (including graph drawing) in computer science (68R10)

Related Items (27)

Maximizing throughput in multi-queue switches ⋮ Two-sided Online Bipartite Matching and Vertex Cover: Beating the Greedy Algorithm ⋮ Online crowdsourced truck delivery using historical information ⋮ A stochastic algorithm for online bipartite resource allocation problems ⋮ Serve or skip: the power of rejection in online bottleneck matching ⋮ Online Submodular Welfare Maximization: Greedy Beats 1/2 in Random Order ⋮ Near optimal algorithms for online weighted bipartite matching in adversary model ⋮ Online stochastic weighted matching algorithm for real‐time shared parking ⋮ Online bottleneck matching on a line ⋮ Online allocation and display ads optimization with surplus supply ⋮ Collecting weighted items from a dynamic queue ⋮ Near optimal algorithms for online maximum edge-weighted \(b\)-matching and two-sided vertex-weighted \(b\)-matching ⋮ A randomized \(O(\log^2k)\)-competitive algorithm for metric bipartite matching ⋮ Tighter Bounds for Online Bipartite Matching ⋮ Station assignment with reallocation ⋮ Frequency capping in online advertising ⋮ Online algorithms for maximum cardinality matching with edge arrivals ⋮ Unnamed Item ⋮ Pricing and allocation algorithm designs in dynamic ridesharing system ⋮ Attenuate locally, win globally: attenuation-based frameworks for online stochastic matching with timeouts ⋮ Online submodular maximization: beating 1/2 made simple ⋮ A stronger impossibility for fully online matching ⋮ On Policies for Single-Leg Revenue Management with Limited Demand Information ⋮ Online Algorithms for Maximum Cardinality Matching with Edge Arrivals ⋮ Online Stochastic Matching: New Algorithms with Better Bounds ⋮ Learn from history for online bipartite matching ⋮ Size versus fairness in the assignment problem

Cites Work

• Online matching with blocked input
• On-line algorithms for weighted bipartite matching and stable marriages
• The Online Transportation Problem
• Online Weighted Matching

This page was built for publication: An optimal deterministic algorithm for online \(b\)-matching