We consider the problem of finding the monotone eccentricity of a vertex v of a polytope. This is the largest number of pivots through the graph of the polytope required to reach an optimal vertex starting from v. In particular, we study a polytope introduced by Frieze and Teng [3] derived from the exact partition problem. This polytope is simple and nearly 0/1, with at most two fractional components per vertex. We show that Frieze and Teng’s result on the complexity of computing lower bounds on diameters of exact partition polytopes can be extended to show that computing monotone eccentricity is also NP-Hard, and in fact \(\textsf {D}^\textsf {P}\) -hard, even on simple polytopes.