Online maximum matching with recourse

DOI10.1007/S10878-020-00641-WMaRDI QIDQ830934zbMATH OpenOpenAlexFDO

Authors Spyros Angelopoulos, Christoph Dürr, Shendan Jin

Publication date 10 May 2021

Published in Journal of Combinatorial Optimization (Search for Journal in Brave)

Full work available at URL https://drops.dagstuhl.de/opus/volltexte/2018/9590/

zbMATH Keywords

competitive analysismatchingonline algorithmsrecourse

Mathematics Subject Classification ID

Combinatorial optimization (90C27)

Recommendations

• Online maximum matching with recourse
• Maximum matching in the online batch-arrival model
• Online algorithms for maximum cardinality matching with edge arrivals
• Online algorithms for maximum cardinality matching with edge arrivals
• Permutation Strikes Back: The Power of Recourse in Online Metric Matching

Cites work

• 64.4 Some logarithm inequalities
• Approximation, Randomization and Combinatorial Optimization. Algorithms and Techniques
• Buyback problem -- approximate matroid intersection with cancellation costs
• scientific article; zbMATH DE number 193018 (Why is no real title available?)
• scientific article; zbMATH DE number 1232130 (Why is no real title available?)
• scientific article; zbMATH DE number 2086630 (Why is no real title available?)
• Improved bounds for online preemptive matching
• Maintaining assignments online: matching, scheduling, and flows
• On randomized algorithms for matching in the online preemptive model
• Online algorithms for maximum cardinality matching with edge arrivals
• Online bipartite matching with amortized O(^2 n) replacements
• Online constrained optimization with recourse
• Online matching and ad allocation
• Online minimization knapsack problem
• Online Steiner tree with deletions
• The power of deferral: maintaining a constant-competitive Steiner tree online
• The power of recourse for online MST and TSP

Cited in

(16)

• Online algorithms for maximum cardinality matching with edge arrivals
• Online load balancing with general reassignment cost
• Online maximum matching with recourse
• Online algorithms for maximum cardinality matching with edge arrivals
• Online matching with concave returns
• Approximation and Online Algorithms
• Online 2-stage stable matching
• Permutation Strikes Back: The Power of Recourse in Online Metric Matching
• The power of amortized recourse for online graph problems
• Online knapsack with removal and recourse
• Low recourse arborescence forests under uniformly random arcs
• The online piercing set problem with recourse
• Interval-constrained bipartite matching over time
• Online knapsack with removal and recourse
• Online deterministic minimum cost bipartite matching with delays on a line
• Online deterministic minimum cost bipartite matching with delays on a line

This page was built for publication: Online maximum matching with recourse

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