Skip to main content
Fachgebiete
Automobil + Motoren Bauwesen + Immobilien Business IT + Informatik Elektrotechnik + Elektronik Energie + Nachhaltigkeit Finance + Banking Management + Führung Marketing + Vertrieb Maschinenbau + Werkstoffe Versicherung + Risiko
DE
EN
Themenseiten
Organisationspsychologie Projektmanagement Marketing Smart Manufacturing
Bücher
Zeitschriften
Weitere Formate
Podcasts Webinare Technik Webinare Wirtschaft Kongresse Veranstaltungskalender Awards
Jetzt Einzelzugang starten
Zugang für Unternehmen
Referenzkunden
MTZ-Fachkongress

Antriebe und Energiesysteme von morgen


Austausch von Automobil- und Energiewirtschaft

Am 14./15. Mai geht es in Chemnitz um die Mobilitätswende durch Elektro- und Wasserstofffahrzeuge.
Erweiterte Suche
Anmelden
nach oben
Erschienen in:
A Unified Approach for Domination Problems on Different Network Topologies Kapitel lesen Erstes Kapitel lesen

2013 | OriginalPaper | Buchkapitel

Partition in High Dimensional Spaces

verfasst von : Zhao Zhang, Weili Wu

Erschienen in: Handbook of Combinatorial Optimization

Verlag: Springer New York

Einloggen

Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.

search-config
loading …

Abstract

Partition combined with shifting strategy is a powerful method in producing polynomial time approximation scheme (PTAS) for many NP-hard geometric problems. The focus of this chapter is on the ideas and the techniques of partition method which can be applied to high dimensional space, including the basic ideas, the small compensation technique which is used to deal with the requirement of connection, the multilayer partition technique which is used to deal with the situation when the geometric objects are not uniform, and the growing partition technique which does not require the geometric representation of the graph.

Sie haben noch keine Lizenz? Dann Informieren Sie sich jetzt über unsere Produkte:

Springer Professional "Wirtschaft+Technik"

Online-Abonnement

Mit Springer Professional "Wirtschaft+Technik" erhalten Sie Zugriff auf:

  • über 102.000 Bücher
  • über 537 Zeitschriften

aus folgenden Fachgebieten:

  • Automobil + Motoren
  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Elektrotechnik + Elektronik
  • Energie + Nachhaltigkeit
  • Finance + Banking
  • Management + Führung
  • Marketing + Vertrieb
  • Maschinenbau + Werkstoffe
  • Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

Jetzt informieren

Springer Professional "Technik"

Online-Abonnement

Mit Springer Professional "Technik" erhalten Sie Zugriff auf:

  • über 67.000 Bücher
  • über 390 Zeitschriften

aus folgenden Fachgebieten:

  • Automobil + Motoren
  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Elektrotechnik + Elektronik
  • Energie + Nachhaltigkeit
  • Maschinenbau + Werkstoffe




 

Jetzt Wissensvorsprung sichern!

Jetzt informieren

Springer Professional "Wirtschaft"

Online-Abonnement

Mit Springer Professional "Wirtschaft" erhalten Sie Zugriff auf:

  • über 67.000 Bücher
  • über 340 Zeitschriften

aus folgenden Fachgebieten:

  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Finance + Banking
  • Management + Führung
  • Marketing + Vertrieb
  • Versicherung + Risiko




Jetzt Wissensvorsprung sichern!

Jetzt informieren
Vorheriges Kapitel Packing Circles in Circles and Applications
Nächstes Kapitel Probabilistic Verification and Non-approximability
Literatur
1.
P.K. Agarwal, M. van Kreveld, S. Suri, Label placement by maximum independent set in rectangles. Comput. Geom. Theory Appl. 11, 209–218 (1998)CrossRefMATH
2.
K.M. Alzoubi, P. Wan, O. Frieder, Message-optimal connected dominating sets in mobile ad hoc networks, in Proceedings of the 3rd ACM International Symposium on Mobile Ad Hoc Networking and Computing, Lausanne, 2002
3.
E.M. Arkin, M.M. Halldǒrsson, R. Hassin, Approximating the tree and tour covers of a graph. Inform. Process. Lett. 47, 275–282 (1993)MathSciNetCrossRefMATH
4.
S. Arora, C. Lund, R. Motwani, M. Sudan, M. Szegegy, Proof verification and hardness of approximation problems, in Proc. 33rd Annual Symp. on Foundations of Computer Science (FOCS 1992), Pittsburgh, PA, 1992, pp. 14–23
5.
B.S. Baker, Approximation algorithms for NP-complete problems on planar graphs, in Proceedings of the 24th Annual IEEE Symposium on Foundations of Computer Science, Tucson, November 7–9. IEEE, New York, 1983, pp. 254–273. J. ACM 41, 153–180 (1994)
6.
R. Bar-Yehuda, S. Even, On approximating a vertex cover for planar graphs, in STOC, New York, NY, USA, 1982, pp. 303–309
7.
R. Bar-Yehuda, S. Even, A local-ratio theorem for approximating the weighted vertex cover problem. Inform. Process. Lett. 47, 275–282 (1993)MathSciNetCrossRef
8.
P. Berman, T. Fujito, On approximation properties of the independent set problem for degree 3 graphs, Workshop on Algorithms and Data Structures. Lect. Note Comput. Sci. 955, 449–460 (1995)MathSciNetCrossRef
9.
P. Berman, B. Basgupta, S. Muthukrishnan, S. Ramaswami, Efficient approximation algorithms for tiling and packing problem with rectangles. J. Algorithm 41, 178–189 (2001)
10.
V. Bharghavan, B. Das, Routing in ad hoc networks using minimum connected dominating sets, in International Conference on Communication, Montreal, 1997
11.
J. Blum, M. Ding, A. Thaeler, X.Z. Cheng, Connected dominating set in sensor networks and MANETs, in Handbook of Combinatorial Optimization (Kluwer Academic, Dordrecht, 2004), pp. 329–369
12.
13.
14.
M. Cadei, M.X. Cheng, X. Cheng, D. Du, Connected domination in ad hoc wireless networks, in Proceedings of the Sixth International Symposium on Mobile Ad Hoc Networking and Computing, Lausanne, 2002
15.
T.M. Chan, Polynomial-time approximation schemes for packing and piercing fat objects. J. Algorithm 46, 178–189 (2003)CrossRefMATH
16.
Y.P. Chen, A.L. Liestman, Approximating minimum size weakly-connected dominating sets for clustering mobile ad hoc networks, in Proceedings of the Third ACM International Symposium on Mobile Ad Hoc Networking and Computing, Lausanne, 2002
17.
X. Cheng, X. Huang, D. Li, W. Wu, D. Du, A polynomial-time approximation scheme for minimum connected dominating set in ad hoc wireless networks. Networks 42, 202–208 (2003)MathSciNetCrossRefMATH
18.
19.
B. Das, V. Bharghavan, Routing in ad-hoc networks using minimum connected dominating sets, in ICC’97, Las Vegas, NV, USA, 1997, pp. 376–380
20.
21.
D.-Z. Du, Y. Zhang, Q. Feng, On better heuristic for Euclidean Steiner minimum trees, in Proceedings 32nd IEEE Symposium on Foundations of Computer Science, San Juan, Puerto Rico, 1991, pp. 431–439
22.
T. Erlebach, K. Jansen, E. Seidel, Polynomial-time approximation schemes for geometric graphs, in Proceedings of the 12th ACM-SIAM Symposium on Discrete Algorithms (SODA’01), Philadelphia, PA, USA, 2001, pp. 671–679
23.
T. Erlebach, K. Jansen, E. Seidel, Polynomial-time approximation schemes for geometric intersection graphs. SIAM J. Comput. 34, 1302–1323 (2005)MathSciNetCrossRefMATH
24.
B. Escoffier, L. Gourvès, J. Monnot, Complexity and approximation results for the connected vertex cover problem. Graph Theor. Concept Comput. Sci. Lect. Note Comput. Sci. 4769, 202–213 (2007)CrossRef
25.
U. Feige, A threshold of lnn for approximating set cover, in Proceedings of the 28th Annual ACM Symposium on Theory of Computing (STOC), (ACM, New York, 1996), pp. 314–318
26.
T. Fujito, T. Doi, A 2-approximation NC algorithm for connected vertex cover and tree cover. Inform. Process. Lett. 90, 59–63 (2004)MathSciNetCrossRefMATH
27.
X.F. Gao, W. Wang, Z. Zhang, S.W. Zhu, W.L. Wu, A PTAS for minimum d-hop connected dominating set in growth bounded graphs. Optim. Lett. 4, 321–333 (2010)MathSciNetCrossRefMATH
28.
M.R. Garey, D.S. Johnson, Computers and Intractability: A Guide to the Theory of NP-Completeness (Freeman, San Francisco, 1978)
29.
B. Gfeller, E. Vicari, A Faster distributed approximation scheme for the connected dominating set problem for growth-bounded graphs, in ADHOC-NOW 2007, vol. 4686, ed. by E. Kranakis, J. Opatrny. LNCS (2007), pp. 59–73
30.
C. Glaßer, S. Reith, H. Vollmer, The complexity of base station positioning in cellular networks. Discrete Appl. Math. 148, 1–12 (2005)MathSciNetCrossRefMATH
31.
32.
D.S. Hochbaum, W. Maass, Approximation schemes for covering and packing problems in image processing and VLSI. J. ACM 32, 130–136 (1985)MathSciNetCrossRefMATH
33.
D.S. Hochbaum, Approximation Algorithm for NP-Hard Problems (PWS, Boston, 1997)
34.
H.B. Hunt III, M.V. Marathe, V. Radhakrishnan, S.S. Ravi, D.J. Rosenkrantz, R.E. Stearns, NC-approximation schemes for NP- and PSPACE-hard problems for geometric graphs. J. Algorithm 26, 238–274 (1998)MathSciNetCrossRefMATH
35.
K. Jansen, L. Porkolab, On preemptive resource constrained scheduling: polynomial-time approximation schemes. Int. Programm. Combin. Optim. Lect. Note Comput. Sci. 2337, 329–349 (2006)MathSciNetCrossRef
36.
T. Jiang, E.B. Lawler, L.S. Wang, Aligning sequences via an evolutionary tree: complexity and algorithms, in Proceedings 26th ACM Symposium on Theory of Computing, New York, NY, USA, 1994, pp. 760–769
37.
D.S. Johnson, Approximation algorithms for combinatorial problems. JCSS 9, 256–278 (1974)MATH
38.
R.M. Karp, Probabilistic analysis of partitioning algorithms for the travelling-salesman problem in the plane. Math. Oper. Res. 2, 209–224 (1977)MathSciNetCrossRefMATH
39.
S. Khot, O. Regev, Vertex cover might be hard to approximate to within \(2 - \epsilon \). J. Comput. Syst. Sci. 74, 335–349 (2008)MathSciNetCrossRefMATH
40.
S. Khuller, U. Vishkin, N.A. Young, Primal-dual parallel approximation technique applied to weighted set and vertex cover, Proceedings of the 3rd Integer Programming and Combinatorial Optimization Conference, Erice, Italy, 1993, pp. 333–341
41.
D. Kim, Z. Zhang, X.Y. Li, W. Wang, W.L. Wu, D.-Z. Du, A better approximation algorithm for computing connected dominating sets in unit ball graphs. IEEE Trans. Mobile Comput. 9, 1108–1118 (2010)CrossRef
42.
P. Koebe, Kontaktprobleme der konformen Abbildung, Brichte über die Verhandlungen der Sächsischen Akademic der Wissenschaften, Leipzig. Math. Phys. Klasse 88, 141–164 (1936)
43.
J. Komolos, M.T. Shing, Probabilistic partitioning algorithms for the rectilinear steiner tree problem. Networks 15, 413–423 (1985)MathSciNetCrossRef
44.
N. Lev-Tov, D. Peleg, Polynomial time approximation schemes for base station coverage with minimum total radii. Comput. Network 47, 489–501 (2005)CrossRefMATH
45.
C. Lund, M. Yannakakis, On the hardness of approximating minimization problems, in Proc. 25th ACM Symp. on Theory of Computing (STOC 1993), San Diego, CA, 1993, pp. 286–293
46.
E. Malesińska, Graph-theoretical models for frequency assignment problems, PhD thesis, Technische Universität Berlin, 1997
47.
M.V. Marathe, H. Breu, H.B. Hunt III, S.S. Ravi, D.J. Rosenkrantz, Simple heuristics for unit disk graphs. Networks 25, 59–68 (1995)MathSciNetCrossRefMATH
48.
M. Min, S.C.-H. Huang, J. Liu, E. Shragowitx, W. Wu, Y. Zhao, Y. Zhao, An approximation scheme for the rectilinear Steiner minimum tree in presence of obstructions, Novel Approaches to Hard Discrete Optimization, Fields Institute Communications Series. Am. Math. Soc. 37, 155–163 (2003)
49.
M. Min, H. Du, X. Jia, C.X. Huang, S.C. Huang, W. Wu, Improving construction for connected dominating set with Steiner tree in wireless sensor networks. J. Global Optim. 35, 111–119 (2006)MathSciNetCrossRefMATH
50.
B. Monien, E. Speckenmeyer, Ramsey numbers and an approximation algorithm for the vertex cover problem. Acta Inform. 22, 115–123 (1985)MathSciNetCrossRefMATH
51.
T. Nieberg, J. Hurink, W. Kern, A robust PTAS for maximum weight independent sets in unit disk graphs, WG 2004, ed. by J. Hromkovič, M. Nagl, B. Westfechtel, LNCS, vol. 3353, 2004, pp. 214–221
52.
T. Nieberg, J. Hurink, A PTAS for the minimum dominating set problem in unit disk graphs, WAOA 2005, ed. by T. Erlebach, G. Persiano, LNCS, vol. 3879, 2006, pp. 296–306
53.
L. Ruan, H. Du, X. Jia, W. Wu, Y. Li, K. Ko, A greedy approximation for minimum connected dominating set. Theor. Comput. Sci. 329, 325–330 (2004)MathSciNetCrossRefMATH
54.
55.
W.D. Smith, D.C. Wormald, Geometric separator theorems and applications, in Proc. 39th IEEE Sympos. Found. Comput. Sci., Palo Alto, California, USA, 1998, pp. 232–243
56.
57.
P. Wan, K.M. Alzoubi, O. Frieder, Distributed construction of connected dominating set in wireless ad hoc networks, in Proc. Infocom’2002, New York, NY, USA, 2002
58.
59.
L.S. Wang, T. Jiang, E.L. Lawler, Approximation algorithms for tree alignment with a given phylogeny. Algorithmica 16, 302–315 (1996)MathSciNetCrossRef
60.
L.S. Wang, T. Jiang, D. Gusfield, A more efficient approximation scheme for tree alignment, in Proceedings 1st International Conference on Computational Biology, New York, NY, USA, 1997, pp. 310–319
61.
A. Wiese, E. Kranakis, Local PTAS for dominating and connected dominating set in location aware unit disk graphs. Approx. Online Algorithm Lect. Note Comput. Sci. 5426, 227–240 (2009)MathSciNetCrossRef
62.
J. Wu, H.L. Li, On calculating connected dominating set for efficient routing in ad hoc wireless networks, in Proceedings of the 3rd ACM International Workshop on Discrete Algorithms and Methods for Mobile Computing and Communications, New York, NY, USA, 1999, pp. 7–14
63.
Z. Zhang, X.F. Gao, W.L. Wu, D.-Z. Du, A PTAS for minimum connected dominating set in 3-dimensional wireless sensor networks. J. Global Optim. 45, 451–458 (2009)MathSciNetCrossRefMATH
64.
Z. Zhang, X.F. Gao, W.L. Wu, PTAS for connected vertex cover in unit disk graphs. Theor. Comput. Sci. 410, 5398–5402 (2009)MathSciNetCrossRefMATH
65.
C. Zong, Shere Packings (Springer, New York, 1999)
66.
F. Zou, X.Y. Li, D.Y. Kim, W.L. Wu, Construction of minimum connected dominating set in 3-dimensional wireless network, in WASA 2008’. Lect. Note Comput. Sci. 5258, 134–140 (2008)CrossRef
Metadaten
Titel
Partition in High Dimensional Spaces
verfasst von
Zhao Zhang
Weili Wu
Copyright-Jahr
2013
Verlag
Springer New York
Buch
Handbook of Combinatorial Optimization

Print ISBN: 978-1-4419-7996-4

Electronic ISBN: 978-1-4419-7997-1

Copyright-Jahr: 2013

DOI
https://doi.org/10.1007/978-1-4419-7997-1_60

Premium Partner

    Bildnachweise