Integer point sets minimizing average pairwise \(L_{1}\) distance: What is the optimal shape of a town? (English) Zbl 1208.65085
The authors study a special case of the task consisting in finding \(n\) sites from a given set of candidate locations, which minimizes the average distance between the sites. In the special case studied in the paper, a group of \(n\) buildings each occupying; a distinct site on a 2-dimensional integer grid is considered. Such group of buildings is called \(n\)-town and different positions of the building form different shapes of the \(n\)-town. The authors propose a procedure, which makes possible to find the optimal shape of the \(n\)-town, i.e. the shape, which minimizes the sum of all pairwise Manhattan distances between the buildings. Computational experience with the proposed method for values of \(n\) up to \(n= 80\) is presented in the concluding part of the paper.
Reviewer: Karel Zimmermann (Praha)
MSC:
| 65K05 | Numerical mathematical programming methods |
References:
| [1] | Arora, S.; Karger, D. R.; Karpinski, M., Polynomial time approximation schemes for dense instances of NP-hard problems, J. Comput. Syst. Sci., 58, 1, 193-210 (1999) · Zbl 0937.68160 |
| [2] | Asahiro, Y.; Iwama, K.; Tamaki, H.; Tokuyama, T., Greedily finding a dense subgraph, J. Algorithms, 34, 2, 203-221 (2000) · Zbl 0958.68132 |
| [3] | Y. Bartal, M. Charikar, D. Raz, Approximating min-sum \(k\); Y. Bartal, M. Charikar, D. Raz, Approximating min-sum \(k\) · Zbl 1323.68565 |
| [4] | Bender, C. M.; Bender, M. A.; Demaine, E. D.; Fekete, S. P., What is the optimal shape of a city?, J. Phys. A: Math. Gen., 37, 147-159 (2004) · Zbl 1046.90538 |
| [5] | Bender, M. A.; Bunde, D. P.; Demaine, E. D.; Fekete, S. P.; Leung, V. J.; Meijer, H.; Phillips, C. A., Communication-aware processor allocation for supercomputers: Finding point sets of small average distance, Algorithmica, 50, 2, 279-298 (2008) · Zbl 1141.68017 |
| [6] | Fekete, S. P.; Meijer, H., Maximum dispersion and geometric maximum weight cliques, Algorithmica, 38, 501-511 (2003) · Zbl 1095.68082 |
| [7] | Fekete, S. P.; Mitchell, J. S.B.; Beurer, K., On the continuous Fermat-Weber problems, Oper. Res., 53, 61-76 (2005) · Zbl 1165.90553 |
| [8] | S.P. Fekete, J.S.B. Mitchell, K. Weinbrecht, On the continuous Weber and \(k\); S.P. Fekete, J.S.B. Mitchell, K. Weinbrecht, On the continuous Weber and \(k\) · Zbl 1377.90054 |
| [9] | Guttmann-Beck, N.; Hassin, R., Approximation algorithms for minimum sum \(p\)-clustering, Disc. Appl. Math., 89, 125-142 (1998) · Zbl 0921.68044 |
| [10] | Hassin, R.; Levin, A.; Sviridenko, M., Approximating the minimum quadratic assignment problems, ACM Trans. Algorithms, 6, 1, 18:1-18:10 (2009) · Zbl 1300.90024 |
| [11] | Hassin, R.; Rubinstein, S.; Tamir, A., Approximation algorithms for maximum dispersion, Oper. Res. Lett., 21, 3, 133-137 (1997) · Zbl 0888.90144 |
| [12] | P. Indyk, A sublinear time approximation scheme for clustering in metric spaces, in: Proc. 40th Annual IEEE Symposium on Foundations of Computer Science (FOCS), 1999, pp. 154-159.; P. Indyk, A sublinear time approximation scheme for clustering in metric spaces, in: Proc. 40th Annual IEEE Symposium on Foundations of Computer Science (FOCS), 1999, pp. 154-159. |
| [13] | Karp, R. M.; McKellar, A. C.; Wong, C. K., Near-optimal solutions to a 2-dimensional placement problem, SIAM J. Comput., 4, 3, 271-286 (1975) · Zbl 0355.68044 |
| [14] | Kortsarz, G.; Peleg, D., On choosing a dense subgraph, (Proc. 34th Annual Symposium on Foundations of Computer Science (1993), IEEE Computer Society Press: IEEE Computer Society Press Palo Alto, CA), 692-703 |
| [15] | Krumke, S.; Marathe, M.; Noltemeier, H.; Radhakrishnan, V.; Ravi, S.; Rosenkrantz, D., Compact location problems, Theoret. Comput. Sci., 181, 2, 379-404 (1997) · Zbl 0902.90114 |
| [16] | V. Leung, E. Arkin, M. Bender, D. Bunde, J. Johnston, A. Lal, J. Mitchell, C. Phillips, S. Seiden, Processor allocation on Cplant: Achieving general processor locality using one-dimensional allocation strategies. in: Proc. 4th IEEE International Conference on Cluster Computing, 2002, pp. 296-304.; V. Leung, E. Arkin, M. Bender, D. Bunde, J. Johnston, A. Lal, J. Mitchell, C. Phillips, S. Seiden, Processor allocation on Cplant: Achieving general processor locality using one-dimensional allocation strategies. in: Proc. 4th IEEE International Conference on Cluster Computing, 2002, pp. 296-304. |
| [17] | Loiola, E. M.; de Abreu, N. M.M.; Boaventura-Netto, P. O.; Hahn, P.; Querido, T. M., A survey for the quadratic assignment problem, Eur. J. Oper. Res., 176, 2, 657-690 (2007) · Zbl 1103.90058 |
| [18] | J. Mache, V. Lo, Dispersal metrics for non-contiguous processor allocation, Technical Report CIS-TR-96-13, University of Oregon, 1996.; J. Mache, V. Lo, Dispersal metrics for non-contiguous processor allocation, Technical Report CIS-TR-96-13, University of Oregon, 1996. |
| [19] | J. Mache, V. Lo, The effects of dispersal on message-passing contention in processor allocation strategies, in: Proc. Third Joint Conference on Information Sciences, Sessions on Parallel and Distributed Processing, vol. 3, 1997, pp. 223-226.; J. Mache, V. Lo, The effects of dispersal on message-passing contention in processor allocation strategies, in: Proc. Third Joint Conference on Information Sciences, Sessions on Parallel and Distributed Processing, vol. 3, 1997, pp. 223-226. |
| [20] | Ravi, S. S.; Rosenkrantz, D. J.; Tayi, G. K., Heuristic and special case algorithms for dispersion problems, Oper. Res., 42, 2, 299-310 (1994) · Zbl 0805.90074 |
| [21] | Sahni, S.; Gonzalez, T., \(P\)-complete approximation problems, J. ACM, 23, 3, 555-565 (1976) · Zbl 0348.90152 |
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.
