A poly-log competitive posted-price algorithm for online metrical matching on a spider

DOI10.1007/978-3-030-86593-1_5OpenAlexW3201041086MaRDI QIDQ2140487FDOQ2140487

Max Bender, Jacob Gilbert, Kirk Pruhs

Publication date: 20 May 2022

Full work available at URL: https://doi.org/10.1007/978-3-030-86593-1_5

Mathematics Subject Classification ID

Theory of computing (68Qxx)

Cites Work

• On-line algorithms for weighted bipartite matching and stable marriages
• On-line routing of virtual circuits with applications to load balancing and machine scheduling
• Title not available (Why is that?)
• A tight bound on approximating arbitrary metrics by tree metrics
• The multiplicative weights update method: a meta-algorithm and applications
• Online matching on a line
• Online Weighted Matching
• Randomized online algorithms for minimum metric bipartite matching
• A randomized \(O(\log^2k)\)-competitive algorithm for metric bipartite matching
• Approximation and Online Algorithms
• On-Line Load Balancing of Temporary Tasks
• Dynamic pricing of servers on trees
• Pricing Online Decisions: Beyond Auctions
• The Online Metric Matching Problem for Doubling Metrics
• A collection of lower bounds for online matching on the line
• Competitively pricing parking in a tree
• A $$o(n)$$-Competitive Deterministic Algorithm for Online Matching on a Line
• Minimizing Maximum Flow Time on Related Machines via Dynamic Posted Pricing
• Title not available (Why is that?)

Cited In (2)

• Online Metric Algorithms with Untrusted Predictions
• An \(O(\log n)\)-competitive posted-price algorithm for online matching on the line

This page was built for publication: A poly-log competitive posted-price algorithm for online metrical matching on a spider

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2140487)