@misc{KonjevodKrumkeMarathe, author = {Konjevod, Goran and Krumke, Sven and Marathe, Madhav}, title = {Budget Constrained Minimum Cost Connected Medians}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-5783}, number = {00-10}, abstract = {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}, language = {en} } @misc{Groetschel, author = {Gr{\"o}tschel, Martin}, title = {P=NP?}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-6939}, number = {02-26}, abstract = {Hinter der f{\"u}r den Uneingeweihten etwas kryptischen Frage "P = NP?" verbirgt sich das derzeit wichtigste Problem der Komplexit{\"a}tstheorie. Dieser Artikel erl{\"a}utert einige Aspekte der Theorie und erkl{\"a}rt informell, 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} }