A general approximation for multistage subgraph problems
Autor(en): | Chimani, Markus Troost, Niklas Wiedera, Tilo |
Herausgeber: | Fernandes, C.G. Rajsbaum, S. |
Stichwörter: | Approximation Algorithms; Approximation Framework; Graph theory; Multi-stages; Multistage graph; Multistage Graphs; NP-hard; Optimal solutions; Optimal systems; Optimisations; Optimization; Polynomial approximation; Subgraph Optimization; Subgraph problems; Subgraphs; Vertex cover | Erscheinungsdatum: | 2023 | Herausgeber: | Elsevier B.V. | Journal: | Procedia Computer Science | Volumen: | 223 | Startseite: | 334 – 342 | Zusammenfassung: | Subgraph Problems are optimization problems on graphs where a solution is a subgraph that satisfies some property and optimizes some measure. Examples include shortest path, minimum cut, maximum matching, or vertex cover. In reality, however, one often deals with time-dependent data, i.e., the input graph may change over time and we need to adapt our solution accordingly. We are interested in guaranteeing optimal solutions after each graph change while retaining as much of the previous solution as possible. Even if the subgraph problem itself is polynomial-time computable, this multistage variant turns out to be NP-hard in most cases. We present an algorithmic framework that - for any subgraph problem of a certain type - guarantees an optimal solution for each point in time and provides an approximation guarantee for the similarity between subsequent solutions. We show that the class of applicable multistage subgraph problems is very rich and that proving membership to this class is mostly straightforward. As examples, we explicitly state these proofs and obtain corresponding approximation algorithms for the natural multistage versions of Shortest s-t-Path, Perfect Matching, Minimum s-t-Cut - and further classical problems on bipartite or planar graphs, namely Maximum Cut, Vertex Cover, and Independent Set. We also report that all these problems are already NP-hard on only two stages. © 2023 Elsevier B.V.. All rights reserved. |
Beschreibung: | Cited by: 0; Conference name: 12th Latin-American Algorithms, Graphs and Optimization Symposium, LAGOS 2023; Conference date: 18 September 2023 through 22 September 2023; Conference code: 193000; All Open Access, Gold Open Access |
ISSN: | 1877-0509 | DOI: | 10.1016/j.procs.2023.08.245 | Externe URL: | https://www.scopus.com/inward/record.uri?eid=2-s2.0-85174402477&doi=10.1016%2fj.procs.2023.08.245&partnerID=40&md5=a86a5040eb1fae2d57aab94773693da6 |
Zur Langanzeige
Seitenaufrufe
2
Letzte Woche
1
1
Letzter Monat
1
1
geprüft am 03.06.2024