Monotone Integer problems (IPM) are those formulated as integer programming with constraints that have at most two variables, x-variables, appearing with opposite sign coefficients, and a third variable, z-variable, that can appear in one constraint only. All IPMs are solved as a minimum s,t-cut on a respective graph.
One use of IPM is for 2-approximations for any NP-hard minimization problem formulated with two variables per inequality. The 2-approximation algorithm is attained with one min-cut procedure, resulting from a transformation to an IPM.
Recently, we introduced the breakpoints algorithm for "budgeted IPM"s which are  NP-hard problems formulated as IPM plus a budget constraint. These include the quadratic knapsack, facility dispersion and the text summarization problems. For these, the breakpoints algorithm that relaxes the budget constraint, delivers high quality solutions in very fast run times. To attain the breakpoints, the parametric cut algorithm generates the "concave envelope" (convex for minimization) that provides a solution to the relaxation for ALL values of the Lagrange multiplier.  The breakpoints in this piecewise linear function correspond to optimal solutions that are nested. The breakpoints algorithm utilizes the solutions at breakpoints close to the budget, to generate a high quality feasible solution to the problem and considerably faster than any other algorithm known for these problems.
For IPM ratio problems, including the densest subgraph problem, we introduce the Incremental Parametric Cut algorithm, that solves monotone ratio problems in the complexity of a single min-cut procedure, based on the insights derived from the concave envelope of the breakpoints. This algorithm is efficient not only in theory but in practice as well. For large scale instances of the densest subgraph problems, it is orders of magnitude faster than recent leading methods that are based on heuristics, and also significantly faster than the equally-efficient, in theory, parametric cut algorithm.