Submodular learning and covering with response-dependent costs

DOI10.1016/j.tcs.2017.12.033zbMath1398.68456arXiv1602.07120OpenAlexW3023755868MaRDI QIDQ1663646

Sivan Sabato

Publication date: 22 August 2018

Published in: Theoretical Computer Science, Lecture Notes in Computer Science (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/1602.07120

zbMATH Keywords

submodular functionsinteractive learningoutcome costs

Mathematics Subject Classification ID

Learning and adaptive systems in artificial intelligence (68T05) Approximation methods and heuristics in mathematical programming (90C59) Problem solving in the context of artificial intelligence (heuristics, search strategies, etc.) (68T20)

Cites Work

• Unnamed Item
• Unnamed Item
• Submodular functions and electrical networks
• An analysis of the greedy algorithm for the submodular set covering problem
• Approximating decision trees with value dependent testing costs
• A threshold of ln n for approximating set cover
• Trading off Worst and Expected Cost in Decision Tree Problems
• An analysis of approximations for maximizing submodular set functions—I