Wavelets sind in natürlicher Weise auf der gesamten reellen Achse definiert. Auf einem endlichen Intervall benötigt man zusätzliche Randfunktionen und modifizierte Algorithmen.

In diesem Vortrag werde ich verschiedene Ansätze für dieses Problem erläutern, und insbesondere unerwartete neue Phänomene diskutieren, die im Fall von Multiwavelets auftreten.

Fluss- und Routingprobleme gehören zu den klassischen Fragestellungen der diskreten Mathematik. Dennoch sind in praktischen Anwendungen die bekannten Algorithmen für diese Probleme häufig nur sehr eingeschränkt anwendbar. Ein Grund hierfür ist, dass die meisten bekannten Fluss- und Routingalgorithmen statische Modelle betrachten, also Modelle, in denen Zeitabhängigkeit nicht oder nur unzureichend abgebildet wird. In diesem Vortrag führen wir dynamische, also zeitabhängige, Fluss- und Routingmodelle ein. Motiviert wird die Definition dieser Modelle durch verschiedene praktische Anwendungen, z.B. in der Verkehrsplanung. Im Gegensatz zu den meisten klassischen Fragestellungen auf diesem Gebiet sind die hier auftretenden Optimierungsprobleme allerdings nicht mehr optimal in Polynomialzeit lösbar. Dennoch ist es möglich, Approximationsresultate zu erzielen, von denen wir einige vorstellen werden. Eine seit langem bekannte Methode zur Modellierung dynamischer Flüsse ist das zeitexpandierte Netzwerk. Während man mit dieser Methode sehr einfach dynamische Fragestellungen auf statische zurückführen kann, hat dieser Ansatz den Nachteil, dass er extrem große Netzwerke erzeugt und daher für praktische Anwendungen in der Regel nicht verwendbar ist. Aufbauend auf diesem zeitexpandierten Netzwerk stellen wir eine implizite Zeitexpansion vor, die eine sehr kompakte Darstellung erlaubt und damit den Entwurf schneller Routingalgorithmen möglich macht. In einem Industrieprojekt zum Routing von AGVs (Automated Guided Vehicles) konnte die praktische Effizienz der so entwickelten Verfahren nachgewiesen werden.

Diskrete Optimierungsprobleme sind im Allgemeinen nicht polynomial lösbar und werden meist mit Branch-and-Bound oder ähnlichen Algorithmen gelöst. Für diese Verfahren ist es essentiell, gute Schranken zur Verfügung zu haben. Neben den klassischen LP-Relaxierungen haben sich semidefinite Relaxierungen als sehr erfolgreich erwiesen. Dabei werden lineare Probleme über dem Kegel der semidefiniten Matrizen gelöst. Im Vortrag sollen die Vor- und Nachteile dieses Ansatzes diskutiert und mögliche alternative Matrixkegel vorgestellt werden. Als besonders vielversprechend erweist sich dabei der Kegel der so genannten copositiven Matrizen. Dieser Ansatz hat zudem den Vorteil, dass er auf ganzzahlige Probleme mit Polynomfunktionen erweitern lässt.

Telekommunikationsnetze sind in Schichten (engl. layer) organisiert. Die Schichten basieren auf unterschiedlichen Technologien und sind jeweils für spezifische Aufgaben zuständig, wie beispielsweise Routingentscheidungungen, Qualititätskontrolle oder Transport. Die Planung eines Zwei-Layer-Netzes umfasst u. a. die Planung einer Topologie für die IP(Internet)-Netzschicht und die optische Netzschicht, die Dimensionierung von Hardware (Router, Multiplexer etc.) und Linkkapazitäten, sowie die Bestimmung eines Routings für gegebene Kommunikationsbedarfe. Auch Ausfallsicherheitsanforderungen müssen in der Planung berücksichtigt werden, um im Falle eines durchtrennten Kabels oder eines Hardware-Ausfalls den betroffenen Verkehr umrouten zu können. Mangels besserer Planungsmethoden wurden bislang meistens die Routing- und die Transportschicht einzeln geplant, obwohl es starke Abhängigkeiten zwischen ihnen gibt. In diesem Vortrag werden wir eine ganzzahlige lineare Formulierung für eine integrierte Planung beider Schichten vorstellen. Da dieses Modell mit konventionellen Ansätzen sehr schwer zu lösen ist, erarbeiten wir mehrere Klassen von gültigen Ungleichungen. Eine große Rolle spielt in diesem Zusammenhang die Mixed-Integer Rounding (MIR) Methode. Insbesonder werden bewährte Schnittebenen aus der Single-Layer-Netzplanung an eine integrierte Multi-Layer-Planung angepasst und erweitert. Durch den Einsatz dieser Schnittebenen innerhalb eines Branch-and-Cut-Algorithmus konnten die Lösungszeiten für einige praktisch relevante Netzplanungsprobleme von einem Tag auf wenige Stunden reduziert werden. Dieser Vortrag basiert sich auf gemeinsame Arbeiten mit Sebastian Orlowski und Christian Raack im Auftrag von Nokia Siemens Networks.

We will introduce a multi-resolution approximation (MRA) approach to the study of smooth function extensions with application to image inpainting. Solution of the Dirichlet problem relative to some “Sturm-Liouville” differential operator is used as the “ground level” of the MRA, and details in terms of “anisotropic” differential boundary data are filled in, according to the desirable number of higher-resolution levels. An error formula, in terms of the integral diffusion operators with the Green’s functions of the “anisotropic” differential operators as diffusion kernels, is formulated and applied to derive the order of approximations.

Stichworte : Inpainting, Anisotropie in der Bildverarbeitung,Wavelet-Shrinkage, Forward-backward Algorithmus.

Inpainting ist ein spezielles Interpolationsproblem in der Bildverarbeitung. Ziel ist es, unbekannte Bildregionen in einem (möglicherweise verrauschten) Bild wiederherzustellen. Für unseren neuen Inpainting Algorithmus kombinieren wir Ideen der anisotropen Regularisierung und Diffusion mit Haar-Wavelet Shrinkage. Es handelt sich hierbei um einen iterativen Algorithmus, bei dem in jeder Iteration zunächst ein Entrauschungsschritt durchgeführt wird, gefolgt von einem Korrekturschritt, in dem die Grauwerte im bekannten Teil des Bildes wieder zurückgesetzt werden. Die anisotropen Methoden, die im Entrauschungsschritt benutzt werden, erlauben es Kanten und Objekte im Bild besser wiederherzustellen. Wie in [1] kann der Algorithmus als ein ”Forward-backward splitting” Algorithmus zur Minimierung eines bestimmten Funktionals interpretiert werden. Wir zeigen die Konvergenz unseres Algorithmus, insbesondere die Existenz einer Minimalstelle des zugehörigen Funktionals. Dies ist eine gemeinsame Arbeit mit R. H. Chan (The Chinese University of Hong Kong) and G. Steidl (Universität Mannheim).

[1] J.-F. Cai, R. H. Chan, and Z. Shen. A framelet-based image inpainting algorithm. Applied and Computational Harmonic Analysis, to appear.

Ein klassischer Ansatz zur Lösung nichtlinearer Optimierungsprobleme über binären Variablen ist die Linearisierung. Dazu werden zunächst neue Variablen eingeführt, die die nichtlinearen Terme modellieren; diese werden dann durch geeignete lineare Ungleichungen an die ursprünglichen Variablen gekoppelt. So entsteht ein lineares binäres Optimierungsproblem. Um dieses praktisch erfolgreich lösen zu können, etwa mit Schnittebenenverfahren, benötigt man eine gute Beschreibung des von allen zulässigen Lösungen aufgespannten Polytops. Da die Linearisierung aber üblicherweise für jede Variable einzeln geschieht, ist die entstehende Relaxierung meist schwach. Alternative Ansätze erreichen eine bessere Relaxierung, jedoch um den Preis einer stark vergrößerten Zahl von Variablen, was wiederum zu praktisch unlösbaren Problemen führt. Im Vortrag wird ein neuer Ansatz vorgestellt, der beiden Schwächen Rechnung trägt. Das allgemeine Problem wird durch Einführung weniger zusätzlicher Variablen auf ein quadratisches reduziert. Sofern das ursprüngliche Problem nur einfache (z.B. boolesche) Nebenbedingungen enthält, kann das resultierende quadratische Problem als unbeschränkt aufgefasst werden und ist somit zum Problem äquivalent, in einem Graphen einen maximalen Schnitt zu finden. Letzteres ist polyedrisch intensiv untersucht worden; alle Ergebnisse übertragen sich mithilfe der vorgestellten Reduktion automatisch auf das allgemeine Problem. Im Allgemeinen liefert die obige Reduktionsmethode allerdings ein beschränktes quadratisches Problem. Solche Probleme sind praktisch bereits sehr schwer zu lösen und wenig untersucht. Im zweiten Teil des Vortrags soll anhand eines Beispiels diskutiert werden, welche Effekte beim Übergang von einer linearen zu einer quadratischen Zielfunktion auftreten, und welche Lösungsansätze erfolgreich sein können. Zum Abschluss sollen außerdem einige Anwendungen der beschränkten quadratischen binären Optimierung vorgestellt werden, u.a. bei der Synthese digitaler Signale und bei der Steuerung von Motoren.

Algorithmen, die zum Finden der Lösung zufällige Ereignisse nutzen, sind seit über dreißig Jahren ein wichtiger Bestandteil der diskreten Algorithmik. Für viele Probleme sind solche randomisierten Algorithmen die derzeit beste bekannte Lösungsmethode. Zusätzlich überzeugen sie durch ihre strukturelle Einfachheit. Häufig genügt es sogar, alle Einzelentscheidungen stochastisch unabhängig zu treffen. Neuere Ergebnisse allerdings deuten darauf hin, dass ein wohldosierter Einsatz von Zufall oft zu bevorzugen ist. In meinem Vortrag möchte ich dieses anhand von zwei Beispielen aus dem Broadcasting in Netzwerken und dem randomisierten Runden erläutern.

Die Untersuchung von ``dünnen`` Lösungen von linearen Gleichungssystemen, d.h. Lösungen mit möglichst wenigen Nicht-Nullelementen, ist in der letzten Zeit ein viel untersuchtes Thema in unterschiedlichen Forschungsbereichen, insbesondere in der Signalverarbeitung unter dem Stichwort ``Compressed Sensing``. Die grundsätzliche Thematik ist die Repräsentation eines Punktes (rechte Seite) durch ein Erzeugendensystem (Spalten der Matrix). Je dünner die Lösungen desto besser für die Anwendungen. Obwohl dieses kombinatorische Optimierungsproblem NP-schwer ist, können unter bestimmten Voraussetzungen optimale Lösungen mittels eines linearen Optimierungsproblems gefunden werden. Der Hauptschwerpunkt des Vortrags liegt in der Darstellung des Beitrages den diskrete Optimierungsmethoden für dieses Problem liefern können. Insbesondere soll der Zusammenhang mit der Analyse von unzulässigen linearen Ungleichungssystemen hergestellt und die hierfür bekannten polyedrischen Erkenntnisse bzw. Lösungsverfahren diskutiert werden. Am Ende möchte ich kurz auf die Anwendung dieser Methoden bei der adaptiven Verfeinerung von Finite-Elemente-Gittern zur Lösung von partiellen Differentialgleichungen eingehen.

Interessante topologische und geometrische Eigenschaften geschlossener glatter Mannigfaltigkeiten hängen entscheidend von der Geometrie ``im Großen`` ihrer universellen Überlagerungen ab. Dabei nehmen wir die Perspektive eines weit entfernten Beobachters ein und sehen von lokalen topologisch-geometrischen Eigenschaften der universellen Überlagerungen ab. Wir diskutieren dieses Zusammenspiel anhand einiger neuerer Ergebnisse.