Exact approximation ratio found for rotated coordinate median in plane

The Exact Approximation Ratio of Uniformly Rotated Coordinate-wise Median in the Euclidean Plane

Computational Engineering, Finance, and ScienceComputer Science and Game Theory

Summary

The paper studies a method to pick a point based on many agents’ locations by choosing a random rotated coordinate system, finding the median on each axis, and converting back to normal coordinates. The authors find the exact worst-case ratio comparing this point's total distance to agents against the best possible, for certain ways of measuring distances. They prove the upper bound on this ratio matches a previously known lower bound, using a new inequality and a careful averaging technique over rotations. This precisely characterizes the method's worst-case performance but does not claim it is optimal among all possible methods.

What this means in practice

  • For location-based service developers: Use the exact performance guarantee of rotated coordinate medians to design robust location aggregation in spatial preference systems.
  • For distributed system engineers: Implement coordinate-wise median selection with known error bounds for consensus and aggregation in distributed networks handling spatial data.

A theory result. No direct application yet.

Authors

Song Zichen

Abstract

Uniformly rotated coordinate-wise median chooses a random orthonormal coordinate system, takes a median in each coordinate, and maps the resulting point back to the Euclidean plane. We determine its exact worst-case expected approximation ratio when social cost is the $L_p$ norm of the agents' Euclidean distances and $1<p<2$. The ratio is \(\frac{2^{2-1/p}}π\int_0^{π/2}(\cos^pθ+\sin^pθ)^{1/p}\ddθ\). This expression was previously established as a lower bound by Chan, Lin, and Wang; our contribution is the matching upper bound. The proof establishes a strengthened coordinate-wise median inequality relative to an arbitrary reference point. Its right-hand side is linear in a sum of direction-dependent norms, which permits direct averaging over rotations without the loss incurred by passing through a $p$th-moment bound. We give all auxiliary inequalities and a self-contained proof of tightness using the established two-cluster-and-outlier construction. The upper bound holds for every finite profile and every measurable choice within the coordinate median intervals, while odd-size profiles suffice for the matching lower bound. The result characterizes this fixed mechanism, rather than the optimal approximation ratio among all randomized strategyproof mechanisms.
View PDFOpen arXiv