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

DOI10.1142/s179383092350057xMaRDI QIDQ6637060

Toshiya Itoh, Shuichi Miyazaki, Tsubasa Harada

Publication date: 13 November 2024

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

zbMATH Keywords

greedy algorithmcompetitive analysisonline algorithmonline facility assignment problemonline metric matching problem

Mathematics Subject Classification ID

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

Cites Work

• Unnamed Item
• Unnamed Item
• On-line algorithms for weighted bipartite matching and stable marriages
• A match in time saves nine: deterministic online matching with delays
• A primal-dual online deterministic algorithm for matching with delays
• Online matching on a line
• A collection of lower bounds for online matching on the line
• The Online Metric Matching Problem for Doubling Metrics
• Bayesian Mechanism Design
• A $$o(n)$$-Competitive Deterministic Algorithm for Online Matching on a Line
• An O(log2 k)-Competitive Algorithm for Metric Bipartite Matching
• Randomized online algorithms for minimum metric bipartite matching
• On the k -server conjecture
• The Online Transportation Problem
• Polylogarithmic Bounds on the Competitiveness of Min-cost Perfect Matching with Delays
• A Robust and Optimal Online Algorithm for Minimum Metric Bipartite Matching
• Online Weighted Matching
• Min-Cost Bipartite Perfect Matching with Delays
• Competitive analysis for two variants of online metric matching problem
• Impatient Online Matching
• Minimum Cost Perfect Matching with Delays for Two Sources
• Approximation and Online Algorithms
• Deterministic min-cost matching with delays
• Online facility assignment

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