Placing Green Bridges Optimally, with Habitats Inducing Cycles
Authors: Maike Herkenrath, Till Fluschnik, Francesco Grothe, Leon Kellerhals
IJCAI 2022 | Conference PDF | Archive PDF | Plain Text | LLM Run Details
| Reproducibility Variable | Result | LLM Response |
|---|---|---|
| Research Type | Experimental | We study this problem from a theoretical (algorithms and complexity) and an experimental perspective, while focusing on the case where habitats induce cycles. We prove that the NP-hardness persists in this case even if the graph structure is restricted. If the habitats additionally induce faces in plane graphs however, the problem becomes efficiently solvable. In our empirical evaluation we compare this algorithm as well as ILP formulations for more general variants and an approximation algorithm with another. Our evaluation underlines that each specialization is beneficial in terms of running time, whereas the approximation provides highly competitive solutions in practice. |
| Researcher Affiliation | Academia | Maike Herkenrath , Till Fluschnik , Francesco Grothe and Leon Kellerhals Technische Universität Berlin, Faculty IV, Algorithmics and Computational Complexity, Germany {till.fluschnik, leon.kellerhals}@tu-berlin.de, {herkenrath, f.grothe}@campus.tu-berlin.de |
| Pseudocode | No | The paper describes algorithms and mathematical formulations (e.g., ILP formulation) but does not provide pseudocode or a clearly labeled algorithm block. |
| Open Source Code | Yes | All material to reproduce the results is available online.3 |
| Open Datasets | No | We used data freely available by Open Street Maps (OSM). The paper describes how they generated their experimental instances from OSM data, but does not provide a link or specific citation for the generated datasets themselves. |
| Dataset Splits | No | The paper describes generating different types of instances (face, cycle, walk) and varying parameters (r, q) to create 5 instances for each configuration, but it does not specify explicit training, validation, or test dataset splits. |
| Hardware Specification | Yes | We compared the implementations on machines equipped with an Intel Xeon W-2125 CPU and 256GB of RAM running Ubuntu 18.04. |
| Software Dependencies | Yes | The habitat graph generation is implemented in Python 3. The matching is computed using Kolmogorov s [Kolmogorov, 2009] C++ implementation of the Blossom V algorithm. For the cycle instances generated the habitat graph in Python 3 and used Gurobi 9.5.0 to solve ILP formulation (1). |
| Experiment Setup | Yes | For each instance type, for each graph above, for each r {50, 100, 150, 200}, for each q {5, 7, . . . , 13} in the case of cycle and walk instances, we generated 5 instances. [...] For the ILP-based solvers, we set a time limit of 30s for the solving time (not the build time). |