The Online Median Problem

DOI10.1137/S0097539701383443zbMath1128.90550MaRDI QIDQ4706233

Ramgopal R. Mettu, C. Greg Plaxton

Publication date: 19 June 2003

Published in: SIAM Journal on Computing (Search for Journal in Brave)

zbMATH Keywords

clusteringfacility locationapproximation algorithms\(k\)-means\(k\)-mediandiscrete location theory

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Analysis of algorithms (68W40) Discrete location and assignment (90B80) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Approximation algorithms (68W25)

Related Items

Incremental network design with shortest paths, A cost-sharing scheme for the \(k\)-level facility location game with penalties, A cross-monotonic cost-sharing scheme for the concave facility location game, Incremental facility location problem and its competitive algorithms, Computing knapsack solutions with cardinality robustness, An incremental version of the \(k\)-center problem on boundary of a convex polygon, A 16-competitive algorithm for hierarchical median problem, Better bounds for incremental medians, Unnamed Item, Relaxed triangle inequality ratio of the Sørensen-Dice and Tversky indexes, An Optimal Incremental Algorithm for Minimizing Lateness with Rejection, Efficient Approximations for the Online Dispersion Problem, A cost-sharing method for an uncapacitated facility location game with penalties, An Improved Competitive Algorithm for One-Dimensional Incremental Median Problem, Graph summarization with quality guarantees, The \(k\)-level facility location game, On the competitive ratio for online facility location, Towards flexible demands in online leasing problems, An approximation algorithm for the Euclidean incremental median problem, A distributed O(1)-approximation algorithm for the uniform facility location problem, Non-cooperative facility location and covering games, Incremental medians via online bidding, Kinetic facility location, A simple and deterministic competitive algorithm for online facility location, Randomized priority algorithms, Soft-capacitated facility location game, Unnamed Item, Incremental algorithms for facility location and \(k\)-median, Better Bounds for Incremental Medians, Semimetric Properties of Sørensen-Dice and Tversky Indexes, Robust Independence Systems, Cache me if you can: capacitated selfish replication games in networks, A cost-sharing method for an economic lot-sizing game, Sub-logarithmic distributed algorithms for metric facility location, Clairvoyant Mechanisms for Online Auctions, Approximation algorithms for hierarchical location problems, Near-optimal clustering in the \(k\)-machine model, The reverse greedy algorithm for the metric k-median problem, General bounds for incremental maximization