  We consider a monopolist seller facing a single buyer with additive
valuations over n heterogeneous, independent items. It is known that in this
important setting optimal mechanisms may require randomization [HR12], use
menus of infinite size [DDT15], and may be computationally intractable [DDT14].
This has sparked recent interest in finding simple mechanisms that obtain
reasonable approximations to the optimal revenue [HN12, LY13, BILW14]. In this
work we attempt to find the optimal simple mechanism.
  There are many ways to define simple mechanisms. Here we restrict our search
to partition mechanisms, where the seller partitions the items into disjoint
bundles and posts a price for each bundle; the buyer is allowed to buy any
number of bundles.
  We give a PTAS for the problem of finding a revenue-maximizing partition
mechanism, and prove that the problem is strongly NP-hard. En route, we prove
structural properties of near-optimal partition mechanisms which may be of
independent interest: for example, there always exists a near-optimal partition
mechanism that uses only a constant number of non-trivial bundles (i.e. bundles
with more than one item).
