Logarithmic inapproximability results for the minimum shortest path routing conflict problem
| dc.contributor.author | Bley, Andreas | |
| dc.date.accessioned | 2021-12-17T10:08:15Z | |
| dc.date.available | 2021-12-17T10:08:15Z | |
| dc.date.issued | 2009-07-01 | |
| dc.description.abstract | Nowadays most data networks use shortest path protocols such as OSPF or IS-IS to route traffic. Given administrative routing lengths for the links of a network, all data packets are sent along shortest paths with respect to these lengths from their source to their destination. One of the most fundamental problems in planning shortest path networks is to decide whether a given set S of routing paths forms a valid routing and, if this is not the case, to find a small subset R of paths that cannot occur together in any valid routing. In this paper we show that it is NP-hard to approximate the minimal size or the minimal weight of a shortest path conflict $R\subseteq S$ by a factor less than $c\log |S|$ for some $c>0$. | en |
| dc.identifier.issn | 2197-8085 | |
| dc.identifier.uri | https://depositonce.tu-berlin.de/handle/11303/15656 | |
| dc.identifier.uri | http://dx.doi.org/10.14279/depositonce-14429 | |
| dc.language.iso | en | en |
| dc.rights.uri | http://rightsstatements.org/vocab/InC/1.0/ | en |
| dc.subject.ddc | 510 Mathematik | en |
| dc.subject.other | shortest path routing | en |
| dc.subject.other | computational complexity | en |
| dc.title | Logarithmic inapproximability results for the minimum shortest path routing conflict problem | en |
| dc.type | Research Paper | en |
| dc.type.version | submittedVersion | en |
| tub.accessrights.dnb | free | en |
| tub.affiliation | Fak. 2 Mathematik und Naturwissenschaften::Inst. Mathematik | de |
| tub.affiliation.faculty | Fak. 2 Mathematik und Naturwissenschaften | de |
| tub.affiliation.institute | Inst. Mathematik | de |
| tub.publisher.universityorinstitution | Technische Universität Berlin | en |
| tub.series.issuenumber | 2009, 25 | en |
| tub.series.name | Preprint-Reihe des Instituts für Mathematik, Technische Universität Berlin | en |
| tub.subject.msc2000 | 90C60 Abstract computational complexity for mathematical programming problems | en |
| tub.subject.msc2000 | 90B18 Communication networks | en |
Files
Original bundle
1 - 1 of 1