TU Berlin

Combinatorial Optimization & Graph Algorithms group (COGA)Abstracts COGA-Seminar

COGA 5-Wheel

Page Content

to Navigation

There is no English translation for this web page.

Marko Lehmann: Ein O(n log n) Algorithmus für die Berechnung maximaler s,t-Flüsse in gerichteten planaren Graphen

In der vorliegenden Arbeit betrachten wir einen gerichteten planaren Graphen mit n Knoten und suchen einen maximalen Fluss von einem Quellknoten s zu einem Zielknoten t. Für die Lösung des Problems stellen wir den Algorithmus mit einer Laufzeit von O(n log n), entwickelt von Glencora Borradaile und Philip Klein, vor. Zunächst wird mittels einer Kürzesten-Wege-Berechnung, ausgehend von einem Quellknoten, im dualen Graphen eine Zirkulation ermittelt, um Kreise im Uhrzeigersinn zu entfernen. Anschließend wird über den am weitesten links gelegenen s, t-Weg im Residualgraph sukzessive ein Fluss geschickt.
Der Algorithmus bricht ab, wenn kein gerichteter s, t-Weg im Residualgraph mehr vorhanden ist. Wir erhalten als Output einen s, t-Fluss mit maximalen Flusswert.

Benjamin Müller: Das Connected Facility Location Problem mit baumförmigen Zugangsnetzen

Das Connected Facility Location Problem mit baumförmigen Zugangsnetzen (CFL-T) ist ein diskretes Optimierungsproblem aus dem Bereich Network Design. In diesem Problem werden Kunden über mehrere Bäume mit ausgewählten Facilities verbunden, so dass der Bedarf jedes Kunden gedeckt wird. In einer zulässigen Lösung des Problems wird gefordert, dass die Bäume bezüglich einer Kostenfunktion tiefenbeschränkt sind und dass die Bäume nur eine maximale Einheit an Gütern durch das Netzwerk transportieren können.
In meinem Vortrag werde ich auf die Komplexität dieses Problems eingehen und zeigen, dass das Problem NP vollständig ist und mit Hilfe kombinatorischer Ideen, einen Approximationsalgorithmus vorstellen, der eine konstante Güte garantiert.

Sabine Werner: Robuste Optimierung über Matroiden und ganzzahligen Polymatroiden

Ein Matroid ist eine Struktur, die den Begriff der linearen Unabhängigkeit verallgemeinert. Wenn man jeder der sogenannten unabhängigen Mengen dieser Struktur ein Gewicht zuordnet, kann man nach Basen (inklusionsmaximalen unabhängigen Mengen) minimalen oder maximalen Gewichts suchen. Polymatroide sind nun eine Verallgemeinerung von Matroiden in dem Sinn, dass das induzierte Polytop eines Matroids gerade ein Polymatroid ist. Wir wollen diese beiden linearen Optimierungsprobleme auf Robustheit gegenüber unsicheren Daten untersuchen. Dafür wird hier der Begriff der Gamma-Robustheit verwendet, das heißt dass sich höchstens gamma-viele Gewichte verändern können.

Jannik Matuschke: Degree-constrained orientations of embedded graphs

(joint work with Yann Disser)
We consider the problem of orienting the edges of an embedded graph in such a way that the in-degrees of both the nodes and faces meet given values. We show that the number of feasible solutions is bounded by 22g, where g is the genus of the embedding, and all solutions can be determined within time O(22g|E|2 + |E|3). In particular, for planar graphs the solution is unique if it exists and for every fixed genus there is a polynomial time algorithm to find all solutions. We show that the problem becomes NP-complete if only upper and lower bounds on the in-degrees are specified instead of exact values.

Ashwin Arulselvan: A branch-and-cut algorithm for Incremental Connected Facility Location Problem

(Joint work with Andreas Bley and Ivana Ljubic)

In an incremental connected facility location problem, we are given a set of potential facilities, a set of interconnection nodes, a set of customers with demands and a planning horizon. In each time period, we are required to determine the set of customers served along with their serving facilities and the interconnection between the currently open facilities. The objective is to maximise the net present value, which is given by the discounted revenue and costs involved. We model the problem as an integer program and present some valid inequalities to strengthen the model. We also study some exact and heuristics procedures for the separation routine. We briefly discuss a lifting procedure to strengthen these inequalities. We finally present the computational results of our implementation.

Veronika Günther: Flussalgorithmen zur Optimierung der Grünflächenversorgung in Großstädten

Die Qualität einer Großstadt lässt sich mit Hilfe vieler verschiedener Kriterien beschreiben. Eines ist die Versorgung der Einwohner mit Grünflächen im Naherholungsbereich oder anders: Wie viel Quadratmeter Grünfläche stehen einem Einwohner im Umkreis von höchstens 1500 Metern zur Verfügung?

Meine Diplomarbeit beinhaltet eine Analyse des Ist-Zustandes unter verschieden Aspekten, wie z. B. die Entfernung oder die Auslastung der Grünflächen. Diese so entstandenen Probleme lassen sich als Netzwerke auf Graphen mathematisch modellieren und mittels kombinatorischer Flussalgorithmen mit z. B. konvexen Kostenfunktionen lösen. Zudem wird die Qualität der erhaltenen Ergebnisse analysiert.

Mathias Weller: Interval Scheduling and Colorful Independent Sets

The Independent Set problem is to determine for a given graph G and an integer k whether G contains a set of k pairwise non-adjacent vertices. The problem has numerous applications in scheduling, such as resource allocation and steel manufacturing. There, one encounters restricted graph classes such as 2-union graphs, which are edge-wise unions of two interval graphs on the same vertex set, or strip graphs, where additionally one of the two interval graphs is a disjoint union of cliques. We prove NP-hardness of Independent Set on a very restricted subclass of 2-union graphs and identify natural parameterizations to chart the possibilities and limitations of effective polynomial-time preprocessing (kernelization) and fixed-parameter algorithms. Our algorithms are of practical interest and benefit from novel formulations of the computational problems in terms of (list-)colored interval graphs, which give the problems a more combinatorial than geometric flavor.

Judith Simon: Effiziente Implementierung des Netzwerk-Simplex-Algorithmus mit Hilfe dynamischer Baeume

Der Netzwerk-Simplex-Algorithmus ist einer der wichtigsten Algorithmen im Bereich der Optimierung und ein Spezialfall der "klassischen" Simplex-Methode. Unter Anderem löst dieser das Max-Flow-Problem, für das bereits zahlreiche Algorithmen entwickelten wurden, die eine immer schnellere Laufzeit aufweisen. Diese hängt in hohem Maße von der gewählten Pivot-Regel ab. In meinem Vortrag stelle ich eine Pivot-Regel von D. Goldfarb und J. Hao vor, mit der der Algorithmus maximal nm Pivot-Schritte benötigt. Basierend auf dieser Pivot-Regel kann man die Laufzeit des Netzwerk-Simplex-Algorithmus mit Hilfe der von D. Sleator und R. Tarjan entwickelten dynamischen Baeume verbessern.

Stefan Schmid: CloudNets: Combining Clouds with Networking

This talk provides an overview of the CloudNet project at Telekom Innovation Laboratories in Berlin. The CloudNets project envisions an Internet where arbitrarily specified virtual networks can be requested at short notice to connect cloud resources (such as storage or CPU) in a manner that provides QoS guarantees. I will present some use cases for CloudNets and will discuss the different stakeholders (and possible business opportunities) in such an Internet. Interestingly, although the presented architecture constitutes a clean-slate approach in the sense that it requires core networking support, it can be incrementally deployed (e.g., in a single ISP or between two collaborating ISPs). The talk will also include a short demo of our current prototype architecture.

The main algorithmic challenges of our architecture concern the access control, the embedding, and the migration of CloudNets. Due to the uncertainty of the demand for CloudNets and its resources, we pursue an online algorithm and competitive analysis approach for these problems. I will sketch an online access control scheme based on Naor and Buchbinder’s online primal-dual framework that achieves a low competitive ratio in the sense that our algorithm accepts only the high-benefit CloudNets. Moreover, I will sketch online algorithms for virtual service migration in an intra- and an inter-provider setting; these algorithms perform well in the worst-case and without relying on any kind of demand prediction and oracle models.

This is joint work with T-Labs (group of Anja Feldmann), NTT DoCoMo (group of Wolfgang Kellerer), Marcin Bienkowski, Guy Even and Moti Medina.

S. Thomas McCormick: Separation of Series Constraints for One-Machine Scheduling with Precedence

by S. Thomas McCormick, A. Ridha Mahjoub, and Y. Kobayashi

A 1991 paper by Queyranne and Wang proposed three classes of valid constraints for the convex hull of feasible completion times for schedules on a single machine subject to precedence constraints. These classes are called the parallel constraints, serial constraints, and Z constraints. These constraints have been very useful in many contexts. Queyranne and Wang showed how to separate the parallel constraints, but the complexity of separating the serial and Z constraints has remained open. Here we show that it is NP Hard to separate even a very special subclass of serial constraints.  We also develop a fast, parametric way to find an earliest feasible deadline for a subset of jobs, and use it to show that separation is polynomial when the precedence constraints are series-parallel.  We also note that there is a compact extended formulation of the problem by Wolsey, and in this context separation of both series and parallel constraints becomes trivial.  It is surprising that an NP Hard separation problem can "hide" within an extended formulation where separation is much easier.  We further consider the case of two-dimensional precedence constraints, whose underlying problem is solvable in polynomial time.  We show how to separate the serial constraints in this case as well.

Marlen Schwengfelder: Modellierung von Gebäudestrukturen durch Graphen in der Evakuierungsplanung

Das ZET Evakuierungstool ist eine Software, mit der die Evakuierung eines Gebäudes berechnet und dargestellt werden kann. Realisiert wird dies durch die Kalkulation eines speziellen dynamischen Flusses, eines sogenannten Earliest Arrival Flows. Ausschlaggebend dabei ist der zugrundeliegende Graph, der die Struktur des Gebäudes möglichst gut abbilden soll. Das dafür bisher in ZET angewandte Verfahren baut Graphen auf, die durch eine Vielzahl an Kanten und Knoten gekennzeichnet sind. Da sich dies negativ auf die Laufzeit des genutzten Flussalgorithmus auswirkt, war das Ziel der Arbeit, einen kleineren Graphen zu erstellen, den Wert der Evakuierung dabei aber möglichst beizubehalten. Dazu wurden einerseits verschiedene Ansätze untersucht, die die Kanten- und Knotenanzahl des bestehenden Graphen reduzieren. Andererseits wurde ein Verfahren entwickelt, das den Graphen eines Gebäudes komplett neu aufbaut. Alle Konzepte wurden in der Arbeit sowohl theoretisch als auch empirisch analysiert. Im Vortrag soll ein Überblick über die dabei gewonnenen Erkenntnisse gegeben werden.

Hendrik Lüthen: On Matroid and Shortest Path Problems with Additional Precedence Constraints

In a weighted red-blue-colored matroid it is easy to find a minimum cost
basis that contains exactly k red elements (by a result from Gabow and
Tarjan). If precedence constraints are added this problem extends to
poset matroids and is not solvable in polynomial time.
In a weighted red-blue-colored graph it is easy to find a shortest path
that contains exactly k red edges via a modified Dijkstra-algorithm. But
again this problem becomes hard if we have an additional poset on the
edges and require the path to be an ideal, chain or antichain.
In the talk these and related problems (for example restricting the
poset) will be presented

Martin Groß: Approximating Earliest Arrival Flows in Arbitrary Networks

The earliest arrival flow problem is motivated by evacuation planning. It asks for a flow over time in a network with supplies and demands that maximizes the satisfied demands at every point in time. Gale [1959] has shown the existence of such flows for networks with a single source and sink. For multiple sources and a single sink the existence follows from work by Minieka [1973] and an exact algorithm has been presented by Baumann and Skutella [FOCS'06]. If multiple sinks are present, it is known that earliest arrival flows do not exist in general.

We address the open question of approximating earliest arrival flows in arbitrary networks with multiple sinks and present constructive approximations of time and value for them. We give tight bounds for the best possible approximation factor in most cases. In particular, we show that there is always a 2-value-approximation of earliest arrival flows and that no better approximation factor is possible in general. Furthermore, we describe an FPTAS for computing the best possible approximation factor along with the corresponding flow for any given instance (which might be better than 2).

This is joint work with Jan-Philipp Kappmeier, Daniel Schmidt (University of Cologne) and Melanie Schmidt (TU Dortmund)

Roman Rischke: Bepreiste Szenarien in der zweistufigen robusten kombinatorischen Optimierung

Bei der Anwendung der kombinatorischen Optimierung in der Praxis muss man sich häufig mit dem Problem der Datenunsicherheit auseinandersetzen. Messfehler, die nicht restlos ausgeschlossen werden können, und die Unfähigkeit, zukünftige Ereignisse mit Bestimmtheit vorherzusagen, sind beispielhafte Gründe dafür, dass die (nominalen) Eingangsdaten für ein kombinatorisches Optimierungsproblem in praktischen Anwendungen häufig mit Unsicherheit behaftet sind. In der Praxis müssen Entscheidungen also oft auf der Grundlage einer Menge von möglichen Szenarien getroffen werden. Ein etablierter Ansatz, mit dieser Datenunsicherheit umzugehen, ist die robuste Optimierung. Im Vortrag wird ein Einblick in die zweistufige robuste kombinatorische Optimierung gegeben und dabei wird insbesondere verdeutlicht, dass die bestehenden Konzepte ein gewisses Maß an "Willkür" bei der Wahl der Szenariomenge hervorrufen. Um dieser "Willkür" zu begegnen, wird im Vortrag das Konzept der bepreisten Szenarien für die zweistufige robuste kombinatorische Optimierung vorgestellt. Dieses neue Konzept wird anhand des zweistufigen robusten Weighted-Disjoint-Hitting-Set-Problems näher untersucht und den bestehenden Konzepten gegenübergestellt.

Daniela Luft: Single Machine Scheduling mit monomischer Zielfunktion in den Fertigstellungszeiten

Im betrachteten Single-Machine-Scheduling-Problem sind eine Maschine und eine endliche Menge von Jobs gegeben. Hierbei besitzt jeder Job eine gegebene Bearbeitungszeit und  ein gegebenes Gewicht. Zudem wird angenommen, dass die Bearbeitung eines Jobs nicht  unterbrochen werden darf.  Ziel ist es, eine Reihenfolge der Jobs auf der Maschine so zu bestimmen, dass die gewichtete Summe der Fertigstellungszeiten der Jobs minimal ist. Hierbei gehen die Fertigstellungszeiten aller Jobs monomisch (zum Beispiel quadratisch) in die Zielfunktion  ein. Um die Anordnungsmöglichkeiten der Jobs bei der Aufstellung eines optimalen Zeitplans zu verringern, existieren sogenannte Order Constraints.  Order Constraints sind hinreichende Bedingungen dafür, dass zwei Jobs in einer bestimmten Reihenfolge in einem optimalen Zeitplan auftreten.  Für das betrachtete Single-Machine-Scheduling-Problem mit quadratischen Kosten existieren bereits eine Reihe von Order Constraints, jedoch sind für den allgemein monomischen Fall kaum Resultate aus der Literatur bekannt.  Daher war es Teil meiner Arbeit zu untersuchen, ob sich die bekannten Order Constraints für quadratische Kosten auf den allgemein monomischen Fall übertragen lassen.  Im Rahmen der Arbeit wurde das betrachtete Single-Machine-Scheduling-Problem mittels SCIP und CPLEX exakt gelöst. Hierfür wurden unterschiedliche mathematische Formulierungen in Kombination mit Order Constraints aufgestellt und experimentell gegenübergestellt. 

Im Vortrag werden einerseits die betrachteten Formulierungen und Order Constraints und  andererseits die Resultate der experimentellen Untersuchung vorgestellt.

Berit Johannes: Robust Optimization and Sigma2p-Completeness

In this informal talk, I will give a brief introduction to the
complexity class Sigma2p and show that several robust optimization
problems are Sigma2p-complete.  Sigma2p lies one level above NP and
co-NP in the polynomial hierarchy, and Sigma2p-complete problems are
therefore at least as hard as NP-complete problems, if not harder.  I
will also show when and how NP-completeness proofs can be used to
generate completeness proofs for Sigma2p.  As a result, problems such
as "Does a given graph G contain a Hamiltonian cycle T such that all
other Hamiltonian cycles in G must have at least K edges with T in
common?" are Sigma2p-complete.

Ashi Yoshimoto (Institute of Statistical Mathematics, Tokyo, Japan): Spatial Concerns and Formulation for Harvest Scheduling in Forestry

Spatial concerns have been paid a great deal of attention since 1980's
in forestry.  The early application started to avoid harvesting
adjacent forest units in the same period subject to so-called
"Adjacency Constraints".  Many forest units were fragmented due to
this constraint. Since then, some unit aggregation was recommended to
reserve a certain sized-area for conserving wildlife habitat and
others.  Application of fragmentation and aggregation can be found in
many practices.  In this presentation, formulation techniques by
matrix notation are demonstrated to solve spatially constrained
harvest scheduling along with some applications.

Navigation

Quick Access

Schnellnavigation zur Seite über Nummerneingabe