A combinatorial algorithm for the 1-median problem in R-d with the Chebyshev norm

作者：Hatzl Johannes^*; Karrenbauer Andreas

来源：Operations Research Letters, 2010, 38(5): 383-385.

DOI：10.1016/j.orl.2010.07.002

• Facility location
• 1-median problem
• Fractional b-matching

We consider the 1-median problem in R-d with the Chebyshev norm: given n points with non-negative weights, find a point that minimizes the sum of the weighted distances to the given points. We propose a combinatorial algorithm for this problem by reformulating it as a fractional b-matching problem. This graph-theoretical problem can be solved by a min-cost-flow algorithm. Moreover, we show that there is a 1-median, which is half-integral, provided that the points have integral coordinates.

• 出版日期2010-9