If you want to make money online : Register now

Maximal Elements in a Lower Set

, , No Comments
Problem Detail: 

I have a collection of objects, and a feasibility property for sets of objects which is slow to compute. If a set is feasible then so is any subset. For example, it could be whether the set of things will fit into a certain-sized packing crate.

I want to compute all feasible sets (equivalently - all maximal feasible sets), minimizing the number of evaluations of the feasibility property (worst-case or average). Does anyone know of any theoretical work on this?

Bonus question - what if the cost to compute the property is linear (or superlinear) in the size of the set being evaluated?

Asked By : user29970
Answered By : Yuval Filmus

Your problem is equivalent to exact learning of monotone DNFs. This task is equivalent to learning all minterms of a monotone function, whereas you are interested in learning all maxterms of a monotone function, but the two problems are equivalent. (Look these terms up if you are not familiar with them.)

If the only queries you allow are membership queries (test whether a given set is feasible or not) then your problem is rather difficult. Theorem 2 in Angluin's Queries and Concept Learning shows that $2^n-1$ queries are required even if there are only $2n$ objects and $n+1$ minterms. See the paper for other models in which your problem can be solved efficiently.

Best Answer from StackOverflow

Question Source : http://cs.stackexchange.com/questions/64833

3200 people like this

 Download Related Notes/Documents


Post a Comment

Let us know your responses and feedback