2026-07-25T06:30:00Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:7466 2024-03-06T10:40:32Z ddc:004 open_access

Simple Greedy Algorithms for Fundamental Multidimensional Graph Problems Bilò, Vittorio Caragiannis, Ioannis Fanelli, Angelo Flammini, Michele Monaco, Gianpiero multidimensional graph problems matroids shortest paths Steiner trees arborescences We revisit fundamental problems in undirected and directed graphs, such as the problems of computing spanning trees, shortest paths, steiner trees, and spanning arborescences of minimum cost. We assume that there are d different cost functions associated with the edges of the input graph and seek for solutions to the resulting multidimensional graph problems so that the p-norm of the different costs of the solution is minimized. We present combinatorial algorithms that achieve very good approximations for this objective. The main advantage of our algorithms is their simplicity: they are as simple as classical combinatorial graph algorithms of Dijkstra and Kruskal, or the greedy algorithm for matroids. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Vittorio Bilò and Ioannis Caragiannis and Angelo Fanelli and Michele Flammini and Gianpiero Monaco 2017 Is Part Of LIPIcs, Volume 80, 44th International Colloquium on Automata, Languages, and Programming (ICALP 2017) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.ICALP.2017.125 urn:nbn:de:0030-drops-74669 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2017.125 eng https://creativecommons.org/licenses/by/3.0/legalcode