394
eng
reportzib
0
1999-03-03
1999-03-03
--
Euler is Standing in Line
In this paper we study algorithms for ``Dial-a-Ride'' transportation problems. In the basic version of the problem we are given transportation jobs between the vertices of a graph and the goal is to find a shortest transportation that serves all the jobs. This problem is known to be NP-hard even on trees. We consider the extension when precedence relations between the jobs with the same source are given. Our results include a polynomial time algorithm on paths and an approximation algorithm on general graphs with a performance of~$9/4$. For trees we improve the performance to~$5/3$.
SC-99-06
395
urn:nbn:de:0297-zib-3947
Appeared in: Discrete Appl. Math. 113 (2001) 87-107. A prel. vers. appeared in: Proc. of the 25nd Intern. Workshop on Graph-Theoretic Concepts in Computer Science (WG'99), Lecture Notes in Computer Science, vol. 1665, Springer (1999) 42-54
Dietrich Hauptmeier
Sven O. Krumke
Jörg Rambau
Hans-Christoph Wirth.
ZIB-Report
SC-99-06
eng
uncontrolled
NP-completeness
eng
uncontrolled
polynomial-time approximation algorithms
eng
uncontrolled
stacker-crane problem
eng
uncontrolled
vehicle routing
eng
uncontrolled
elevator system
eng
uncontrolled
Eulerian Cycle
Informatik, Informationswissenschaft, allgemeine Werke
Modes of computation (nondeterministic, parallel, interactive, probabilistic, etc.) [See also 68Q85]
Analysis of algorithms and problem complexity [See also 68W40]
ZIB Allgemein
ONLINE-PLANNING
https://opus4.kobv.de/opus4-zib/files/394/SC-99-06.ps
https://opus4.kobv.de/opus4-zib/files/394/SC-99-06.pdf
578
eng
reportzib
0
2000-03-24
2000-03-24
--
Budget Constrained Minimum Cost Connected Medians
Several practical instances of network design problems require the network to satisfy multiple constraints. In this paper, we address the \emph{Budget Constrained Connected Median Problem}: We are given an undirected graph $G = (V,E)$ with two different edge-weight functions $c$ (modeling the construction or communication cost) and $d$ (modeling the service distance), and a bound~$B$ on the total service distance. The goal is to find a subtree~$T$ of $G$ with minimum $c$-cost $c(T)$ subject to the constraint that the sum of the service distances of all the remaining nodes $v \in V\setminus T$ to their closest neighbor in~$T$ does not exceed the specified budget~$B$. This problem has applications in optical network design and the efficient maintenance of distributed databases. We formulate this problem as bicriteria network design problem, and present bicriteria approximation algorithms. We also prove lower bounds on the approximability of the problem that demonstrate that our performance ratios are close to best possible
00-10
579
urn:nbn:de:0297-zib-5783
Appeared in: Proceedings of the 26th International Workshop on Graph-Theoretic Concepts in Computer Science, Konstanz, Germany, Vol 1928 of Lecture Notes in Computer Science, Springer Jun 2000, 267-278
Goran Konjevod
Sven O. Krumke
Madhav Marathe
ZIB-Report
00-10
eng
uncontrolled
NP-hardness
eng
uncontrolled
Approximation Algorithms
eng
uncontrolled
Network
Informatik, Informationswissenschaft, allgemeine Werke
Complexity classes (hierarchies, relations among complexity classes, etc.) [See also 03D15, 68Q17, 68Q19]
Analysis of algorithms and problem complexity [See also 68W40]
Graph theory (including graph drawing) [See also 05Cxx, 90B10, 90B35, 90C35]
ZIB Allgemein
https://opus4.kobv.de/opus4-zib/files/578/ZR-00-10.ps
https://opus4.kobv.de/opus4-zib/files/578/ZR-00-10.pdf
363
eng
reportzib
0
1998-07-10
1998-07-10
--
On the Complexity of Vertex-Disjoint Length-Restricted Path Problems
Let $G=(V,E)$ be a simple graph and $s$ and $t$ be two distinct vertices of $G$. A path in $G$ is called $\ell$-bounded for some $\ell\in\mathbb{N}$, if it does not contain more than $\ell$ edges. We study the computational complexity of approximating the optimum value for two optimization problems of finding sets of vertex-disjoint $\ell$-bounded $s,t$-paths in $G$. First, we show that computing the maximum number of vertex-disjoint $\ell$-bounded $s,t$-paths is $\mathcal{AP\kern-1pt X}$--complete for any fixed length bound $\ell\geq 5$. Second, for a given number $k\in\mathbb{N}$, $1\leq k \leq |V|-1$, and non-negative weights on the edges of $G$, the problem of finding $k$ vertex-disjoint $\ell$-bounded $s,t$-paths with minimal total weight is proven to be $\mathcal{NPO}$--complete for any length bound $\ell\geq 5$. Furthermore, we show that, even if $G$ is complete, it is $\mathcal{NP}$--complete to approximate the optimal solution value of this problem within a factor of $2^{\langle\phi\rangle^\epsilon}$ for any constant $0<\epsilon<1$, where $\langle\phi\rangle$ denotes the encoding size of the given problem instance $\phi$. We prove that these results are tight in the sense that for lengths $\ell\leq 4$ both problems are polynomially solvable, assuming that the weights satisfy a generalized triangle inequality in the weighted problem. All results presented also hold for directed and non-simple graphs. For the analogous problems where the path length restriction is replaced by the condition that all paths must have length equal to $\ell$ or where vertex-disjointness is replaced by edge-disjointness we obtain similar results.
SC-98-20
364
urn:nbn:de:0297-zib-3639
Appeared in: Computational Complexity 12 (2004) 131-149
Andreas Bley
ZIB-Report
SC-98-20
eng
uncontrolled
disjoint paths
eng
uncontrolled
length bounded paths
eng
uncontrolled
approximation
eng
uncontrolled
reducibility
eng
uncontrolled
completeness
Informatik, Informationswissenschaft, allgemeine Werke
Paths and cycles [See also 90B10]
Connectivity
Analysis of algorithms and problem complexity [See also 68W40]
Combinatorial optimization
ZIB Allgemein
https://opus4.kobv.de/opus4-zib/files/363/SC-98-20.ps
https://opus4.kobv.de/opus4-zib/files/363/SC-98-20.pdf
621
eng
reportzib
0
2000-12-19
2000-12-19
--
An Approximation Algorithm for the Non-Preemptive Capacitated Dial-a-Ride Problem
In the Capacitated Dial-a-Ride Problem (CDARP) we are given a transportation network and a finite set of transportation jobs. Each job specifies the source and target location which are both part of the network. A server which can carry at most $C$~objects at a time can move on the transportation network in order to process the transportation requests. The problem CDARP consists of finding a shortest transportation for the jobs starting and ending at a designated start location. In this paper we are concerned with the restriction of CDARP to graphs which are simple paths. This setting arises for instance when modelling applications in elevator transportation systems. It is known that even for this restricted class of graphs CDARP is NP-hard to solve. We provide a polynomial time approximation algorithm that finds a transportion of length at most thrice the length of the optimal transportation.
00-53
622
urn:nbn:de:0297-zib-6217
Sven O. Krumke
Jörg Rambau
Steffen Weider
ZIB-Report
00-53
eng
uncontrolled
NP-completeness
eng
uncontrolled
polynomial-time approximation algorithms
eng
uncontrolled
stacker-crane problem
eng
uncontrolled
vehicle
Informatik, Informationswissenschaft, allgemeine Werke
Modes of computation (nondeterministic, parallel, interactive, probabilistic, etc.) [See also 68Q85]
Analysis of algorithms and problem complexity [See also 68W40]
ZIB Allgemein
Weider, Steffen
https://opus4.kobv.de/opus4-zib/files/621/ZR-00-53.ps
https://opus4.kobv.de/opus4-zib/files/621/ZR-00-53.pdf
1127
eng
reportzib
0
2009-05-06
2009-05-06
--
On the Hardness of Finding Small Shortest Path Routing Conflicts
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 of routing paths forms a valid routing and, if this is not the case, to find a small subset of the given paths that cannot be shortest paths simultaneously for any routing lengths. In this paper we show that it is NP-hard to approximate the size of the smallest shortest path conflict by a factor less than 7/6.
09-15
1438-0064
1176
urn:nbn:de:0297-zib-11276
Appeared in: Proceedings of 4th International Network Optimization Conference (INOC2009)
Andreas Bley
unknown unknown
ZIB-Report
09-15
eng
uncontrolled
shortest path routing
eng
uncontrolled
computational complexity
Mathematik
Analysis of algorithms and problem complexity [See also 68W40]
Communication networks [See also 68M10, 94A05]
Combinatorial optimization
Abstract computational complexity for mathematical programming problems [See also 68Q25]
Mathematical Optimization
https://opus4.kobv.de/opus4-zib/files/1127/ZR_09_15.pdf
https://opus4.kobv.de/opus4-zib/files/1127/ZR_09_15.ps
1105
eng
reportzib
Warsaw University of Technology
0
2008-12-18
2008-12-18
--
On the complexity of column generation in survivable network design with path-based survivability mechanisms
This survey concerns optimization problems arising in the design of survivable communication networks. It turns out that such problems can be modeled in a natural way as non-compact linear programming formulations based on multicommodity flow network models. These non-compact formulations involve an exponential number of path flow variables, and therefore require column generation to be solved to optimality. We consider several path-based survivability mechanisms and present results, both known and new, on the complexity of the corresponding column generation problems (called the pricing problems). We discuss results for the case of the single link (or node) failures scenarios, and extend the considerations to multiple link failures. Further, we classify the design problems corresponding to different survivability mechanisms according to the structure of their pricing problem. Finally, we show that almost all encountered pricing problems are hard to solve for scenarios admitting multiple failures.
08-51
1438-0064
1146
urn:nbn:de:0297-zib-11058
Sebastian Orlowski
unknown unknown
Michal Pióro
ZIB-Report
08-51
deu
uncontrolled
Netzplanung
deu
uncontrolled
Dimensionierung
deu
uncontrolled
Spaltengenerierung
deu
uncontrolled
Mehrfachausfälle
eng
uncontrolled
survivable network design
eng
uncontrolled
routing
eng
uncontrolled
column generation
eng
uncontrolled
pricing
eng
uncontrolled
complexity
Mathematik
Network design and communication [See also 68R10, 90B18]
Analysis of algorithms and problem complexity [See also 68W40]
Special problems of linear programming (transportation, multi-index, etc.)
Programming involving graphs or networks [See also 90C27]
Mathematical Optimization
https://opus4.kobv.de/opus4-zib/files/1105/ZR_08_51.pdf
https://opus4.kobv.de/opus4-zib/files/1105/ZR_08_51.ps
691
eng
reportzib
0
2002-05-07
2002-05-07
--
Budgeted Maximal Graph Coverage
An instance of the \emph{maximum coverage} problem is given by a set of weighted ground elements and a cost weighted family of subsets of the ground element set. The goal is to select a subfamily of total cost of at most that of a given budget maximizing the weight of the covered elements. We formulate the problem on graphs: In this situation the set of ground elements is specified by the nodes of a graph, while the family of covering sets is restricted to connected subgraphs. We show that on general graphs the problem is polynomial time solvable if restricted to sets of size at most~$2$, but becomes NP-hard if sets of size~$3$ are permitted. On trees, we prove polynomial time solvability if each node appears in a fixed number of sets. In contrast, if vertices are allowed to appear an unbounded number of times, the problem is NP-hard even on stars. We finally give polynomial time algorithms for special cases where the subgraphs form paths and the host graph is a line, a cycle or a star.
02-24
692
urn:nbn:de:0297-zib-6918
Appeared in: Graph-Theoretic Concepts in Computer Science. 28th Intern. Workshop, WG 2002, Cesky Krumlov, Czech Republic, June 13-15, 2002; revised papers. L. Kucera (ed.) Springer 2002. LNCS 2573. Pp. 321-332
Sven O. Krumke
Madhav V. Marathe
Diana Poensgen
Sekharipuram S. Ravi
Hans-Christoph Wirth
ZIB-Report
02-24
eng
uncontrolled
budgeted maximum coverage
eng
uncontrolled
approximation algorithm
eng
uncontrolled
dynamic programming
Informatik, Informationswissenschaft, allgemeine Werke
Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) [See also 68Q15]
Analysis of algorithms and problem complexity [See also 68W40]
Combinatorial optimization
ZIB Allgemein
https://opus4.kobv.de/opus4-zib/files/691/ZR-02-24.ps
https://opus4.kobv.de/opus4-zib/files/691/ZR-02-24.pdf
692
eng
habilitation
0
2002-06-18
2002-06-18
--
Online Optimization: Competitive Analysis and Beyond
Traditional optimization techniques assume, in general, knowledge of all data of a problem instance. There are many cases in practice, however, where decisions have to be made before complete information about the data is available. In fact, it may be necessary to produce a part of the problem solution as soon as a new piece of information becomes known. This is called an \emph{online situation}, and an algorithm is termed \emph{online}, if it makes a decision (computes a partial solution) whenever a new piece of data requests an action. \emph{Competitive analysis} has become a standard yardstick to measure the quality of online algorithms. One compares the solution produced by an online algorithm to that of an optimal (clairvoyant) offline algorithm. An online algorithm is called $c$-competitive if on every input the solution it produces has cost'' at most $c$~times that of the optimal offline algorithm. This situation can be imagined as a game between an online player and a malicious adversary. Although competitive analysis is a worst-case analysis and henceforth pessimistic, it often allows important insights into the problem structure. One can obtain an idea about what kind of strategies are promising for real-world systems and why. On the other hand there are also cases where the offline adversary is simply too powerful and allows only trivial competitiveness results. This phenomenon is called hitting the triviality barrier''. We investigate several online problems by means of competitive analysis. We also introduce new concepts to overcome the weaknesses of the standard approach and to go beyond the triviality barrier.
02-25
693
urn:nbn:de:0297-zib-6925
Sven O. Krumke
ZIB-Report
02-25
eng
uncontrolled
competitive analysis
eng
uncontrolled
online optimization
eng
uncontrolled
online algorithm
eng
uncontrolled
approximation algorithm
Informatik, Informationswissenschaft, allgemeine Werke
Analysis of algorithms and problem complexity [See also 68W40]
Communication networks [See also 68M10, 94A05]
Combinatorial optimization
Mathematical Optimization
ZIB Allgemein
Habilitationen
ONLINE-PLANNING
https://opus4.kobv.de/opus4-zib/files/692/ZR-02-25.ps
https://opus4.kobv.de/opus4-zib/files/692/ZR-02-25.pdf
693
deu
reportzib
0
2002-07-01
2002-07-01
--
P=NP?
Hinter der für den Uneingeweihten etwas kryptischen Frage "P = NP?" verbirgt sich das derzeit wichtigste Problem der Komplexitätstheorie. Dieser Artikel erläutert einige Aspekte der Theorie und erklärt informell, was "P = NP?" bedeutet. Es geht nicht nur um komplizierte algorithmische Mathematik und Informatik, sondern um grundsätzliche Fragen unserer Lebensumwelt. Kann man vielleicht beweisen, dass es für viele Probleme unseres Alltags keine effizienten Lösungsmethoden gibt?
02-26
694
urn:nbn:de:0297-zib-6939
Erschienen in: Elemente der Mathematik, Vol. 57, Nr. 3 (2002) 96-102
Martin Grötschel
ZIB-Report
02-26
deu
uncontrolled
computational complexity
deu
uncontrolled
P=NP
Informatik, Informationswissenschaft, allgemeine Werke
Complexity of computation (including implicit computational complexity) [See also 68Q15, 68Q17]
Instructional exposition (textbooks, tutorial papers, etc.)
Complexity classes (hierarchies, relations among complexity classes, etc.) [See also 03D15, 68Q17, 68Q19]
Analysis of algorithms and problem complexity [See also 68W40]
ZIB Allgemein
Grötschel, Martin
https://opus4.kobv.de/opus4-zib/files/693/ZR-02-26.ps
https://opus4.kobv.de/opus4-zib/files/693/ZR-02-26.pdf
689
eng
reportzib
0
2002-05-07
2002-05-07
--
Online Call Admission in Optical Networks with Larger Wavelength Demands
In the problem of \emph{Online Call Admission in Optical Networks}, briefly called \textsc{oca}, we are given a graph $G=(V,E)$ together with a set of wavelengths~$W$ and a finite sequence $\sigma=r_1,r_2,\dots$ of calls which arrive in an online fashion. Each call~$r_j$ specifies a pair of nodes to be connected and an integral demand indicating the number of required lightpaths. A lightpath is a path in~$G$ together with a wavelength~$\lambda \in W$. Upon arrival of a call, an online algorithm must decide immediately and irrevocably whether to accept or to reject the call without any knowledge of calls which appear later in the sequence. If the call is accepted, the algorithm must provide the requested number of lightpaths to connect the specified nodes. The essential restriction is the wavelength conflict constraint: each wavelength is available only once per edge, which implies that two lightpaths sharing an edge must have different wavelengths. Each accepted call contributes a benefit equal to its demand to the overall profit. The objective in \textsc{oca} is to maximize the overall profit. Competitive algorithms for \textsc{oca} have been known for the special case where every call requests just a single lightpath. In this paper we present the first competitive online algorithms for the general case of larger demands.
02-22
690
urn:nbn:de:0297-zib-6890
Appeared in: Graph-Theoretic Concepts in Computer Science. 28 Intern. Workshop, WG 2002, Cesky Krumlov, Czech Republic, June 13-15, 2002, revised papers. L. Kucera (ed.) Springer 2002. LNCS 2573. Pp. 333-344
Sven O. Krumke
Diana Poensgen
ZIB-Report
02-22
eng
uncontrolled
Call Admission
eng
uncontrolled
Routing and Wavelength Allocation
eng
uncontrolled
Optical Networks
eng
uncontrolled
Competitive Analysis
eng
uncontrolled
Colorability
Informatik, Informationswissenschaft, allgemeine Werke
Analysis of algorithms and problem complexity [See also 68W40]
Communication networks [See also 68M10, 94A05]
Combinatorial optimization
ZIB Allgemein
DynRoute
ONLINE-PLANNING
https://opus4.kobv.de/opus4-zib/files/689/ZR-02-22.ps
https://opus4.kobv.de/opus4-zib/files/689/ZR-02-22.pdf
818
eng
reportzib
0
2004-11-08
2004-11-08
--
A Note on Contraction Degeneracy
The parameter contraction degeneracy -- the maximum minimum degree over all minors of a graph -- is a treewidth lower bound and was first defined in (Bodlaender, Koster, Wolle, 2004). In experiments it was shown that this lower bound improves upon other treewidth lower bounds. In this note, we examine some relationships between the contraction degeneracy and connected components of a graph, block s of a graph and the genus of a graph. We also look at chordal graphs, and we study an upper bound on the contraction degeneracy and another lower bound for treewidth. A data structure that can be used for algorithms computing the degeneracy and similar parameters, is also described.
04-43
819
urn:nbn:de:0297-zib-8180
Thomas Wolle
Arie M.C.A. Koster
Hans L. Bodlaender
ZIB-Report
04-43
eng
uncontrolled
contraction degeneracy
eng
uncontrolled
genus of a graph
eng
uncontrolled
treewidth lower bounds
Informatik, Informationswissenschaft, allgemeine Werke
Graph algorithms [See also 68R10, 68W05]
Analysis of algorithms and problem complexity [See also 68W40]
Graph theory (including graph drawing) [See also 05Cxx, 90B10, 90B35, 90C35]
ZIB Allgemein
NWO-TACO
https://opus4.kobv.de/opus4-zib/files/818/ZR-04-43.ps
https://opus4.kobv.de/opus4-zib/files/818/ZR-04-43.pdf
819
eng
reportzib
0
2004-11-08
2004-11-08
--
Degree-Based Treewidth Lower Bounds
Every lower bound for treewidth can be extended by taking the maximum of the lower bound over all subgraphs or minors. This extension is shown to be a very vital idea for improving treewidth lower bounds. In this paper, we investigate a total of nine graph parameters, providing lower bounds for treewidth. The parameters have in common that they all are the vertex-degree of some vertex in a subgra ph or minor of the input graph. We show relations between these graph parameters and study their computational complexity. To allow a practical comparison of the bounds, we developed heuristic algorithms for those parameters that are NP-hard to compute. Computational experiments show that combining the treewidth lower bounds with minors can considerably improve the lower bounds.
04-44
820
urn:nbn:de:0297-zib-8193
Appeared in: Proc. 4th Int. Workshop on Experimental and Efficient Algorithms WEA 2005. S. E. Nikoletseas (ed.) LNCS 3503, Springer 2005, pp. 101-112
Arie M.C.A. Koster
Thomas Wolle
Hans L. Bodlaender
ZIB-Report
04-44
eng
uncontrolled
contraction degeneracy
eng
uncontrolled
Ramachandramurthi parameter
eng
uncontrolled
treewidth lower bounds
Informatik, Informationswissenschaft, allgemeine Werke
Graph algorithms [See also 68R10, 68W05]
Analysis of algorithms and problem complexity [See also 68W40]
Graph theory (including graph drawing) [See also 05Cxx, 90B10, 90B35, 90C35]
ZIB Allgemein
NWO-TACO
https://opus4.kobv.de/opus4-zib/files/819/ZR-04-44.ps
https://opus4.kobv.de/opus4-zib/files/819/ZR-04-44.pdf
820
eng
reportzib
0
2004-11-08
2004-11-08
--
On the Maximum Cardinality Search Lower Bound for Treewidth
The Maximum Cardinality Search algorithm visits the vertices of a graph in some order, such that at each step, an unvisited vertex that has the largest number of visited neighbors becomes visited. An MCS-ordering of a graph is an ordering of the vertices that can be generated by the Maximum Cardinality Search algorithm. The visited degree of a vertex $v$ in an MCS-ordering is the number of neighbors of $v$ that are before $v$ in the ordering. The visited degree of an MCS-ordering $\psi$ of $G$ is the maximum visited degree over all vertices $v$ in $\psi$. The maximum visited degree over all MCS-orderings of graph $G$ is called its {\em maximum visited degree}. Lucena (2003) showed that the treewidth of a graph $G$ is at least its maximum visited degree. We show that the maximum visited degree is of size $O(\log n)$ for planar graphs, and give examples of planar graphs $G$ with maximum visited degree $k$ with $O(k!)$ vertices, for all $k\in \Bbb{N}$. Given a graph $G$, it is NP-complete to determine if its maximum visited degree is at least $k$, for any fixed $k\geq 7$. Also, this problem does not have a polynomial time approximation algorithm with constant ratio, unless P=NP. Variants of the problem are also shown to be NP-complete. We also propose and experimentally analyses some heuristics for the problem. Several tiebreakers for the MCS algorithm are proposed and evaluated. We also give heuristics that give upper bounds on the value of the maximum visited degree of a graph, which appear to give results close to optimal on many graphs from real life applications.
04-45
821
urn:nbn:de:0297-zib-8201
Appeared in: Discrete Applied Mathematics 155 (2007) 1348-1372. An extended abstract appeared in: Proceedings of International Workshop on Graph-Theoretic Concepts in Computer Science, WG 2004, Lecture Notes in Computer Science 3353, 2005, 81-92
Hans L. Bodlaender
Arie M.C.A. Koster
ZIB-Report
04-45
eng
uncontrolled
maximum cardinality search
eng
uncontrolled
treewidth
eng
uncontrolled
lower bounds
eng
uncontrolled
planar graphs
eng
uncontrolled
graph algorithms
Informatik, Informationswissenschaft, allgemeine Werke
Graph algorithms [See also 68R10, 68W05]
Analysis of algorithms and problem complexity [See also 68W40]
Graph theory (including graph drawing) [See also 05Cxx, 90B10, 90B35, 90C35]
ZIB Allgemein
NWO-TACO
https://opus4.kobv.de/opus4-zib/files/820/ZR-04-45.ps
https://opus4.kobv.de/opus4-zib/files/820/ZR-04-45.pdf
891
deu
reportzib
0
2005-12-14
2005-12-14
--
Das Problem mit der Komplexität: P = NP?
Was Komplexität ist, weiß niemand so richtig. In vielen Wissenschaftsgebieten wird der Begriff Komplexität verwendet, überall mit etwas anderer Bedeutung. Mathematik und Informatik hab en eine eigene Theorie hierzu entwickelt: die Komplexitätstheorie. Sie stellt zwar grundlegende Begriffe bereit, aber leider sind die meisten wichtigen Fragestellungen noch ungelöst. Diese kurze Einführung konzentriert sich auf einen speziellen, aber bedeutenden Aspekt der Theorie: Lösbarkeit von Problemen in deterministischer und nichtdeterministischer polynomialer Zeit. Hinter der für Uneingeweihte etwas kryptischen Frage "P = NP?" verbirgt sich das derzeit wichtigste Problem der Komplexitätstheorie. Anhand dieser Fragestellung werden einige Aspekte der Theorie erläutert und formell erklärt, was "P = NP?" bedeutet. Es geht nicht nur um komplizierte algorithmische Mathematik und Informatik, sondern um grundsätzliche Fragen unserer Lebensumwelt. Kann man vielleicht beweisen, dass es für viele Probleme unseres Alltags keine effizienten Lösungsmethoden gibt?
05-58
891
urn:nbn:de:0297-zib-8916
Ersch. in: Kombinatorische Optimierung erleben - In Studium und Unterricht von Stefan Hußmann und Brigitte Lutz-Westphal. Aus der Reihe: Mathematik erleben. Unter Mitarbeit von Brieden, Andreas / Gritzmann, Peter / Grötschel, Martin / Leuders, Timo. Vieweg, 2007. ISBN: 978-3-528-03216-6 S.265-274
Martin Grötschel
ZIB-Report
05-58
deu
uncontrolled
Komplexität
deu
uncontrolled
Komplexitätstheorie
Informatik, Informationswissenschaft, allgemeine Werke
Instructional exposition (textbooks, tutorial papers, etc.)
Analysis of algorithms and problem complexity [See also 68W40]
Instructional exposition (textbooks, tutorial papers, etc.)
ZIB Allgemein
Grötschel, Martin
https://opus4.kobv.de/opus4-zib/files/891/ZR-05-58.pdf
896
eng
reportzib
0
2006-01-25
2006-01-25
--
Approximability of Unsplittable Shortest Path Routing Problems
In this paper, we discuss the relation of unsplittable shortest path routing (USPR) to other routing schemes and study the approximability of three USPR network planning problems. Given a digraph $D=(V,A)$ and a set $K$ of directed commodities, an USPR is a set of flow paths $\Phi_{(s,t)}$, $(s,t)\in K$, such that there exists a metric $\lambda=(\lambda_a)\in \mathbb{Z}^A_+$ with respect to which each $\Phi_{(s,t)}$ is the unique shortest $(s,t)$-path. In the \textsc{Min-Con-USPR} problem, we seek for an USPR that minimizes the maximum congestion over all arcs. We show that this problem is hard to approximate within a factor of $\mathcal{O}(|V|^{1-\epsilon})$, but easily approximable within min$(|A|,|K|)$ in general and within $\mathcal{O}(1)$ if the underlying graph is an undirected cycle or a bidirected ring. We also construct examples where the minimum congestion that can be obtained by USPR is a factor of $\Omega(|V|^2)$ larger than that achievable by unsplittable flow routing or by shortest multi-path routing, and a factor of $\Omega(|V|)$ larger than by unsplittable source-invariant routing. In the CAP-USPR problem, we seek for a minimum cost installation of integer arc capacities that admit an USPR of the given commodities. We prove that this problem is $\mathcal{NP}$-hard to approximate within $2-\epsilon$ (even in the undirected case), and we devise approximation algorithms for various special cases. The fixed charge network design problem \textsc{Cap-USPR}, where the task is to find a minimum cost subgraph of $D$ whose fixed arc capacities admit an USPR of the commodities, is shown to be $\mathcal{NPO}$-complete. All three problems are of great practical interest in the planning of telecommunication networks that are based on shortest path routing protocols. Our results indicate that they are harder than the corresponding unsplittable flow or shortest multi-path routing problems.
06-02
896
urn:nbn:de:0297-zib-8968
A slightly modified version appeared in: Networks 54 (2009) 23-46
Andreas Bley
ZIB-Report
06-02
eng
uncontrolled
Shortest path routing
eng
uncontrolled
unsplittable flow
eng
uncontrolled
computational complexity
eng
uncontrolled
approximation
Informatik, Informationswissenschaft, allgemeine Werke
Paths and cycles [See also 90B10]
Analysis of algorithms and problem complexity [See also 68W40]
Communication networks [See also 68M10, 94A05]
Combinatorial optimization
Abstract computational complexity for mathematical programming problems [See also 68Q25]
ZIB Allgemein
X-WiN
https://opus4.kobv.de/opus4-zib/files/896/ZR-06-02.pdf
https://opus4.kobv.de/opus4-zib/files/896/ZR-06-02.ps
889
eng
reportzib
0
2005-12-09
2005-12-09
--
Probabilistic Competitive Analysis of a Dial-a-Ride Problem on Trees Under High Load
In this paper we consider a simple variant of the Online Dial-a-Ride Problem from a probabilistic point of view. To this end, we look at a probabilistic version of this online Dial-a-Ride problem and introduce a probabilistic notion of the competitive ratio which states that an algorithm performs well on the vast majority of the instances. Our main result is that under the assumption of high load a certain online algorithm is probabilistically $(1+o(1))$-competitive if the underlying graph is a tree. This result can be extended to general graphs by using well-known approximation techniques at the expense of a distortion factor~$O(\log\|V\|)$.
05-56
889
urn:nbn:de:0297-zib-8896
Benjamin Hiller
ZIB-Report
05-56
eng
uncontrolled
probabilistic competitive analysis
eng
uncontrolled
Dial-a-Ride problem
eng
uncontrolled
online algorithms
eng
uncontrolled
IGNORE strategy
Informatik, Informationswissenschaft, allgemeine Werke
Nonnumerical Algorithms and Problems (E.2-5, G.2, H.2-3)
Analysis of algorithms and problem complexity [See also 68W40]
Approximation algorithms
ZIB Allgemein
Hiller, Benjamin
ONLINE-PLANNING
https://opus4.kobv.de/opus4-zib/files/889/ZR-05-56.pdf
https://opus4.kobv.de/opus4-zib/files/889/ZR-05-56.ps
1011
eng
masterthesis
TU Ilmenau
0
2004-12-31
2004-12-31
--
Bad Guys are Rare: Probabilistic Analysis of an Elementary Dial-a-Ride Problem
This thesis deals with a Dial-a-Ride problem on trees and considers both offline and online versions of this problem. We study the behavior of certain algorithms on random instances, i.e. we do probabilistic analysis. The focus is on results describing the typical behavior of the algorithms, i.e. results holding with (asymptotically) high probability. For the offline version, we present a simplified proof of a result of Coja-Oghlan, Krumke und Nierhoff. The results states that some heuristic using a minimum spanning tree to approximate a Steiner tree gives optimal results with high probability. This explains why this heuristic produces optimal solutions quite often. In the second part, probabilistic online versions of the problem are introduced. We study the online strategies REPLAN and IGNORE. Regarding the IGNORE strategy we can show that it works almost optimal under high load with high probability.
1026
urn:nbn:de:0297-zib-10114
Benjamin Hiller
unknown unknown
eng
uncontrolled
Dial-a-Ride problem on trees
eng
uncontrolled
probabilistic analysis
eng
uncontrolled
online algorithms
Mathematik
Nonnumerical Algorithms and Problems (E.2-5, G.2, H.2-3)
Combinatorics (F.2.2)
Analysis of algorithms and problem complexity [See also 68W40]
Graph theory (including graph drawing) [See also 05Cxx, 90B10, 90B35, 90C35]
Transportation, logistics
Studienabschlussarbeiten
Mathematical Optimization
Hiller, Benjamin
ONLINE-PLANNING
Zuse Institute Berlin (ZIB)
https://opus4.kobv.de/opus4-zib/files/1011/probabilistic_darp.pdf
838
eng
reportzib
0
2005-01-12
2005-01-12
--
Inapproximability Results for the Inverse Shortest Paths Problem with Integer Length and Unique Shortest Paths
We study the complexity of two Inverse Shortest Paths (ISP) problems with integer arc lengths and the requirement for uniquely determined shortest paths. Given a collection of paths in a directed graph, the task is to find positive integer arc lengths such that the given paths are uniquely determined shortest paths between their respective terminals. The first problem seeks for arc lengths that minimize the length of the longest of the prescribed paths. In the second problem, the length of the longest arc is to be minimized. We show that it is $np-hard$ to approximate the minimal longest path length within a factor less than $8/7$ or the minimal longest arc length within a factor less than $9/8$. This answers the (previously) open question whether these problems are $np-hard$ or not. We also present a simple algorithm that achieves an $\mathcal{O}(|V|)$-approximation guarantee for both variants. Both ISP problems arise in the planning of telecommunication networks with shortest path routing protocols. Our results imply that it is $\mathcal{NP}$-hard to decide whether a given path set can be realized with a real shortest path routing protocol such as OSPF, IS-IS, or RIP.
urn:nbn:de:0297-zib-8388
838
05-04
Appeared in: Networks 50 (2007) 29-36. And also as : "Finding Small Administrative Lengths for Shortest Path Routing" in Proceedings of the Second International Network Optimization Conference vol(1) (INOC 2005) 121-128, Lisboa
Andreas Bley
ZIB-Report
05-04
eng
uncontrolled
Inverse Shortest Paths
eng
uncontrolled
Computational Complexity
eng
uncontrolled
Approximation
eng
uncontrolled
Shortest Path Routing
Informatik, Informationswissenschaft, allgemeine Werke
Paths and cycles [See also 90B10]
Analysis of algorithms and problem complexity [See also 68W40]
Communication networks [See also 68M10, 94A05]
Combinatorial optimization
Abstract computational complexity for mathematical programming problems [See also 68Q25]
ZIB Allgemein
X-WiN
https://opus4.kobv.de/opus4-zib/files/838/ZR-05-04.ps
https://opus4.kobv.de/opus4-zib/files/838/ZR-05-04.pdf