We study the problems of picking the media where a good or service is advertised in such a way the cost of placing these advertisements is minimized but, simultaneously, the individuals of some given population segments reach some minimum average advertisement impressions (views); or they reach some minimum probabilities of watching the advertisement at least once; or they reach both. The proposed model lets the publicist explicitly define the dependencies between media audience (i.e., whether viewers of some medium typically watch some other medium; or typically do not watch it; or typically watch it as the rest of the audience). We prove the Log-APX-hardness of these three problems. We present two heuristics to suboptimally solve each of these problems (one greedy and the other one based on genetic algorithms) and compare their performance for several problem instances.