Nothing Special   »   [go: up one dir, main page]
Skip to main content
Springer Nature Link
Log in

Optimal Ordering of Tests with Extreme Dependencies

  • Conference paper
Modelling, Computation and Optimization in Information Systems and Management Sciences

Part of the book series: Advances in Intelligent Systems and Computing ((AISC,volume 359))

Abstract

Optimization of testing strategies has numerous facets. Here we examine the case where tests are one-sided perfect - thus an optimal strategy consists of a sequence of tests, and the remaining problem is to find an optimal (w.r.t. time, or any other resource) ordering of a given set of tests. In prior work, we examined conditions under which statistically independent test sequences can be optimized under precedence constraints. This paper examines conditions under which one can efficiently find an optimal ordering of tests with statistical dependencies. We provide low-order polynomial time algorithms for special cases with non-trivial dependency structures.

This is a preview of subscription content, log in via an institution to check access.

Access this chapter

Log in via an institution

Subscribe and save

Springer+ Basic
$34.99 /Month
  • Get 10 units per month
  • Download Article/Chapter or eBook
  • 1 Unit = 1 Article or 1 Chapter
  • Cancel anytime
Subscribe now

Buy Now

Chapter
USD 29.95
Price excludes VAT (USA)
  • Available as PDF
  • Read on any device
  • Instant download
  • Own it forever
eBook
USD 129.00
Price excludes VAT (USA)
  • Available as PDF
  • Read on any device
  • Instant download
  • Own it forever
Softcover Book
USD 169.99
Price excludes VAT (USA)
  • Compact, lightweight edition
  • Dispatched in 3 to 5 business days
  • Free shipping worldwide - see info

Tax calculation will be finalised at checkout

Purchases are for personal use only

Institutional subscriptions

Preview

Unable to display preview. Download preview PDF.

Unable to display preview. Download preview PDF.

Similar content being viewed by others

References

  1. Berend, D., Brafman, R., Cohen, S., Shimony, S.E., Zucker, S.: Optimal Ordering of Independent Tests with Precedence Constraints. Discrete Applied Mathematics 162, 115–127 (2014)

    Article  MATH  MathSciNet  Google Scholar 

  2. Berend, D., Brafman, R., Cohen, S., Shimony, S.E., Zucker, S.: Optimal Ordering of Statistically Dependent Tests, preprint

    Google Scholar 

  3. Lawler, E.L.: Sequencing Jobs to Minimize total weighted Completion Time. Annals of Discrete Mathematics 2, 75–90 (1978)

    Article  MATH  MathSciNet  Google Scholar 

  4. Monma, C.L., Sidney, J.B.: Sequencing with series-parallel precedence constraints. Mathematics of Operations Research 4(3), 215–224 (1979)

    Article  MATH  MathSciNet  Google Scholar 

  5. Viola, P.A., Jones, M.J.: Rapid object Detection using a Boosted Cascade of Simple Features. CVPR 1, 511–518 (2001)

    Google Scholar 

Download references

Author information

Authors and Affiliations

  1. Departments of Mathematics and Computer Science, Ben-Gurion University, Beer Sheva, Israel

    Daniel Berend

  2. Department of Computer Science, Ben-Gurion University, Beer Sheva, Israel

    Solomon E. Shimony

  3. Orbotech, Yavne, Israel

    Shimon Cohen

  4. Department of Computer Science, Sapir academic College, Shaar Hanegev, Israel

    Shira Zucker

Authors
  1. Daniel Berend
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Shimon Cohen
    View author publications

    You can also search for this author in PubMed Google Scholar

  3. Solomon E. Shimony
    View author publications

    You can also search for this author in PubMed Google Scholar

  4. Shira Zucker
    View author publications

    You can also search for this author in PubMed Google Scholar

Editor information

Editors and Affiliations

  1. Laboratory of Theoretical and Applied Computer Science, University of Lorraine-Metz, Metz, France

    Hoai An Le Thi

  2. Laboratory of Mathematics, National Institute for Applied Sciences-Rouen, Rouen, France

    Tao Pham Dinh

  3. Division of Knowledge Management Systems Institute of Informatics (I-32), Wroclaw University of Technology, Wroclaw, Poland

    Ngoc Thanh Nguyen

Rights and permissions

Reprints and permissions

Copyright information

© 2015 Springer International Publishing Switzerland

About this paper

Cite this paper

Berend, D., Cohen, S., Shimony, S.E., Zucker, S. (2015). Optimal Ordering of Tests with Extreme Dependencies. In: Le Thi, H., Pham Dinh, T., Nguyen, N. (eds) Modelling, Computation and Optimization in Information Systems and Management Sciences. Advances in Intelligent Systems and Computing, vol 359. Springer, Cham. https://doi.org/10.1007/978-3-319-18161-5_8

Download citation

  • DOI: https://doi.org/10.1007/978-3-319-18161-5_8

  • Publisher Name: Springer, Cham

  • Print ISBN: 978-3-319-18160-8

  • Online ISBN: 978-3-319-18161-5

  • eBook Packages: EngineeringEngineering (R0)

Publish with us

Policies and ethics

Search

Navigation