Optimal search with positive switch cost is NP-hard

DOI10.1016/0020-0190(85)90108-5zbMath0577.90041OpenAlexW2084476663MaRDI QIDQ1065706

Ingo Wegener

Publication date: 1985

Published in: Information Processing Letters (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/0020-0190(85)90108-5

zbMATH Keywords

optimal strategyNP-hardnessoptimal searchpositive switch cost

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Search theory (90B40)

Related Items

Complexity of searching an immobile hider in a graph, Online failure diagnosis in interdependent networks, A search problem on a bipartite network, Optimal discrete search with imperfect specificity

Cites Work

• Unnamed Item
• Unnamed Item
• The Euclidean traveling salesman problem is NP-complete
• Optimal Search Strategies
• Discrete Sequential Search with Positive Switch Cost
• Discrete Dynamic Programming
• Optimal Search for Detecting a Hidden Object