Testing idealness in the filter oracle model
Abdi, A.
, Cornuéjols, G., Guenin, B. & Tunçel, L.
(2022).
Testing idealness in the filter oracle model.
Operations Research Letters,
50(6), 753 - 755.
https://doi.org/10.1016/j.orl.2022.11.004
, Cornuéjols, G., Guenin, B. & Tunçel, L.
(2022).
Testing idealness in the filter oracle model.
Operations Research Letters,
50(6), 753 - 755.
https://doi.org/10.1016/j.orl.2022.11.004
A filter oracle for a clutter consists of a finite set V and an oracle which, given any set X ⊆ V , decides in unit time whether X contains a member of the clutter. Let A2n be an algorithm that, given any clutter C over 2n elements via a filter oracle, decides whether C is ideal. We prove that in the worst case, A2n makes at least 2n−1 calls to the filter oracle. Our proof uses the theory of cuboids.
