When restricted to cost arrays possessing the sum Monge property, many combinatorial optimization problems with sum objective functions become significantly easier to solve. Examples include the usual sum-objective-function versions of the assignment problem, the transportation problem, the traveling-salesman problem, and several shortest-path problems. Furthermore, the more general algebraic assignment and transportation problems, which are formulated in terms of an ordered commutative semigroup (H, *, {le}), are similarly easier to solve given cost arrays possessing the corresponding algebraic Monge property, which requires that for all i < k and j < {ell}, a[i,j] * a[k,{ell}] {le} a[i,{ell}] * a[k,j]. In this paper, we show that Monge-array results for two sum-of-edge-costs shortest-path problems can likewise be extended to a general algebraic setting, provided the problems` ordered commutative semigroup (H, *, {le}) satisfies one additional restriction. We also show how our algorithms can be modified to solve certain bottleneck shortest-path problems, even though the ordered commutative semigroup ({Re}, max, {le}) naturally associated with bottleneck problems does not satisfy our additional restriction. We also provide improved algorithms for several other bottleneck combinatorial optimization problems whose cost arrays possess the strict bottleneck Monge property. Finally, we show how our bottleneck shortest-path techniques can be used to obtain fast algorithms for a variant of Hirschberg and Larmore`s optimal paragraph formation problem, a processor-allocation problem first formulated by Bokhari, and a special case of the bottleneck traveling-salesman problem.
