scientific article; zbMATH DE number 19871

MaRDI QIDQ3979382zbMATH OpenFDO

Authors D. Einav, M. R. Fehling

Publication date 26 June 1992

zbMATH Keywords

\(NP\)-completeoptimal strategy

Mathematics Subject Classification ID

Theory of languages and software systems (knowledge-based systems, expert systems, etc.) for artificial intelligence (68T35)

Review text

[For the entire collection see Zbl 0741.68004.] The authors formulate the problem of finding a solution at minimal cost if several methods are available and the time needed to made a choice among methods also is a cost. They show that the problem of computing an optimal strategy is \(NP\)-complete. They outline a procedure that works in pseudopolynomial time.

Recommendations

• Optimal search with positive switch cost is NP-hard
• scientific article; zbMATH DE number 3850820
• scientific article; zbMATH DE number 431475
• Scheduling of resource tasks
• Optimal sequential backup strategy under constrained resources

Cited in

(2)

• Deliberation scheduling for problem solving in time-constrained environments
• Monitoring and control of anytime algorithms: A dynamic programming approach

This page was built for publication:

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3979382)