scientific article; zbMATH DE number 7758339

DOI10.4230/lipics.approx/random.2020.37arXiv2001.03107MaRDI QIDQ6062163

Nicole Megow, Lukas Nölke

Publication date: 31 October 2023

Full work available at URL: https://arxiv.org/abs/2001.03107

Title: zbMATH Open Web Interface contents unavailable due to conflicting licenses.

zbMATH Keywords

competitive analysisonlinerecoursemin-cost matching in bipartite graphs

Mathematics Subject Classification ID

Combinatorial optimization (90C27) Approximation algorithms (68W25) Randomized algorithms (68W20)

Related Items (3)

Online load balancing with general reassignment cost ⋮ The power of amortized recourse for online graph problems ⋮ Online knapsack with removal and recourse

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
• Online constrained optimization with recourse
• Greedy metric minimum online matchings with random arrivals
• A collection of lower bounds for online matching on the line
• A \(o(n)\)-competitive deterministic algorithm for online matching on a line
• The Online Metric Matching Problem for Doubling Metrics
• Bayesian Mechanism Design
• The Power of Dynamic Distance Oracles
• Linear-Time Approximation for Maximum Weight Matching
• The Power of Deferral: Maintaining a Constant-Competitive Steiner Tree Online
• Dynamic Steiner Tree Problem
• A Robust and Optimal Online Algorithm for Minimum Metric Bipartite Matching
• Online Weighted Matching
• Online perfect matching and mobile computing
• Stochastic Online Metric Matching
• Online Bipartite Matching with Amortized O (log ² n ) Replacements
• Maintaining Assignments Online: Matching, Scheduling, and Flows
• The Power of Recourse for Online MST and TSP

This page was built for publication: