  We focus on a generalization of the classic Minisum approval voting rule,
introduced by Barrot and Lang (2016), and referred to as Conditional Minisum
(CMS), for multi-issue elections with preferential dependencies. Under this
rule, voters are allowed to declare dependencies between different issues, but
the price we have to pay for this higher level of expressiveness is that we end
up with a computationally hard rule. Motivated by this, we first focus on
finding special cases that admit efficient algorithms for CMS. Our main result
in this direction is that we identify the condition of bounded treewidth (of an
appropriate graph, emerging from the provided ballots) as the necessary and
sufficient condition for exact polynomial algorithms, under common complexity
assumptions. We then move to the design of approximation algorithms. For the
(still hard) case of binary issues, we identify natural restrictions on the
voters' ballots, under which we provide the first multiplicative approximation
algorithms for the problem. The restrictions involve upper bounds on the number
of dependencies an issue can have on the others and on the number of
alternatives per issue that a voter can approve. Finally, we also investigate
the complexity of problems related to the strategic control of conditional
approval elections by adding or deleting either voters or alternatives and we
show that in most variants of these problems, CMS is computationally resistant
against control. Overall, we conclude that CMS can be viewed as a solution that
achieves a satisfactory tradeoff between expressiveness and computational
efficiency, when we have a limited number of dependencies among issues, while
at the same time exhibiting sufficient resistance to control.
