Your hint was very useful. If I understand correctly, when constraint is added, lets say I want to find first K element -- |A|=K --, then the problem is not polynomial any more. Moreover, I am dealing with a large number of elements (> 500K) and not only being polynomial can be useful. I am continuing with: icml-2011.org/papers/506_icmlpaper.pdf Thanks again, and it would be very useful if you can give me more information.