Approximating Freeness under Constraints with Applications