An improved competitive algorithm for one-dimensional incremental median problem

DOI10.1007/978-3-642-21204-8_7MaRDI QIDQ3004653zbMATH OpenOpenAlexFDO

Authors Wenqiang Dai, Yi Feng

Publication date 3 June 2011

Published in Frontiers in Algorithmics and Algorithmic Aspects in Information and Management (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/978-3-642-21204-8_7

Mathematics Subject Classification ID

Combinatorial optimization (90C27) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Approximation algorithms (68W25) Discrete location and assignment (90B80)

Recommendations

• Better Bounds for Incremental Medians
• Better bounds for incremental medians
• An approximate solution algorithm for the one-dimensional online median problem
• An approximation algorithm for the Euclidean incremental median problem
• Incremental facility location problem and its competitive algorithms

Cites work

• scientific article; zbMATH DE number 44281 (Why is no real title available?)
• scientific article; zbMATH DE number 4123493 (Why is no real title available?)
• scientific article; zbMATH DE number 1746287 (Why is no real title available?)
• scientific article; zbMATH DE number 1775394 (Why is no real title available?)
• scientific article; zbMATH DE number 821272 (Why is no real title available?)
• A general approach for incremental approximation and hierarchical clustering
• A new greedy approach for facility location problems
• An Overview of Representative Problems in Location Research
• Better Bounds for Incremental Medians
• Greedy Strikes Back: Improved Facility Location Algorithms
• Improved complexity bounds for location problems on the real line
• Local search heuristic for k-median and facility location problems
• Oblivious Medians Via Online Bidding
• The Online Median Problem

Cited in

(7)

• Incremental medians via online bidding
• An approximate solution algorithm for the one-dimensional online median problem
• Better Bounds for Incremental Medians
• Incremental facility location problem and its competitive algorithms
• An approximation algorithm for the Euclidean incremental median problem
• A 16-competitive algorithm for hierarchical median problem
• Better bounds for incremental medians

This page was built for publication: An improved competitive algorithm for one-dimensional incremental median problem

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