direkt zum Inhalt springen

direkt zum Hauptnavigationsmenü

Sie sind hier

TU Berlin

Page Content

There is no English translation for this web page.

Abstracts for COGA-Seminar WS 2014/15

Antje Lehmann: On variations of the facility location problem

We study facility location with exact, homogenous capacities, i.e., a facility location problem where each opened facility must have exactly k clients assigned to it. For a variant with exactly two or less than two clients, we give a polynomial time algorithm. For the variant with k greater or equal to three and metric assignment costs, we propose an approximation algorithm and analyse it. We give some hardness results, both for the metric and for the non-metric case. In addition, we show that if the Unique Games Conjecture is true, the non-metric version of the problem cannot be approximated within constant factor.

Zita Knódel: Verkehrslenkung mehrerer Fahrzeugklassen mit unterschiedlichen Mautgebühren

In einem Verkehrsnetz können zwei Gleichgewichte - das Nutzergleichgewicht und das Systemoptimum - gebildet werden. Das Nuztergleichgewicht ist erreicht, wenn kein Verkehrsteilnehmer seine Reisekosten durch Wahl eines anderen Weges verbessern kann. In einem Systemoptimum sind die für die Erfüllung der Verkehrsnachfrage benötigten Fahrzeiten minimal. Da durch die Minimierung der Gesamtfahrzeit Staus vermieden und Erdölressourcen eingespart werden können, ist das Systemoptimum der gesellschaftlich angestrebte Zustand. In der Arbeit wurde gezeigt, dass in jedem Mehrgüternetzwerk, mit heterogenen Nutzer und mehreren Fahrzeugklassen, das Systemoptimum mit Maut erzwingbar ist. Der konstruktive Beweis der Erzwingbarkeit des Systemoptimums gibt gleichzeitig eine Methode für die Berechnung der Maut an. Weiterhin wurde gezeigt, dass die Berechnung in poynomieller Zeit erfolgen kann.

Julia Kern: Optimal Routing in Congested Networks

We study the problem of finding an integer congestion minimizing routing in a directed network with homogeneous, non-linear costs. We distinguish different types of cost functions, namely linear, supermodular, submodular and arbitrary. Additionally we differentiate between three game types: In the asymmetric version each agent has an individual source-sink pair whereas for the single-source game all agents have a common source node and in the symmetric version all have a common source and sink node. The asymmetric problems are generalizations to the unsplittable multicommodity flow problem and the buy at bulk network design problem. We present hardness results and (approximation) algorithms on some of these cost and game type combinations (partly by Meyers and Schulz, 2012).

Theresa Thunig: Designing speed limits for good traffic equilibria

We study the design of traffic networks to influence selfish behavior by introducing speed limits on the streets. To model such a street network, we consider a directed graph in which the latency of an edge experienced by travelers is a non-negative, non-decreasing, and continuous function of its congestion. Users want to travel from a source vertex s to a destination vertex t and are assumed to selfishly and non-cooperatively choose their minimum latency path. We analyze the quality of such a routing, which is given by the sum of all travel times, also called the total latency. It is well known that selfishly routing users do not minimize the total latency. Therefore, our goal is to slightly change latency functions of the network, such that the total latency of selfish routing improves.

In this thesis, we allow to increase latency functions by introducing speed limits and, thus, new minimal travel times on the edges of the network. Since such a speed limit is able to disperse all the users from an edge by increasing its latency sufficiently, speed limits are a generalization of Roughgarden’s edge removals from 2006.

We compare the power of both network design variants and show that their maximum possible benefit is the same, although there are examples where speed limits are more powerful than edge removals. Furthermore, we show that speed limits, which are more powerful than edge removals, are not able to force the minimum possible total latency. Additionally, we characterize the maximum graph class where speed limits as well as edge removals are not able to improve the total latency independently of latency functions: It is the class of series-parallel graphs. Finally, we analyze the approximability of computing optimal speed limits and show that this problem is NP-hard.

Stanley Schade: Robust Location Planning

We consider the location planning problem, which models the supply chain of a company. It is a network flow model that aims to minimize the costs caused by purchase, production and transportation for given customer demands. Since the demands are likely to change over time, we apply adjustable robust optimization methodology and consider the demands as uncertain. In our case, each demand may vary within a given interval and a parameter gamma is used to limit the conservativeness of the obtained solutions.

The resulting problem can be solved using an LP-formulation. As the number of variables and constraints of this formulation is usually big, we discuss an alternative method by Thiele, Terry and Epelman (2009). They use a cutting plane technique that stems from convex optimization. The main problem that arises in their method is to solve the adversarial problem, which is solved using mixed-integer linear programming. We show that this problem is NP-complete in general.

Michael Kreutz: Flows over time and maintenance of arcs

In this thesis we consider the MaxTFFAO Problem, an optimization problem that combines elements from both network flow problems and scheduling problems. We are given a directed graph G with a source s and a sink t and capacities u, a list of maintenance jobs J and a discrete time horizon T. A maintenance job has a processing time and a time window in which it has to be processed on an associated arc without preemption. During the time interval of maintenance the capacity on the associated arc reduces to zero, prohibiting any flow to be carried along this arc. We are interested in scheduling the jobs such that we find a maximum s-t-flow over time with time horizon T in the resulting network. In general this problem is NP-hard. Here we restrict the MaxTFFAO Problem to different special cases and discuss their complexity. We concentrate on the special case where the underlying network is an s-t-path and develop an efficient algorithm that uses dynamic programming techniques in order to solve this problem under the additional restriction that all jobs have the same processing time. In addition, we relax this restriction and consider non-equal processing times where the jobs can be ordered such that both the release times and the deadlines of the jobs are strictly increasing. We conjecture that our algorithm solves this subproblem efficiently. Finally, we consider the MaxTFFAO Problem where the underlying network is an s-t-path and the jobs have an arbitrary structure and show an efficient algorithm that solves this problem in the case where the jobs can be preempted.

Julia Kern: Welfare Optimization in Congested Networks

We study the problem of finding an integer congestion minimizing routing in a directed network with homogeneous, non-linear cost functions. Each player has a designated source and sink node and needs to be routed in a non-splittable manner. The task of finding an optimal solution to the directed network congestion game generalizes various NP-hard problems like integer multi-commodity flow, Steiner tree and buy-at-bulk network design. In this talk we present a proof of a pseudo-polynomial 3-approximation for general quadratic cost functions. Furthermore we give a review on various cost types including constant, linear and supermodular functions.

This extends the results of Meyers and Schulz [2012] and is especially interesting since (exact, unweighted) finite games can be represented as integer network congestion games [Milchtaich, 2013].

Nadja Eberhardt: The unrooted set covering connected subgraph problem differentiating between HIV envelope sequences

HIV ist nach wie vor eine tödliche Krankheit, für die derzeit weder eine passive noch eine aktive Impfung existiert. Das Paper von Maher und Murray untersuchte daher die Gensequenzen der Hülle von HI-Viren. Ziel war es, Genbereiche zu identifizieren, die für eine passive Impfung in Frage kommen. Dafür wurde aus den Gensequenzen von insgesamt 266 Patienten ein Graph erstellt, der, nach Anwendung des unrooted set covering connected subgraph problems, jene Sequenzpositionen enthält, die bei einer Impfung angesteuert werden sollten. Das unrooted set covering connected subgraph problem kann in zwei Unterprobleme geteilt und mithilfe der Benders' decomposition gelöst werden. Am Ende soll auf zwei mögliche Erweiterungen des Papers in Form meiner Masterarbeit eingegangen werden.

Zusatzinformationen / Extras

Quick Access:

Schnellnavigation zur Seite über Nummerneingabe

Auxiliary Functions

This site uses Matomo for anonymized webanalysis. Visit Data Privacy for more information and opt-out options.