An optimal deterministic algorithm for online b-matching
From MaRDI portal
Publication:1575950
DOI10.1016/S0304-3975(99)00140-1zbMATH Open0951.68116OpenAlexW2085938855WikidataQ127580350 ScholiaQ127580350MaRDI QIDQ1575950FDOQ1575950
Authors: Bala Kalyanasundaram, Kirk Pruhs 
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
Recommendations
- Near optimal algorithms for online maximum weighted \(b\)-matching
- Near optimal algorithms for online maximum edge-weighted \(b\)-matching and two-sided vertex-weighted \(b\)-matching
- A \(o(n)\)-competitive deterministic algorithm for online matching on a line
- Online Weighted Matching
- Deferred on-line bipartite matching
Cites Work
Cited In (40)
- Title not available (Why is that?)
- On the lower bound of the competitive ratio for the weighted online roommates problem
- An Optimal Algorithm for Online Freeze-tag
- An optimal deterministic algorithm for online b-matching
- Pricing and allocation algorithm designs in dynamic ridesharing system
- Online primal dual meets online matching with stochastic rewards: configuration LP to the rescue
- Online crowdsourced truck delivery using historical information
- Online algorithms for maximum cardinality matching with edge arrivals
- Online algorithms for maximum cardinality matching with edge arrivals
- Attenuate locally, win globally: attenuation-based frameworks for online stochastic matching with timeouts
- Online allocation and display ads optimization with surplus supply
- Online submodular welfare maximization: greedy beats 1/2 in random order
- Online matching with stochastic rewards: advanced analyses using configuration linear programs
- A \(o(n)\)-competitive deterministic algorithm for online matching on a line
- Near optimal algorithms for online maximum weighted \(b\)-matching
- Two-sided online bipartite matching and vertex cover: beating the greedy algorithm
- Tighter bounds for online bipartite matching
- Maximizing throughput in multi-queue switches
- Optimal Algorithms for Online b-Matching with Variable Vertex Capacities
- A \(o(n)\)-competitive deterministic algorithm for online matching on a line
- Near optimal algorithms for online maximum edge-weighted \(b\)-matching and two-sided vertex-weighted \(b\)-matching
- Online stochastic weighted matching algorithm for real‐time shared parking
- Online bottleneck matching on a line
- A randomized \(O(\log^2k)\)-competitive algorithm for metric bipartite matching
- Online stochastic matching: new algorithms with better bounds
- A stochastic algorithm for online bipartite resource allocation problems
- Collecting weighted items from a dynamic queue
- Serve or skip: the power of rejection in online bottleneck matching
- Near optimal algorithms for online weighted bipartite matching in adversary model
- Frequency capping in online advertising
- A stronger impossibility for fully online matching
- Online perfect matching and mobile computing
- Size versus fairness in the assignment problem
- Improved online algorithms for jumbled matching
- On policies for single-leg revenue management with limited demand information
- Station assignment with reallocation
- Edge-weighted online bipartite matching
- Title not available (Why is that?)
- Learn from history for online bipartite matching
- Deterministic dynamic matching in \(O(1)\) update time
This page was built for publication: An optimal deterministic algorithm for online \(b\)-matching
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1575950)
