arXiv:2611.13224 · v1

An Improved $(1+2e)$-Approximation Algorithm for Metric Data Placement

首次提交 2026-11-10 04:53

版本更新 2026-11-10 04:53

雷达观测 2026-11-11 11:04

摘要

We study the metric data placement problem with site-capacity constraints and fixed installation costs, aiming to minimize the total cost of placing data (resources) and accessing their nearest copies. We develop a deterministic polynomial-time approximation algorithm based on a natural linear programming relaxation of the problem. Starting from an optimal fractional solution, we construct multiscale metric-ball partitions independently for each resource and connect overlapping balls at consecutive levels to form a flow network. The resource layers are then coupled through shared site-capacity arcs, allowing us to obtain an integral placement by minimizing a surrogate cost over a single min-cost circulation. By optimizing the choice of ball radii, we establish an approximation factor of $1+2e\approx 6.44$. To our knowledge, this is the best approximation guarantee for the metric data placement problem since its introduction by Baev and Rajaraman in 2001.