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
Bücher
Zeitschriften
Themenseiten
Organisationspsychologie Projektmanagement Marketing Smart Manufacturing
Weitere Formate
Podcasts Webinare Technik Webinare Wirtschaft Kongresse Veranstaltungskalender Awards
Jetzt Einzelzugang starten
Zugang für Unternehmen
Referenzkunden
SLX-Digitalkonferenz: Zukunftswerkstatt 2024

Mehr Umsatz mit Top-Kontakten

Am 7. Mai erfahren Sie, wie Vertriebsteams Leadgenerierung, Leadnurturing und Leadstrategien effizient steuern können.
Erweiterte Suche
Anmelden
nach oben
Journal of Combinatorial Optimization
Erschienen in: Journal of Combinatorial Optimization 2/2014

01.02.2014

An efficient FPRAS type group testing procedure to approximate the number of defectives

verfasst von: Yongxi Cheng, Yinfeng Xu

Erschienen in: Journal of Combinatorial Optimization | Ausgabe 2/2014

Einloggen

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

search-config
loading …

Abstract

In many fault detection problems, we want to detect or identify defective items in a sample set by using the minimum number of tests. Group testing is for the scenario where each test is on a subset of items, and tells whether the subset contains at least one defective item or not. Another practically important problem is to estimate the number of defective items in a sample set. In this paper, we present an efficient FPRAS (fully polynomial-time randomized approximation scheme) type group testing procedure to approximate the number of defective items in a sample set.
Vorheriger Artikel Generalized perfect domination in graphs
Nächster Artikel Improved approximation algorithms for the max-bisection and the disjoint 2-catalog segmentation problems

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 "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

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
Literatur
Alon N, Matias Y, Szegedy M (1999) The space complexity of approximating the frequency moments. J Comput Syst Sci 58(1):137–147 CrossRefMATHMathSciNet
Cheng Y (2011) An efficient randomized group testing procedure to determine the number of defectives. Oper Res Lett 39(5):352–354 MATHMathSciNet
Cormode G, Muthukrishnan S (2005) What’s hot and what’s not: tracking most frequent items dynamically. ACM Trans Database Syst 30(1):249–278 CrossRefMathSciNet
Damaschke P, Sheikh Muhammad A (2010a) Competitive group testing and learning hidden vertex covers with minimum adaptivity. Discrete Math Algorithms Appl 2(3):291–311 CrossRefMATHMathSciNet
Damaschke P, Sheikh Muhammad A (2010b) Bounds for nonadaptive group tests to estimate the amount of defectives. In: Proc 4th international conference on combinatorial optimization and applications. Lecture notes in computer science, vol 6509, pp 117–130 CrossRef
Dorfman R (1943) The detection of defective members of large populations. Ann Math Stat 14:436–440 CrossRef
Du DZ, Hwang FK (2000) Combinatorial group testing and its applications, 2nd edn. World Scientific, Singapore MATH
Li CH (1962) A sequential method for screening experimental variables. J Am Stat Assoc 57:455–477 CrossRefMATH
Sobel M, Groll PA (1959) Group testing to eliminate efficiently all defectives in a binomial sample. Bell Syst Tech J 38:1179–1252 CrossRefMathSciNet
Wein LM, Zenios SA (1996) Pooled testing for hiv screening: capturing the dilution effect. Oper Res 44(4):543–569 CrossRefMATH
Wolf J (1985) Born again group testing: Multiaccess communications. IEEE Trans Inf Theory IT-31:185–191 CrossRef
Metadaten
Titel
An efficient FPRAS type group testing procedure to approximate the number of defectives
verfasst von
Yongxi Cheng
Yinfeng Xu
Publikationsdatum
01.02.2014
Verlag
Springer US
Erschienen in
Journal of Combinatorial Optimization / Ausgabe 2/2014
Print ISSN: 1382-6905
Elektronische ISSN: 1573-2886
DOI
https://doi.org/10.1007/s10878-012-9516-5

Weitere Artikel der Ausgabe 2/2014

Journal of Combinatorial Optimization 2/2014 Zur Ausgabe

OriginalPaper

An improved distributed data aggregation scheduling in wireless sensor networks

OriginalPaper

Sharp bounds of the Zagreb indices of k-trees

OriginalPaper

Generalized perfect domination in graphs

OriginalPaper

A study of search algorithms’ optimization speed

OriginalPaper

Boundary graph classes for some maximum induced subgraph problems

OriginalPaper

Improvements to MCS algorithm for the maximum clique problem