The minimal Manhattan network problem in three dimensions. (English) Zbl 1211.68514
Das, Sandip (ed.) et al., WALCOM: Algorithms and computation. Third international workshop, WALCOM 2009, Kolkata, India, February 18–20, 2009. Proceedings. Berlin: Springer (ISBN 978-3-642-00201-4/pbk). Lecture Notes in Computer Science 5431, 369-380 (2009).
Summary: For the Minimal Manhattan Network Problem in three dimensions (MMN3D), one is given a set of points in space, and an admissible solution is an axis-parallel network that connects every pair of points by a shortest path under \(L _{1}\)-norm (Manhattan metric). The goal is to minimize the overall length of the network. Here, we show that MMN3D is \(\mathcal {NP}\)- and \(\mathcal {APX}\)-hard, with a lower bound on the approximability of \(1 + 2\cdot 10^{ - 5}\). This lower bound applies to MMN2-3D already, a sub-problem in between the two and three dimensional case. For MMN2-3D, we also develop a 3-approximation algorithm which is the first algorithm for the Minimal Manhattan Network Problem in three dimensions at all.
For the entire collection see [Zbl 1156.68004].
For the entire collection see [Zbl 1156.68004].
MSC:
| 68W25 | Approximation algorithms |
| 68Q17 | Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) |
| 68R10 | Graph theory (including graph drawing) in computer science |
| 68U05 | Computer graphics; computational geometry (digital and algorithmic aspects) |
References:
| [1] | Althöfer, I., Das, G., Dobkin, D., Joseph, D., Soares, J.: On Sparse Spanners of Weighted Graphs. Discrete Comput. Geom. 9, 81–100 (1993) · Zbl 0762.05039 · doi:10.1007/BF02189308 |
| [2] | Benkert, M., Shirabe, T., Widmann, F., Wolff, A.: The Minimum Manhattan Network Problem–Approximations and Exact Solution. Computational Geometry: Theory and Applications 35(3), 188–208 (2006) · Zbl 1144.90319 · doi:10.1016/j.comgeo.2005.09.004 |
| [3] | Berman, P., Karpinski, M., Scott, A.D.: Approximation Hardness of Short Symmetric Instances of MAX-3SAT Electronic Colloquium on Computational Complexity Report No. 49 (2003), http://eccc.hpi-web.de/eccc-reports/2003/TR03-049/ |
| [4] | Chandra, B., Das, G., Narasimhan, G., Soares, J.: New Sparseness Results on Graph Spanners. Internat. J. Comput. Geom. Appl. 5, 125–144 (1995) · Zbl 0818.68078 · doi:10.1142/S0218195995000088 |
| [5] | Chen, D., Das, G., Smid, M.: Lower bounds for computing geometric spanners and approximate shortest paths. Discrete Applied Math. 110, 151–167 (2001) · Zbl 0980.68119 · doi:10.1016/S0166-218X(00)00280-8 |
| [6] | Chepoi, V., Nouioua, K., Vaxès, Y.: A rounding algorithm for approximating minimum Manhattan networks. Theoret. Comp. Sci. 390, 56–69 (2008) · Zbl 1209.90069 · doi:10.1016/j.tcs.2007.10.013 |
| [7] | Das, G., Narasimhan, G.: A Fast Algorithm for Constructing Sparse Euclidian Spanners. Internat. J. Comput. Geom. Appl. 7, 297–315 (1997) · Zbl 0883.68117 · doi:10.1142/S0218195997000193 |
| [8] | Engels, B.: The Transitive Minimum Manhattan Subnetwork Problem in 3 Dimensions. Submitted to Discrete Applied Mathematics: Proceedings of the 6th Cologne Twente Workshop 2007 (November 12, 2007) · Zbl 1226.05098 |
| [9] | Gudmundsson, J., Levcopoulos, C., Narasimhan, G.: Approximating a Minimum Manhattan Network. Nordic J. Computing 8, 219–232 (2001) · Zbl 0985.68092 |
| [10] | Gudmundsson, J., Levcopoulos, C., Narasimhan, G.: Fast Greedy Algorithms for Constructing Sparse Geometric Spanners. SIAM J. Computing 31, 1479–1500 (2002) · Zbl 1041.68108 · doi:10.1137/S0097539700382947 |
| [11] | Kato, R., Imai, K., Asano, T.: An improved algorithm for the minimum manhattan network problem. In: Bose, P., Morin, P. (eds.) ISAAC 2002. LNCS, vol. 2518, pp. 344–356. Springer, Heidelberg (2002) · Zbl 1019.68819 · doi:10.1007/3-540-36136-7_31 |
| [12] | Seibert, S., Unger, W.: A 1.5-approximation of the minimal manhattan network problem. In: Deng, X., Du, D.-Z. (eds.) ISAAC 2005. LNCS, vol. 3827, pp. 246–255. Springer, Heidelberg (2005) · Zbl 1173.68869 · doi:10.1007/11602613_26 |
| [13] | Seibert, S., Unger, W.: Refined Analysis of the Minimal Manhattan Network Problem and a 1.25 Approximation (submitted for publication) |
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.
