IT Consultant, 2F 2000 Kft., Hegyalja út 5., 1016 Budapest, Hungary
Abstract:
In this paper we consider the worst-case adaptive complexity of the search problem
, where
is also the set of independent sets of a matroid over S. We give a formula for the number of questions needed and an algorithm to find the optimal search algorithm for any matroid. This algorithm uses only O(|S|3) steps (i.e. questions to the independence oracle). This is also the length of Edmonds’ partitioning algorithm for matroids, which does not seem to be avoidable.