TY - GEN A1 - Heinz, Stefan A1 - Krumke, Sven A1 - Megow, Nicole A1 - Rambau, Jörg A1 - Tuchscherer, Andreas A1 - Vredeveld, Tjark T1 - The Online Target Date Assignment Problem N2 - Many online problems encountered in real-life involve a two-stage decision process: upon arrival of a new request, an irrevocable first-stage decision (the assignment of a specific resource to the request) must be made immediately, while in a second stage process, certain ``subinstances'' (that is, the instances of all requests assigned to a particular resource) can be solved to optimality (offline) later. We introduce the novel concept of an \emph{Online Target Date Assignment Problem} (\textsc{OnlineTDAP}) as a general framework for online problems with this nature. Requests for the \textsc{OnlineTDAP} become known at certain dates. An online algorithm has to assign a target date to each request, specifying on which date the request should be processed (e.\,g., an appointment with a customer for a washing machine repair). The cost at a target date is given by the \emph{downstream cost}, the optimal cost of processing all requests at that date w.\,r.\,t.\ some fixed downstream offline optimization problem (e.\,g., the cost of an optimal dispatch for service technicians). We provide general competitive algorithms for the \textsc{OnlineTDAP} independently of the particular downstream problem, when the overall objective is to minimize either the sum or the maximum of all downstream costs. As the first basic examples, we analyze the competitive ratios of our algorithms for the par ticular academic downstream problems of bin-packing, nonpreemptive scheduling on identical parallel machines, and routing a traveling salesman. T3 - ZIB-Report - 05-61 KW - Online Algorithms KW - Online Target Date Assignment Problem Y1 - 2005 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-8945 ER - TY - GEN A1 - Grötschel, Martin T1 - Das Problem mit der Komplexität: P = NP? N2 - 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? T3 - ZIB-Report - 05-58 KW - Komplexität KW - Komplexitätstheorie Y1 - 2005 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-8916 ER - TY - GEN A1 - Gruber, Claus G. A1 - Koster, Arie M.C.A. A1 - Orlowski, Sebastian A1 - Wessäly, Roland A1 - Zymolka, Adrian T1 - A new model and a computational study for Demand-wise Shared Protection N2 - This report combines the contributions to INOC 2005 (Wessälly et al., 2005) and DRCN 2005 (Gruber et al., 2005). A new integer linear programming model for the end-to-end survivability concept deman d-wise shared protection (DSP) is presented. DSP is based on the idea that backup capacity is dedicated to a particular demand, but shared within a demand. It combines advantages of dedicated and shared protection: It is more cost-efficient than dedicated protection and operationally easier than shared protection. In a previous model for DSP, the number of working and backup paths to be configured for a particular demand has been an input parameter; in the more general model for DSP investigated in this paper, this value is part of the decisions to take. To use the new DSP model algorithmically, we suggest a branch-and-cut approach which employs a column generation procedure to deal with the exponential number of routing variables. A computational study to compare the new resilience mechanism DSP with dedicated and shared path protection is performed. The results for five realistic network planning scenarios reveal that the best solutions for DSP are on average 15\% percent better than the corresponding 1+1 dedicated path protection solutions, and only 15\% percent worse than shared path protection. T3 - ZIB-Report - 05-55 KW - demand-wise shared protection KW - resilience KW - network design KW - integer linear programming Y1 - 2005 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-8880 ER - TY - GEN A1 - Grötschel, Martin T1 - Schnelle Rundreisen: Das Travelling Salesman-Problem N2 - Das Travelling-Salesman-Problem (TSP) ist das am intensivsten untersuchte kombinatorische Optimierungsproblem. In diesem Abschnitt wird eine Einführung in das TSP gegeben. Es werden Problemstellungen erläutert, Anwendungen skizziert und einige Schwierigkeiten bei der korrekten Modellierung der Zielfunktion dargelegt. Es ist gar nicht so klar, was in einem konkreten Problem die wirkliche Entfernung ist. Exakte und approximative Lösungsverfahren werden an Beispielen skizziert, und es wird angedeutet, dass man, obwohl TSPs zu den theoretisch schweren Problemen zählen, in der Praxis TSPs von atemberaubender Größe lösen kann. T3 - ZIB-Report - 05-57 KW - Travelling-Salesman-Problem KW - TSP KW - Rundreisen KW - optimale Tour Y1 - 2005 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-8901 ER - TY - GEN A1 - Bodlaender, Hans L. A1 - Grigoriev, Alexander A1 - Koster, Arie M.C.A. T1 - Treewidth Lower Bounds with Brambles N2 - In this paper we present a new technique for computing lower bounds for graph treewidth. Our technique is based on the fact that the treewidth of a graph $G$ is the maximum order of a bramble of $G$ minus one. We give two algorithms: one for general graphs, and one for planar graphs. The algorithm for planar graphs is shown to give a lower bound for both the treewidth and branchwidth that is at most a constant factor away from the optimum. For both algorithms, we report on extensive computational experiments that show that the algorithms give often excellent lower bounds, in particular when applied to (close to) planar graphs. T3 - ZIB-Report - 05-54 KW - treewidth KW - lower bounds KW - branchwidth KW - brambles Y1 - 2005 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-8878 ER - TY - GEN A1 - Hiller, Benjamin T1 - Probabilistic Competitive Analysis of a Dial-a-Ride Problem on Trees Under High Load N2 - 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\|)$. T3 - ZIB-Report - 05-56 KW - probabilistic competitive analysis KW - Dial-a-Ride problem KW - online algorithms KW - IGNORE strategy Y1 - 2005 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-8896 ER - TY - GEN A1 - Kiselev, Arthemy V. A1 - Wolf, Thomas T1 - On weakly non-local, nilpotent, and super-recursion operators for N=1 super-equations N2 - We consider nonlinear, scaling-invariant $N=1$ boson$+$fermion supersymmetric systems whose right-hand sides are homogeneous differential polynomials and satisfy some natural assumptions. We select the super-systems that admit infinitely many higher symmetries generated by recursion operators; we further restrict ourselves to the case when the dilaton dimensions of the bosonic and fermionic super-fields coincide and the weight of the time is half the weight of the spatial variable. We discover five systems that satisfy these assumptions; one system is transformed to the purely bosonic Burgers equation. We construct local, nilpotent, triangular, weakly non-local, and super-recursion operators for their symmetry algebras. T3 - ZIB-Report - 05-52 Y1 - 2005 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-8850 ER - TY - GEN A1 - Kiselev, Arthemy V. A1 - Wolf, Thomas T1 - Supersymmetric representations and integrable super-extensions of the Burgers and Boussinesq equations N2 - New evolutionary supersymmetric systems whose right-hand sides are homogeneous differential polynomials and which possess infinitely many higher symmetries are constructed. Their intrinsic geometry (symmetries, conservation laws, recursion operators, Hamiltonian structures, and exact solutions) is analyzed by using algebraic methods. A supersymmetric $N=1$ representation of the Burgers equation is obtained. An $N=2$ KdV-component system that reduces to the Burgers equation in the diagonal $N=1$ case $\theta^1=\theta^2$ is found; the $N=2$ Burgers equation admits and $N=2$ modified KdV symmetry. A one\/-\/parametric family of $N=0$ super\/-\/systems that exte nd the Burgers equation is described; we relate the systems within this family with the Burgers equation on associative algebras. A supersymmetric boson$+$fermion representation of the dispersionless Boussinesq equation is investigated. We solve this equation explicitly and construct its integrable deformation that generates two infinite sequences of the Hamiltonians. The Boussinesq equation with dispersion is embedded in a one-parametric family of two-component systems with dissipation. We finally construct a three-parametric supersymmetric system that incorporates the Boussinesq equation with dispersion and dissipation but never retracts to it for any values of the parameters. T3 - ZIB-Report - 05-53 Y1 - 2005 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-8869 ER - TY - GEN A1 - Koster, Arie M.C.A. A1 - Wagler, Annegret T1 - Comparing Imperfection Ratio and Imperfection Index for Graph Classes N2 - Perfect graphs constitute a well-studied graph class with a rich structure, reflected by many characterizations with respect to different concepts. Perfect graphs are, for instance, precisely those graphs $G$ where the stable set polytope $STAB(G)$ coincides with the fractional stable set polytope $QSTAB(G)$. For all imperfect graphs $G$ it holds that $STAB(G) \subset QSTAB(G)$. It is, therefore, natural to use the difference between the two polytopes in order to decide how far an imperfect graph is away from being perfect; we discuss three different concepts, involving the facet set of $STAB( G)$, the disjunctive index of $QSTAB(G)$, and the dilation ratio of the two polytopes. Including only certain types of facets for $STAB(G)$, we obtain graphs that are in some sense close to perfect graphs, for example minimally immperfect graphs, and certain other classes of so-called rank-perfect graphs. The imperfection ratio has been introduced by (Gerke and McDiarmid, 2001) as the dilation ratio of $STAB(G)$ and $QSTAB(G)$, whereas (Aguilera et al., 2003) suggest to take the disjunctive index of $Q STAB(G)$ as the imperfection index of $G$. For both invariants there exist no general upper bounds, but there are bounds known for the imperfection ratio of several graph classes (Coulonges et al. 2005, Gerke and McDiarmid, 2001). Outgoing from a graph-theoretical interpretation of the imperfection index, we conclude that the imperfection index is NP-hard to compute and we prove that there exists no upper bound on the imperfect ion index for those graph classes with a known bounded imperfection ratio. Comparing the two invariants on those classes, it seems that the imperfection index measures imperfection much more roughly than the imperfection ratio; therefoe, discuss possible directions for refinements. T3 - ZIB-Report - 05-50 KW - perfect graphs KW - imperfection ratio KW - imperfection index Y1 - 2005 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-8836 ER - TY - GEN A1 - Koch, Thorsten T1 - Rapid Mathematical Programming or How to Solve Sudoku Puzzles in a few Seconds N2 - Using the popular puzzle game of Sudoku, this article highlights some of the ideas and topics covered in ZR-04-58. T3 - ZIB-Report - 05-51 KW - Integer Programming KW - Sudoku KW - IP KW - MIP KW - Zimpl KW - Modelling language Y1 - 2005 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-8845 ER -