×

Inverse median location problems with variable coordinates. (English) Zbl 1204.90059

Summary: Given \(n\) points in \(\mathbb{R}^d\) with nonnegative weights, the inverse 1-median problem with variable coordinates consists in changing the coordinates of the given points at minimum cost such that a prespecified point in \(\mathbb{R}^d\) becomes the 1-median. The cost is proportional to the increase or decrease of the corresponding point coordinate. If the distances between points are measured by the rectilinear norm, the inverse 1-median problem is NP-hard, but it can be solved in pseudo-polynomial time. Moreover, a fully polynomial time approximation scheme exists in this case. If the point weights are assumed to be equal, the corresponding inverse problem can be reduced to \(d\) continuous knapsack problems and is therefore solvable in \(O(nd)\) time. In case that the squared Euclidean norm is used, we derive another efficient combinatorial algorithm which solves the problem in \(O(nd)\) time. It is also shown that the inverse 1-median problem endowed with the Chebyshev norm in the plane is NP-hard. Another pseudo-polynomial algorithm is developed for this case, but it is shown that no fully polynomial time approximation scheme does exist.

MSC:

90B80 Discrete location and assignment
90C27 Combinatorial optimization
Full Text: DOI

References:

[1] Alizadeh B, Burkard RE (2009) Combinatorial algorithms for inverse absolute and vertex 1-center location problems on trees. Technical Report 2009-09, Graz University of Technology · Zbl 1236.90094
[2] Alizadeh B, Burkard RE, Pferschy U (2009) Inverse 1-center location problems with edge length augmentation on trees. To appear in Computing · Zbl 1180.90163
[3] Balas E, Zemel E (1980) An algorithm for large zero-one knapsack problem. Oper Res 28: 1130–1154 · Zbl 0449.90064 · doi:10.1287/opre.28.5.1130
[4] Baroughi Bonab F, Burkard RE, Gassner E (2009) Inverse p-median problems with variable edge lengths. Technical Report 2009-13, Graz University of Technology · Zbl 1216.49032
[5] Burkard RE, Pleschiutschnig C, Zhang J (2004) Inverse median problems. Discret Optim 1: 23–39 · Zbl 1087.90038 · doi:10.1016/j.disopt.2004.03.003
[6] Burkard RE, Galavii M, Gassner E (2008a) The inverse Fermat–Weber problem. Technical Report 2008-14, Graz University of Technology · Zbl 1188.90209
[7] Burkard RE, Pleschiutschnig C, Zhang JZ (2008b) The inverse 1- median problem on a cycle. Discret Optim 5: 242–253 · Zbl 1177.90245 · doi:10.1016/j.disopt.2006.11.008
[8] Cai MC, Yang XG, Zhang JZ (1999) The complexity analysis of the inverse center location problem. J Glob Optim 15: 213–218 · Zbl 0978.90065 · doi:10.1023/A:1008360312607
[9] Gassner E (2008) The inverse 1-maxian problem with edge length modification. J Comb Optim 16: 50–67 · Zbl 1180.90165 · doi:10.1007/s10878-007-9098-9
[10] Hamacher HW (1995) Mathematische Lösungsverfahren für planare Standortprobleme. Vieweg, Braunschweig
[11] Kellerer H, Pferschy U, Pisinger D (2004) Knapsack problems. Springer, Berlin · Zbl 1103.90003
[12] Martello S, Toth P (1990) Knapsack problems: algorithms and computer implementations. Wiley, Chichester · Zbl 0708.68002
[13] Pruhs K, Woeginger GJ (2007) Approximation schemes for a class of subset selection problems. Theor Comput Sci 382: 151–156 · Zbl 1119.90077 · doi:10.1016/j.tcs.2007.03.006
[14] Yang X, Zhang J (2008) Inverse center location problem on a tree. J Syst Sci Complex 21: 651–664 · Zbl 1180.90171 · doi:10.1007/s11424-008-9142-6
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.