Isotonic Optimization with Fixed Costs
This paper introduces a generalized isotonic optimization framework over an arborescence graph, where each node incurs state-dependent convex costs and a fixed cost upon strict increases. We begin with the special case in which the arborescence is a directed path and develop a dynamic programming (DP) algorithm whose DP stage, excluding preprocessing, has an initial … Read more