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

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

Max Bender, Jacob Gilbert, Kirk R. 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)

Related Items (1)

Online Metric Algorithms with Untrusted Predictions

Cites Work

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

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