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

DOI10.1007/978-3-030-86593-1_5MaRDI QIDQ2140487zbMATH OpenOpenAlexFDO

Authors 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

• scientific article; zbMATH DE number 1775400 (Why is no real title available?)
• scientific article; zbMATH DE number 7236471 (Why is no real title available?)
• A \(o(n)\)-competitive deterministic algorithm for online matching on a line
• A collection of lower bounds for online matching on the line
• A randomized \(O(\log^2k)\)-competitive algorithm for metric bipartite matching
• A tight bound on approximating arbitrary metrics by tree metrics
• Approximation and Online Algorithms
• Competitively pricing parking in a tree
• Dynamic pricing of servers on trees
• Minimizing maximum flow time on related machines via dynamic posted pricing
• On-Line Load Balancing of Temporary Tasks
• On-line algorithms for weighted bipartite matching and stable marriages
• On-line routing of virtual circuits with applications to load balancing and machine scheduling
• Online Weighted Matching
• Online matching on a line
• Pricing online decisions: beyond auctions
• Randomized online algorithms for minimum metric bipartite matching
• The Online Metric Matching Problem for Doubling Metrics
• The multiplicative weights update method: a meta-algorithm and applications

Cited in

(2)

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

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)