Capacity-insensitive algorithms for online facility assignment problems on a line

DOI10.1142/S179383092350057XMaRDI QIDQ6637060zbMATH OpenFDO

Authors Tsubasa Harada, Toshiya Itoh, Shuichi Miyazaki

Publication date 13 November 2024

Published in Discrete Mathematics, Algorithms and Applications (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1142/S179383092350057X

zbMATH Keywords

competitive analysisgreedy algorithmonline algorithmonline facility assignment problemonline metric matching problem

Mathematics Subject Classification ID

Online algorithms; streaming algorithms (68W27) Analysis of algorithms (68W40) Communication networks in operations research (90B18) Programming involving graphs or networks (90C35)

Recommendations

• Online facility assignment
• Online facility assignment
• Competitive analysis for two variants of online metric matching problem
• Competitive analysis for two variants of online metric matching problem
• Online facility location with facility movements

Cites work

• A \(o(n)\)-competitive deterministic algorithm for online matching on a line
• A collection of lower bounds for online matching on the line
• A match in time saves nine: deterministic online matching with delays
• A primal-dual online deterministic algorithm for matching with delays
• A robust and optimal online algorithm for minimum metric bipartite matching
• An O(log2 k)-Competitive Algorithm for Metric Bipartite Matching
• Approximation and Online Algorithms
• Competitive analysis for two variants of online metric matching problem
• scientific article; zbMATH DE number 5294801 (Why is no real title available?)
• scientific article; zbMATH DE number 7236471 (Why is no real title available?)
• Impatient Online Matching
• Min-cost bipartite perfect matching with delays
• Minimum cost perfect matching with delays for two sources
• On the k -server conjecture
• On-line algorithms for weighted bipartite matching and stable marriages
• Online facility assignment
• Online matching and ad allocation
• Online matching on a line
• Online Weighted Matching
• Polylogarithmic Bounds on the Competitiveness of Min-cost Perfect Matching with Delays
• Randomized online algorithms for minimum metric bipartite matching
• The Online Metric Matching Problem for Doubling Metrics
• The Online Transportation Problem

Cited in

(1)

• \textsc{Permutation} for online metric matching with \(m\) distinct servers

This page was built for publication: Capacity-insensitive algorithms for online facility assignment problems on a line

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