An efficient algorithm for the single facility location problem with polyhedral norms and disk-shaped demand regions
Tóm tắt
The single facility location problem with demand regions seeks for a facility location minimizing the sum of the distances from n demand regions to the facility. The demand regions represent sales markets where the transportation costs are negligible. In this paper, we assume that all demand regions are disks of the same radius, and the distances are measured by a rectilinear norm, e.g.
$$\ell _1$$
or
$$\ell _\infty $$
. We develop an exact combinatorial algorithm running in time
$$O(n\log ^c n)$$
for some c dependent only on the space dimension. The algorithm is generalizable to the other polyhedral norms.
Tài liệu tham khảo
Bajaj, C.: Proving geometric algorithms nonsolvability: an application of factoring polynomials. J. Symb. Comput. 2(1), 99–102 (1986)
Barvinok, A., Johnson, D.S., Woeginger, G.J., Woodroof, R.: The maximum traveling salesman problem under polyhedral norms. In: Bixby, R.E. et al. (Eds.) Integer Programming and Combinatorial Optimization, 6th International IPCO Conference, Houston, Texas, USA, June 22–24, 1998, Proceedings. Lecture Notes in Computer Science 1412, Springer, Berlin-Heidelberg 1998, pp. 195–201 (1998)
Brimberg, J., Wesolowsky, G.O.: Minisum location with closest Euclidean distances. Ann. Oper. Res. 111(1), 151–165 (2002)
Cohen, E., Megiddo, N.: Maximizing concave functions in fixed dimension. In: Pardalos, P.M. (ed.) Complexity in Numerical Optimization, pp. 74–87. World Scientific, Singapore (1993)
Cohen, M., Lee, Y.T., Miller, G., Pachocki, J., Sidford, A.: Geometric median in nearly linear time. In: Proceedings of the 48th Annual ACM Symposium on Theory of Computing (STOC) 2016, Cambridge, MA, USA, pp. 9–21 (2016)
Dinler, D., Tural, M.K., Iyigun, C.: Heuristics for a continuous multi-facility location problem with demand regions. Comput. Oper. Res. 62, 237–256 (2015)
Kalcsics, J., Nickel, S., Puerto, J., Tamir, A.: Algorithmic results for ordered median problems. Oper. Res. Lett. 30(3), 149–158 (2002)
Karmarkar, N.: A new polynomial-time algorithm for linear programming. Combinatorica 4(4), 373–395 (1984)
Kumar, A., Sabharwal, Y., Sen, S.: Linear-time approximation schemes for clustering problems in any dimensions. J. ACM 57(2), 1–32 (2010)
Nickel, S., Puerto, J.: Location Theory: A Unified Approach. Springer, Berlin (2005)
Nickel, S., Puerto, J., Rodriguez-Chia, A.M.: An approach to location models involving sets as existing facilities. Math. Oper. Res. 28(4), 693–715 (2003)
Nickel, S., Puerto, J., Rodriguez-Chia, A.M., Weißler, A.: Multicriteria planar ordered median problems. J. Optim. Theory Appl. 126(3), 657–683 (2005)
Puerto, J., Fernandez, F.R.: Geometrical properties of the symmetric single facility location problem. J. Nonlinear Convex Anal. 1(3), 321–342 (2000)
Vaidya, P.M.: Speeding-up linear programming using fast matrix multiplication. In: Proceedings of the 30th Annual Symposium on Foundations of Computer Science (SFCS) 1989, pp. 332–337, Research Triangle Park, North Carolina, USA (1989)