Skip to main content
Disciplines
Automotive Business IT + Informatics Construction + Real Estate Electrical Engineering + Electronics Energy + Sustainability Insurance + Risk Finance + Banking Management + Leadership Marketing + Sales Mechanical Engineering + Materials
Events
DE
EN
Books
Journals
Topic Page
Marketing
Start single access now
Access for companies
EXTENDED SEARCH
Log in
Top
Published in:
Tolerance-Based vs. Cost-Based Branching for the Asymmetric Capacitated Vehicle Routing Problem Read chapter Read first chapter

2013 | OriginalPaper | Chapter

Sensor Cover and Double Partition

Authors : Lidong Wu, Weili Wu, Zaixin Lu, Yuqing Zhu, Ding-Zhu Du

Published in: Models, Algorithms, and Technologies for Network Analysis

Publisher: Springer New York

Log in

Activate our intelligent search to find suitable subject content or patents.

search-config
loading …

Abstract

The minimum sensor cover is an important optimization problem in wireless sensor networks, which can be seen as a special case of the minimum set cover problem. The minimum set cover problem is a well-known problem in combinatorial optimization, which has no polynomial-time (ρlnδ)-approximation for 0<ρ<1 unless NP⊆DTIME(n O(loglogn)) where δ is the maximum cardinality of a subset in the input collection. However, the minimum sensor cover problem has polynomial-time constant-approximations because this special case has a geometric structure. The design technique, called partition, is employed to take the advantage of this geometric structure. Especially, the double partition plays an important role. In this article, we would like to give an exploratory essay for the double partition technique together with research progress on approximations for the minimum sensor cover problem.

Dont have a licence yet? Then find out more about our products and how to get one now:

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!

inform now

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!

inform now

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!

inform now
previous chapter Comparative Analysis of the BRIC Countries Stock Markets Using Network Approach
Literature
1.
Ambühl, C., Erlebach, T., Mihalák, M., Nunkesser, M.: Constant-approximation for minimum-weight (connected) dominating sets in unit disk graphs. In: Proceedings of the 9th International Workshop on Approximation Algorithms for Combinatorial Optimization (APPROX 2006). LNCS, vol. 4110, pp. 3–14. Springer, Berlin (2006) CrossRef
2.
Baker, B.S.: Approximation algorithms for NP-complete problems on planar graphs. In: Proc. FOCS, pp. 265–273 (1983)
3.
Boginski, V.L., Commander, C.W., Pardalos, P.M., Ye, Y. (eds.): Sensors: Theory, Algorithms, and Applications. Springer, Berlin (2012)
4.
Cardei, M., Thai, M., Li, Y., Wu, W.: Energy-efficient target coverage in wireless sensor networks. In: IEEE INFOCOM, pp. 1976–1984 (2005)
5.
Dai, D., Yu, C.: A (5+ε)-approximation algorithm for minimum weighted dominating set in unit disk graph. Theor. Comput. Sci. 410, 756–765 (2009) MathSciNetCrossRefMATH
6.
Ding, L., Wu, W., Willson, J.K., Wu, L., Lu, Z., Lee, W.: Constant-approximation for target coverage problem in wireless sensor networks. In: Proc. of the 31st Annual Joint Conf. of IEEE Communication and Computer Society (INFOCOM) (2012)
7.
Du, D.-Z., Ko, K.-I., Hu, X.: Design and Analysis of Approximation Algorithms, pp. 142–157. Springer, Berlin (2012) CrossRefMATH
8.
Du, D.-Z., Wan, P.: Connected Dominating Set: Theory and Applications. Springer, Berlin (2012)
9.
Du, H., Wu, W., Shan, S., Kim, D., Lee, W.: Constructing weakly connected dominating set for secure clustering in distributed sensor network. J. Comb. Optim. 23, 301–307 (2012) MathSciNetCrossRefMATH
10.
Erlebach, T., Mihalak, M.: A (4+ε)-approximation for the minimum-weight dominating set problem in unit disk graphs. In: WAOA 2009, pp. 135–146 (2009)
11.
Gao, X., Huang, Y., Zhang, Z., Wu, W.: (6+ε)-approximation for minimum weight dominating set in unit disk graphs. In: Proceedings of the 14th Annual International Computing and Combinatorics Conference (COCOON 2008). LNCS, vol. 5092, pp. 551–557. Springer, Berlin (2008)
12.
Garg, N., Könemann, J.: Faster and simpler algorithms for multicommodity flows and other fractional packing problems. In: Proc. 39th Annual Symposium on the Foundations of Computer Science, pp. 300–309 (1998)
13.
Hochbaum, D.S., Maass, W.: Approximation schemes for covering and packing problems in image processing and VLSI. J. ACM 32, 130–136 (1985) MathSciNetCrossRefMATH
14.
Huang, Y., Gao, X., Zhang, Z., Wu, W.: A better constant-factor approximation for weighted dominating set in unit disk graph. J. Comb. Optim. 18, 174–194 (2009) MathSciNetCrossRef
15.
Sorokin, A., Boyko, N., Boginski, V., Uryasev, S., Pardalos, P.: Mathematical programming techniques for sensor networks. Algorithms 2, 565–581 (2009) CrossRef
16.
Wang, C., Willson, J., Park, M.A., Farago, A., Wu, W.: On dual power assignment optimization for biconnectivity. J. Comb. Optim. 19, 174–183 (2010) MathSciNetCrossRefMATH
17.
Willson, J.K., Ding, L., Wu, W., Wu, L., Lu, Z., Lee, W.: A better constant-approximation for coverage problem in wireless sensor networks. Preprint
18.
19.
Yang, Y., Cardei, M.: Adaptive energy efficient sensor scheduling for wireless sensor networks. Optim. Lett. 4(3), 359–369 (2010) CrossRef
20.
Zhang, H., Hou, J.C.: Maintaining sensing coverage and connectivity in large sensor networks. Ad Hoc Sens. Wirel. Netw. 1, 89–124 (2005)
21.
Zhang, Y., Li, W.: Modeling and energy consumption evaluation of a stochastic wireless sensor networks. Preprint (2011)
22.
Zou, F., Li, X., Gao, S., Wu, W.: Node-weighted Steiner tree approximation in unit disk graphs. J. Comb. Optim. 18, 342–349 (2009) MathSciNetCrossRefMATH
23.
Zou, F., Wang, Y., Xu, X., Du, H., Li, X., Wan, P., Wu, W.: New approximations for weighted dominating sets and connected dominating sets in unit disk graphs. Theor. Comput. Sci. 412(3), 198–208 (2011) MathSciNetCrossRefMATH
Metadata
Title
Sensor Cover and Double Partition
Authors
Lidong Wu
Weili Wu
Zaixin Lu
Yuqing Zhu
Ding-Zhu Du
Copyright Year
2013
Publisher
Springer New York
Book
Models, Algorithms, and Technologies for Network Analysis

Print ISBN: 978-1-4614-8587-2

Electronic ISBN: 978-1-4614-8588-9

Copyright Year: 2013

DOI
https://doi.org/10.1007/978-1-4614-8588-9_13