TY - GEN A1 - Bley, Andreas T1 - On the Complexity of Vertex-Disjoint Length-Restricted Path Problems N2 - 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. T3 - ZIB-Report - SC-98-20 KW - disjoint paths KW - length bounded paths KW - approximation KW - reducibility KW - completeness Y1 - 1998 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-3639 ER - TY - GEN A1 - Hauptmeier, Dietrich A1 - Krumke, Sven A1 - Rambau, Jörg A1 - Wirth., Hans-Christoph T1 - Euler is Standing in Line N2 - 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$. T3 - ZIB-Report - SC-99-06 KW - NP-completeness KW - polynomial-time approximation algorithms KW - stacker-crane problem KW - vehicle routing KW - elevator system KW - Eulerian Cycle Y1 - 1999 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-3947 ER - TY - GEN A1 - Konjevod, Goran A1 - Krumke, Sven A1 - Marathe, Madhav T1 - Budget Constrained Minimum Cost Connected Medians N2 - 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 T3 - ZIB-Report - 00-10 KW - NP-hardness KW - Approximation Algorithms KW - Network Y1 - 2000 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-5783 ER - TY - GEN A1 - Krumke, Sven A1 - Rambau, Jörg A1 - Weider, Steffen T1 - An Approximation Algorithm for the Non-Preemptive Capacitated Dial-a-Ride Problem N2 - 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. T3 - ZIB-Report - 00-53 KW - NP-completeness KW - polynomial-time approximation algorithms KW - stacker-crane problem KW - vehicle Y1 - 2000 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-6217 ER - TY - GEN A1 - Krumke, Sven A1 - Poensgen, Diana T1 - Online Call Admission in Optical Networks with Larger Wavelength Demands N2 - 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. T3 - ZIB-Report - 02-22 KW - Call Admission KW - Routing and Wavelength Allocation KW - Optical Networks KW - Competitive Analysis KW - Colorability Y1 - 2002 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-6890 ER - TY - GEN A1 - Krumke, Sven A1 - Marathe, Madhav A1 - Poensgen, Diana A1 - Ravi, Sekharipuram S. A1 - Wirth, Hans-Christoph T1 - Budgeted Maximal Graph Coverage N2 - 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. T3 - ZIB-Report - 02-24 KW - budgeted maximum coverage KW - approximation algorithm KW - dynamic programming Y1 - 2002 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-6918 ER - TY - THES A1 - Krumke, Sven T1 - Online Optimization: Competitive Analysis and Beyond N2 - 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. T3 - ZIB-Report - 02-25 KW - competitive analysis KW - online optimization KW - online algorithm KW - approximation algorithm Y1 - 2002 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-6925 ER - TY - GEN A1 - Grötschel, Martin T1 - P=NP? N2 - 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? T3 - ZIB-Report - 02-26 KW - computational complexity KW - P=NP Y1 - 2002 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-6939 ER - TY - GEN A1 - Wolle, Thomas A1 - Koster, Arie M.C.A. A1 - Bodlaender, Hans L. T1 - A Note on Contraction Degeneracy N2 - 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. T3 - ZIB-Report - 04-43 KW - contraction degeneracy KW - genus of a graph KW - treewidth lower bounds Y1 - 2004 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-8180 ER - TY - GEN A1 - Koster, Arie M.C.A. A1 - Wolle, Thomas A1 - Bodlaender, Hans L. T1 - Degree-Based Treewidth Lower Bounds N2 - 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. T3 - ZIB-Report - 04-44 KW - contraction degeneracy KW - Ramachandramurthi parameter KW - treewidth lower bounds Y1 - 2004 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-8193 ER -