Real-world problems are often not fully characterized by a single optimal solution, as they frequently involve multiple competing objectives; it is therefore important to identify the so-called Pareto frontier, which captures solution trade-offs. We propose a fully polynomial-time approximation scheme based on Dynamic Programming (DP) for computing a polynomially succinct curve that approximates the Pareto frontier to within an arbitrarily small epsilon > 0 on tree-structured networks. Given a set of objectives, our approximation scheme runs in time polynomial in the size of the instance and 1/epsilon. We also propose a Mixed Integer Programming (MIP) scheme to approximate the Pareto frontier. The DP and MIP Pareto frontier approaches have complementary strengths and are surprisingly effective. We provide empirical results showing that our methods outperform other approaches in efficiency and accuracy. Our work is motivated by a problem in computational sustainability concerning the proliferation of hydropower dams throughout the Amazon basin. Our goal is to support decision-makers in evaluating impacted ecosystem services on the full scale of the Amazon basin. Our work is general and can be applied to approximate the Pareto frontier of a variety of multiobjective problems on tree-structured networks.

We provide an exact and approximation algorithm based on Dynamic Programming and an approximation algorithm based on Mixed Integer Programming for optimizing for the so-called dendritic connectivity on tree-structured networks in a multi-objective setting. Dendritic connectivity describes the degree of connectedness of a network. We consider different variants of dendritic connectivity to capture both network connectivity with respect to long and short-to-middle distances. Our work is motivated by a problem in computational sustainability concerning the evaluation of trade-offs in ecosystem services due to the proliferation of hydropower dams throughout the Amazon basin. In particular, we consider trade-offs between energy production and river connectivity. River fragmentation can dramatically affect fish migrations and other ecosystem services, such as navigation and transportation. In the context of river networks, different variants of dendritic connectivity are important to characterize the movements of different fish species and human populations. Our approaches are general and can be applied to optimizing for dendritic connectivity for a variety of multi-objective problems on tree-structured networks.