@misc{HeinzKrumkeMegowetal.2005, author = {Heinz, Stefan and Krumke, Sven and Megow, Nicole and Rambau, J{\"o}rg and Tuchscherer, Andreas and Vredeveld, Tjark}, title = {The Online Target Date Assignment Problem}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-8945}, number = {05-61}, year = {2005}, abstract = {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.}, language = {en} } @misc{Groetschel2005, author = {Gr{\"o}tschel, Martin}, title = {Das Problem mit der Komplexit{\"a}t: P = NP?}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-8916}, number = {05-58}, year = {2005}, abstract = {Was Komplexit{\"a}t ist, weiß niemand so richtig. In vielen Wissenschaftsgebieten wird der Begriff Komplexit{\"a}t verwendet, {\"u}berall mit etwas anderer Bedeutung. Mathematik und Informatik hab en eine eigene Theorie hierzu entwickelt: die Komplexit{\"a}tstheorie. Sie stellt zwar grundlegende Begriffe bereit, aber leider sind die meisten wichtigen Fragestellungen noch ungel{\"o}st. Diese kurze Einf{\"u}hrung konzentriert sich auf einen speziellen, aber bedeutenden Aspekt der Theorie: L{\"o}sbarkeit von Problemen in deterministischer und nichtdeterministischer polynomialer Zeit. Hinter der f{\"u}r Uneingeweihte etwas kryptischen Frage "P = NP?" verbirgt sich das derzeit wichtigste Problem der Komplexit{\"a}tstheorie. Anhand dieser Fragestellung werden einige Aspekte der Theorie erl{\"a}utert und formell erkl{\"a}rt, was "P = NP?" bedeutet. Es geht nicht nur um komplizierte algorithmische Mathematik und Informatik, sondern um grunds{\"a}tzliche Fragen unserer Lebensumwelt. Kann man vielleicht beweisen, dass es f{\"u}r viele Probleme unseres Alltags keine effizienten L{\"o}sungsmethoden gibt?}, language = {de} } @misc{GruberKosterOrlowskietal.2005, author = {Gruber, Claus G. and Koster, Arie M.C.A. and Orlowski, Sebastian and Wess{\"a}ly, Roland and Zymolka, Adrian}, title = {A new model and a computational study for Demand-wise Shared Protection}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-8880}, number = {05-55}, year = {2005}, abstract = {This report combines the contributions to INOC 2005 (Wess{\"a}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.}, language = {en} } @misc{Groetschel2005, author = {Gr{\"o}tschel, Martin}, title = {Schnelle Rundreisen: Das Travelling Salesman-Problem}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-8901}, number = {05-57}, year = {2005}, abstract = {Das Travelling-Salesman-Problem (TSP) ist das am intensivsten untersuchte kombinatorische Optimierungsproblem. In diesem Abschnitt wird eine Einf{\"u}hrung in das TSP gegeben. Es werden Problemstellungen erl{\"a}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{\"o}sungsverfahren werden an Beispielen skizziert, und es wird angedeutet, dass man, obwohl TSPs zu den theoretisch schweren Problemen z{\"a}hlen, in der Praxis TSPs von atemberaubender Gr{\"o}ße l{\"o}sen kann.}, language = {de} } @misc{BodlaenderGrigorievKoster2005, author = {Bodlaender, Hans L. and Grigoriev, Alexander and Koster, Arie M.C.A.}, title = {Treewidth Lower Bounds with Brambles}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-8878}, number = {05-54}, year = {2005}, abstract = {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.}, language = {en} } @misc{Hiller2005, author = {Hiller, Benjamin}, title = {Probabilistic Competitive Analysis of a Dial-a-Ride Problem on Trees Under High Load}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-8896}, number = {05-56}, year = {2005}, abstract = {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\|)\$.}, language = {en} } @misc{KiselevWolf2005, author = {Kiselev, Arthemy V. and Wolf, Thomas}, title = {On weakly non-local, nilpotent, and super-recursion operators for N=1 super-equations}, arxiv = {http://arxiv.org/abs/nlin.SI/0511056}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-8850}, number = {05-52}, year = {2005}, abstract = {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.}, language = {en} } @misc{KiselevWolf2005, author = {Kiselev, Arthemy V. and Wolf, Thomas}, title = {Supersymmetric representations and integrable super-extensions of the Burgers and Boussinesq equations}, arxiv = {http://arxiv.org/abs/math-ph/0511071}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-8869}, number = {05-53}, year = {2005}, abstract = {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.}, language = {en} } @misc{KosterWagler2005, author = {Koster, Arie M.C.A. and Wagler, Annegret}, title = {Comparing Imperfection Ratio and Imperfection Index for Graph Classes}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-8836}, number = {05-50}, year = {2005}, abstract = {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.}, language = {en} } @misc{Koch2005, author = {Koch, Thorsten}, title = {Rapid Mathematical Programming or How to Solve Sudoku Puzzles in a few Seconds}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-8845}, number = {05-51}, year = {2005}, abstract = {Using the popular puzzle game of Sudoku, this article highlights some of the ideas and topics covered in ZR-04-58.}, language = {en} }