On Minimum- and Maximum-Weight Minimum Spanning Trees with Neighborhoods

详细信息    查看全文

• 作者：Reza Dorrigiv (1)
  Robert Fraser (2)
  Meng He (1)
  Shahin Kamali (3)
  Akitoshi Kawamura (4)
  Alejandro L贸pez-Ortiz (3)
  Diego Seco (5)
  
  1. Dalhousie University ; Halifax ; Canada
  2. University of Manitoba ; Winnipeg ; Canada
  3. University of Waterloo ; Waterloo ; Canada
  4. University of Tokyo ; Tokyo ; Japan
  5. University of Concepci贸n ; Concepci贸n ; Chile
  
• 关键词：Computational geometry ; Imprecise data ; Minimum spanning trees
• 刊名：Theory of Computing Systems
• 出版年：2015
• 出版时间：January 2015
• 年：2015
• 卷：56
• 期：1
• 页码：220-250
• 全文大小：1,406 KB
• 参考文献：1. Arkin, E., Hassin, R.: Approximation algorithms for the geometric covering salesman problem. Discret. Appl. Math. 55(3), 197鈥?18 (1994) CrossRef
  2. Arora, S.: Polynomial time approximation schemes for Euclidean traveling salesman and other geometric problems. J. ACM 45(5), 753鈥?82 (1998) CrossRef
  3. Bajaj, C.: Geometric optimization and computational complexity. Ph.D. thesis, Cornell University (1984)
  4. Bajaj, C.: The algebraic degree of geometric optimization problems. Discret. Comput. Geom. 3(1), 177鈥?91 (1988) CrossRef
  5. de Berg, M., Gudmundsson, J., Katz, M., Levcopoulos, C., Overmars, M., van der Stappen, A.: TSP with neighborhoods of varying size. J. Algorithm. 57(1), 22鈥?6 (2005) CrossRef
  6. Biedl, T., Kaufmann, M.: Area-efficient static and incremental graph drawings In: Proceedings of the European Symposium on Algorithms, Lecture Notes in Computer Science, vol. 1284, pp. 37鈥?2 (1997)
  7. Bl枚mer, J.: Computing sums of radicals in polynomial time. In: Proceedings of the Symposium on Foundations of Computer Science (FOCS), pp. 670鈥?77. IEEE Computer Society (1991)
  8. Callahan, P.B., Kosaraju, S.R.: A decomposition of multidimensional point sets with applications to k-nearest-neighbors and n-body potential fields. J. ACM 42(1), 67鈥?0 (1995) CrossRef
  9. Chambers, E., Erickson, A., Fekete, S., Lenchner, J., Sember, J., Venkatesh, S., Stege, U., Stolpner, S., Weibel, C., Whitesides, S.: Connectivity graphs of uncertainty regions In: Proceedings of the International Symposium on Algorithms and Computation (ISAAC), Lecture Notes in Computer Science, vol. 6507, pp. 434鈥?45 (2010)
  10. Chou, C.C.: An efficient algorithm for relay placement in a ring sensor networks. Expert Syst. Appl. 37(7), 4830鈥?841 (2010) CrossRef
  11. Dumitrescu, A., Mitchell, J.S.: Approximation algorithms for TSP with neighborhoods in the plane. J. Algorithm 48(1), 135鈥?59 (2003) CrossRef
  12. Durocher, S., Kirkpatrick, D.: The projection median of a set of points. Comput. Geom. 42(5), 364鈥?75 (2009). Special Issue on the Canadian Conference on Computational Geometry (CCCG 2005 and CCCG 2006) CrossRef
  13. Erickson, J., (user J 蔚ffE): Sum-of-square-roots-hard problems? Theoretical Computer Science on StackExchange, http://cstheory.stackexchange.com/questions/4053/sum-of-square-roots-hard-problems (2011)
  14. Erlebach, T., Hoffmann, M., Krizanc, D., Mihal谩k, M., Raman, R.: Computing minimum spanning trees with uncertainty In: Proceedings of the Symposium on Theoretical Aspects of Computer Science (STACS), pp. 277鈥?88 (2008)
  15. de Fermat, P.: Oeuvres de Fermat (Tome 1). Gauthier-Villars et Fils, Paris (1891)
  16. Fiala, J., Kratochv铆l, J., Proskurowski, A.: Systems of distant representatives. Discret. Appl. Math. 145(2), 306鈥?16 (2005) CrossRef
  17. Fischetti, M., Hamacher, H.W., J酶rnsten, K., Maffioli, F.: Weighted k-cardinality trees: Complexity and polyhedral structure. Networks 24(1), 11鈥?1 (1994) CrossRef
  18. Graham, R.L., Hell, P.: On the history of the minimum spanning tree problem. IEEE Ann. Hist. Comput. 7(1), 43鈥?7 (1985) CrossRef
  19. Jarn铆k, V.: O jist茅m probl茅mu minim谩ln铆m (About a certain minimal problem). Pr谩ca Moravsk茅 Pr铆rodovedeck茅 Spolecnosti 6, 57鈥?3 (1930). (in Czech, German summary)
  20. Lichtenstein, D.: Planar formulae and their uses. SIAM J. Comput. 11(2), 329鈥?43 (1982) CrossRef
  21. L枚ffler, M., van Kreveld, M.: Largest and smallest convex hulls for imprecise points. Algorithmica 56(2), 235鈥?69 (2010) CrossRef
  22. Sekino, J.: n-ellipses and the minimum distance sum problem. Am. Math. Mon. 106(3), 193鈥?02 (1999) CrossRef
  23. Yang, Y.: On several geometric network design problems. Ph.D. thesis, State University of New York at Buffalo (2008)
  24. Yang, Y., Lin, M., Xu, J., Xie, Y.: Minimum spanning tree with neighborhoods In: Proceedings of Algorithmic Aspects in Information and Management (AAIM), Lecture Notes in Computer Science, vol. 4508, pp. 306鈥?16 (2007)
  
• 刊物类别：Computer Science
• 刊物主题：Theory of Computation
  Computational Mathematics and Numerical Analysis
  
• 出版者：Springer New York
• ISSN：1433-0490

文摘

We study optimization problems for the Euclidean Minimum Spanning Tree (MST) problem on imprecise data. To model imprecision, we accept a set of disjoint disks in the plane as input. From each member of the set, one point must be selected, and the MST is computed over the set of selected points. We consider both minimizing and maximizing the weight of the MST over the input. The minimum weight version of the problem is known as the Minimum Spanning Tree with Neighborhoods (MSTN) problem, and the maximum weight version (max-MSTN) has not been studied previously to our knowledge. We provide deterministic and parameterized approximation algorithms for the max-MSTN problem, and a parameterized algorithm for the MSTN problem. Additionally, we present hardness of approximation proofs for both settings.