Testing idealness in the filter oracle model

Abdi, AhmadORCID logo; Cornuéjols, Gérard; Guenin, Bertrand; and Tunçel, Levent (2022) Testing idealness in the filter oracle model. Operations Research Letters, 50 (6). 753 - 755. ISSN 0167-6377
Copy

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.
Item Type Article
Keywords ideal clutter,filter oracle,property testing,cuboid,cube-ideal set,minor
Departments Mathematics
DOI 10.1016/j.orl.2022.11.004
Date Deposited 18 Nov 2022 13:03
URI https://researchonline.lse.ac.uk/id/eprint/117366

Explore Further

picture_as_pdf
picture_as_pdf
subject
Published Version
Available under Creative Commons: Attribution 4.0
Download

Atom BibTeX OpenURL ContextObject in Span OpenURL ContextObject Dublin Core MPEG-21 DIDL Data Cite XML EndNote HTML Citation METS MODS RIOXX2 XML Reference Manager Refer ASCII Citation
Export

Downloads