Line Facility Location in Weighted Regions

摘要

In this paper, we present approximation algorithms for the line facility location problem in weighted regions: Given l fixed points in a 2-dimensional weighted subdivision of the plane, with n vertices, find a line L such that the sum of the weighted distances from the fixed points to L is minimized. The weighted region setup is a more realistic model for many facility location problems that arise in practical applications. Our algorithms exploit an interesting property of the problem, that could possibly be used for solving other problems in weighted regions.