Efficiently Optimizing for Dendritic Connectivity on Tree-Structured Networks in a Multi-Objective Framework
Open accessAbstract
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.
The claims and statistics of this paper haven’t been checked yet.
Run the check — free, no account needed. It reads the open-access text and checks the sources it cites.
Integrity signals
Registry
Cites
Statistics
Claims the paper makes
The claims and statistics of this paper haven’t been checked yet.
Run the check — free, no account needed. It reads the open-access text and checks the sources it cites.
Claims other papers make about this one
Each is checked against this paper’s own text: does it say what the citing paper says it does?
This approach has been applied in a number of climate change-related fields, including energy and infrastructure planning, industry, land use, and more.
“This approach has been applied in a number of climate change-related fields, including energy and infrastructure planning [38,325,525,635,732,856], industry [122,334], land use [462,809], and more [127,317,539,761].”
From Tackling climate change with machine learning (2023) · cites this paper as [732]
Self-check
Percentages, sums and reported differences re-computed from the paper’s own numbers.
The self-check needs the paper’s full text.
Cites
A fast and elitist multiobjective genetic algorithm: NSGA-II
Deb, K., Pratap, A., Agarwal, S., & Meyarivan, T. (2002) · IEEE Transactions on Evolutionary Computation · doi:10.1109/4235.996017 · Cited by 50,053 · see citing works
Migration of Freshwater Fishes
(2001) · doi:10.1002/9780470999653 · Cited by 1,062 · see citing works
A survey and annotated bibliography of multiobjective combinatorial optimization
Ehrgott, M., & Gandibleux, X. (2000) · OR Spectrum · doi:10.1007/s002910000046 · Cited by 701 · see citing works
Evolutionary multiobjective optimization in water resources: The past, present, and future
Reed, P. M., Hadka, D., Herman, J. D., et al. (2012) · Advances in Water Resources · doi:10.1016/j.advwatres.2012.01.005 · Cited by 559 · see citing works
Finer, M., & Jenkins, C. N. (2012) · PLoS ONE · doi:10.1371/journal.pone.0035126 · Cited by 526 · see citing works
On the approximability of trade-offs and optimal access of Web sources
Papadimitriou, C. H., & Yannakakis, M. (2002) · Annual Symposium on Foundations of Computer Science · doi:10.1109/sfcs.2000.892068 · Cited by 467 · see citing works
A new measure of longitudinal connectivity for stream networks
Côté, D., Kehler, D. G., Bourne, C. M., et al. (2008) · Landscape Ecology · doi:10.1007/s10980-008-9283-y · Cited by 408 · see citing works
Optimal Design of Water Distribution Systems Using Many-Objective Visual Analytics
Fu, G., Kapelan, Z. S., Kasprzyk, J. R., et al. (2012) · Journal of Water Resources Planning and Management · doi:10.1061/(asce)wr.1943-5452.0000311 · Cited by 187 · see citing works
Barthem, R. B., Goulding, M., Leite, R. G., et al. (2017) · Scientific Reports · doi:10.1038/srep41784 · Cited by 163 · see citing works
Migratory Fishes as Material and Process Subsidies in Riverine Ecosystems
Flecker, A. S., McIntyre, P. B., Moore, J. W., & Anderson, J. T. (2010) · Cited by 152 · see citing works
Self-citationMany-objective optimization and visual analytics reveal key trade-offs for London’s water supply
Matrosov, E. S., Huskova, I., Kasprzyk, J. R., et al. (2015) · Journal of Hydrology · doi:10.1016/j.jhydrol.2015.11.003 · Cited by 133 · see citing works
Gomes, C. P. (2009) · The Bridge · Cited by 118 · see citing works
Self-citationNeumann, F. (2006) · European Journal of Operational Research · doi:10.1016/j.ejor.2006.08.005 · Cited by 101 · see citing works
Qian, C., Yu, Y., & Zhou, Z. (2015) · Proceedings of the AAAI Conference on Artificial Intelligence · doi:10.1609/aaai.v29i1.9579 · Cited by 94 · see citing works
Ecosystem-Level Consequences of Migratory Faunal Depletion Caused by Dams
Freeman, M. C., Pringle, C. M., Greathouse, E. A., et al. (2003) · Cited by 93 · see citing works
Multiple criteria decision making for engineering
Wiecek, M. M., Ehrgott, M., Fadel, G., & Figueira, J. R. (2007) · Omega · doi:10.1016/j.omega.2006.10.001 · Cited by 88 · see citing works
A toolkit for optimizing fish passage barrier mitigation actions
King, S., O'Hanley, J., Newbold, L. R., Kemp, P., & Diebel, M. (2017) · Journal of Applied Ecology · doi:10.1111/1365-2664.12706 · Cited by 63 · see citing works
Dam choices: Analyses for multiple needs
Kareiva, P. (2012) · Proceedings of the National Academy of Sciences · doi:10.1073/pnas.1203263109 · Cited by 61 · see citing works
Reed, P. M., & Kollat, J. B. (2013) · Advances in Water Resources · doi:10.1016/j.advwatres.2013.01.011 · Cited by 59 · see citing works
Selection Hyper-heuristics Can Provably Be Helpful in Evolutionary Multi-objective Optimization
Qian, C., Tang, K., & Zhou, Z. (2016) · Lecture notes in computer science · doi:10.1007/978-3-319-45823-6_78 · Cited by 55 · see citing works
Optimal Fish Passage Barrier Removal—Revisited
King, S., & O’Hanley, J. R. (2014) · River Research and Applications · doi:10.1002/rra.2859 · Cited by 48 · see citing works
Sheng, W., Liu, Y., Meng, X., et al. (2012) · Computers & Mathematics with Applications · doi:10.1016/j.camwa.2012.01.063 · Cited by 45 · see citing works
Efficiently Approximating the Pareto Frontier: Hydropower Dam Placement in the Amazon Basin
Wu, X., Gomes-Selman, J. M., Shi, Q., Xue, Y., García‐Villacorta, R., Anderson, E. P., Sethi, S. A., Steinschneider, S., Flecker, A. S., & Gomes, C. P. (2018) · Proceedings of the AAAI Conference on Artificial Intelligence · doi:10.1609/aaai.v32i1.11347 · Cited by 23 · see citing works
Self-citationRounded Dynamic Programming for Tree-Structured Stochastic Network Design
Wu, X., Sheldon, D. R., & Zilberstein, S. (2014) · Proceedings of the AAAI Conference on Artificial Intelligence · doi:10.1609/aaai.v28i1.8761 · Cited by 19 · see citing works
High value of ecological information for river connectivity restoration
Sethi, S. A., O’Hanley, J. R., Gerken, J., et al. (2017) · Landscape Ecology · doi:10.1007/s10980-017-0571-2 · Cited by 18 · see citing works
Self-citationOptimizing Resilience in Large Scale Networks
Wu, X., Sheldon, D. R., & Zilberstein, S. (2016) · Proceedings of the AAAI Conference on Artificial Intelligence · doi:10.1609/aaai.v30i1.9911 · Cited by 15 · see citing works
Stochastic Network Design in Bidirected Trees
Wu, X., Sheldon, D. R., & Zilberstein, S. (2014) · Cited by 14 · see citing works
Analysis of an Algorithm for Identifying Pareto Points in Multi-Dimensional Data Sets
Yukish, M. A., & Simpson, T. (2004) · AIAA/ISSMO Multidisciplinary Analysis and Optimization Conference (MAO) · doi:10.2514/6.2004-4324 · Cited by 14 · see citing works
Introducing Pareto Minimal Correction Subsets
Terra-Neves, M., Lynce, I., & Manquinho, V. M. (2017) · Lecture notes in computer science · doi:10.1007/978-3-319-66263-3_13 · Cited by 12 · see citing works
Boosting Efficiency for Computing the Pareto Frontier on Tree Structured Networks
Gomes-Selman, J. M., Shi, Q., Xue, Y., et al. (2018) · Lecture notes in computer science · doi:10.1007/978-3-319-93031-2_19 · Cited by 7 · see citing works
Self-citation
Flagged first, then by citations
Cited by
Sorted by citations
Tackling climate change with machine learning
Rolnick, D., Donti, P. L., Kaack, L. H., Kochanski, K., Lacoste, A., Sankaran, K., Ross, A. S., Milojevic-Dupont, N., Jaques, N., Waldman-Brown, A., et al. (2023) · ACM Computing Surveys · doi:10.1145/3485128 · Cited by 336 · see citing works
Self-citation
- Authors
- Shi, Q., Gomes-Selman, J. M., García-Villacorta, R., Sethi, S., Flecker, A. S., & Gomes, C. P.
- Affiliations
- Cornell University (US)
- Stanford University (US)
- Department of Ecology and Evolutionary, Biology, Cornell University
- United States Geological Survey (US)
- Venue
- Proceedings of the 1st ACM SIGCAS Conference on Computing and Sustainable Societies
- Publisher
- ACM
- Published
- 2018-06-20
- Pages
- 1-8
- OpenAlex
- W2809361363
- Cited by
- 5
- References
- 30
- Citations by year
- 2023: 1 · 2022: 4
- FWCI
- 0.00
- Type
- conference paper
- Language
- en
- Open access
- bronze
- doi.org
- Locations
- ACM SIGCAS Conference on Computing and Sustainable Societies (COMPASS) (publishedVersion)
- Funders
- Division of Computing and Communication Foundations (1522054)
- Topics
- Physical Sciences › Computer Science › Computational Theory and Mathematics › Complexity and Algorithms in Graphs
- Physical Sciences › Computer Science › Computational Theory and Mathematics › Advanced Multi-Objective Optimization Algorithms
- Physical Sciences › Engineering › Control and Systems Engineering › Optimization and Mathematical Programming
- Keywords
- tree-structured networks, multi-objective optimization, river networks, river fragmentation, hydroelectric dams, Amazon basin, ecosystem service trade-offs, fish migration, river connectivity, dynamic programming, mixed integer programming, approximation algorithms
About these checks
Registry, retraction, Cites and statistics results are computed, not judged, with one exception: a printed reference that no index lists is read once by a model before it counts as a citation error. Claims are extracted by a model and kept only when their quote appears verbatim in the text; each cited source is then checked, with a model’s help, for whether it says what the claim relies on. Those verdicts can be wrong — read the claim’s quote and the cited source before relying on one.
Statistics and arithmetic are recomputed, not judged.
Confidence bands are shown only for fields calibrated on our annotated test set. None is calibrated yet, so no band is shown.
What counts as a claim ›How we measure confidence ›How we check this ›
Are you an author, or do you see a problem with this page? Request a review
