A primal-dual online deterministic algorithm for matching with delays

DOI10.1007/978-3-030-04693-4_4MaRDI QIDQ1757757zbMATH OpenOpenAlexFDO

Authors Marcin Bienkowski, Artur Kraska, Hsiang-Hsuan Liu, Paweł Schmidt

Publication date 15 January 2019

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

zbMATH Keywords

competitive analysisdelayed servicemetric matchingonline algorithmsprimal-dual algorithms

Mathematics Subject Classification ID

Approximation algorithms (68W25) Online algorithms; streaming algorithms (68W27)

Recommendations

• A match in time saves nine: deterministic online matching with delays
• Online matching: haste makes waste!
• Polylogarithmic Bounds on the Competitiveness of Min-cost Perfect Matching with Delays

Cited in

(18)

• A match in time saves nine: deterministic online matching with delays
• Polylogarithmic Bounds on the Competitiveness of Min-cost Perfect Matching with Delays
• Competitive analysis for two variants of online metric matching problem
• Impatient Online Matching
• Online matching: haste makes waste!
• scientific article; zbMATH DE number 7651147 (Why is no real title available?)
• The power of amortized recourse for online graph problems
• Deterministic primal-dual algorithms for online k-way matching with delays
• Capacity-insensitive algorithms for online facility assignment problems on a line
• Deterministic primal-dual algorithms for online \(k\)-way matching with delays
• Universal optimization for non-clairvoyant subadditive joint replenishment
• Online deterministic minimum cost bipartite matching with delays on a line
• Online deterministic minimum cost bipartite matching with delays on a line
• Online matching with delays and stochastic arrival times
• Universal optimization for non-clairvoyant subadditive joint replenishment
• Online multi-level aggregation with delays and stochastic arrivals
• Online matching with delays and size-based costs
• Nearly-optimal algorithm for non-clairvoyant service with delay

This page was built for publication: A primal-dual online deterministic algorithm for matching with delays

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