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.

Abstracts for COGA-Seminar SS 2015

Christina Weibert: Das stochastische Rucksackproblem

Bei dem stochastischen Rucksackproblem (SRSP) ist ein Rucksack mit einer festen Kapazität sowie eine endliche Menge von Objekten gegeben, wobei jedes Objekt durch seinen Nutzen und seine Größe charakterisiert ist. Die Nutzen von Objekten sind deterministisch, aber die Größen sind unabhängige Zufallsvariablen mit einer bekannten Wahrscheinlichkeitsverteilung. Das bedeutet, dass die tatsächliche Größe eines Objektes im Voraus nicht bekannt ist. Erst nachdem ein Objekt dem Rucksack hinzugefügt wird, offenbart sich seine wirkliche Größe. Wir gehen davon aus, dass die Entscheidung zum Hinzufügen unwiderruflich ist. Wenn das Hinzufügen eines Objektes zu keiner Überfüllung des Rucksacks führt, so wird es als erfolgreiches Hinzufügen bezeichnet. Die Objekte werden nacheinander dem Rucksack solange hinzugefügt, bis es zum ersten Mal die Überschreitung der Kapazität festgestellt wird. Das Ziel ist, den erwarteten Gesamtnutzen dem Rucksack erfolgreich hinzugefügter Objekte zu maximieren.

Es ist bekannt, dass das klassische Rucksackproblem NP-schwer ist. Da das SRSP eine Verallgemeinerung des klassischen Rucksackproblems darstellt, ist das SRSP mindestens NP-schwer. Aus diesem Grund wird versucht, mit Approximationsalgorithmen eine möglichst nahe am Optimum liegende Lösung für das betrachtete Optimierungsproblem zu finden. Im Vortrag werden Resultate des Papers „Approximating the Stochastic Knapsack Problem: The Benefit of Adaptivity“ von Dean u. a. vorgestellt. Es wird insbesondere auf einen 4-Approximationsalgorithmus für das SRSP eingegangen. Der Beweis der Approximationsgüte wird ausführlich dargestellt.

Das SRSP lässt sich auf das korrelierte SRSP verallgemeinern, wenn man die Korrelationsbeziehungen zwischen den Größen und Nutzen von Objekten zulässt. Für dieses Optimierungsproblem wird ein randomisierter Approximationsalgorithmus angegeben, den man im Paper „Approximation Algorithms for Correlated Knapsacks and Non-martingale Bandits“ von Gupta u. a. findet. Anschließend wird gezeigt, dass seine Approximationsgüte gleich 8 ist.

Julie Meißner: MST under Uncertainty - randomized -

We study a network design model where uncertain data is given in the form of intervals and exact data can be explored at a cost. The goal is to find an optimal network minimizing the exploration cost. For the minimum spanning tree problem under uncertainty we present the first randomized algorithm that improves upon the known 2-competitive deterministic algorithms that are tight. We make use of a strong connection to online bipartite vertex cover to achieve a competitive ratio of roughly 1.707 in expectation.

Ágnes Cseh: Many-to-one matchings with lower quotas: Complexity and approximability

Imagine a project-based university course, where our task is to assign students to projects they will enjoy to work on. In the student-project allocation problem, or shorter, SPA, each student submits a list of their acceptable projects, and likewise, each lecturer provides a set of acceptable students to each of their projects. Moreover, some projects are equipped with upper and lower quotas regarding the number of students assigned to them. The quota requirement is strict: projects not reaching their lower quotas must be closed entirely. The challenge is to find a b-matching assigning the highest number of students.

This is a joint work with Ashwin Arulselvan, David Manlove and Jannik Matuschke. A preliminary version of the paper was presented last year at the MDS Statusworkshop, but this talk is essentially different due to new results.

Mahmoud Ragab: On the Convergence for the Number of Comparisons Needed by the Partial quicksort Process

In this Work we look at a version of sorting algorithms based on divide-and-conquer algorithms. The partial Quicksort algorithm, sorts l of unsorted list of length n distinct elements, l ≤ n. It is a version of the Unique pivot Quicksort, and both are stochastic divide-and-conquer algorithms, which widely studied. The survey discusses in detail some different variations of Quicksort starting with the original version developed by Hoare in 1961 and ending with some of the most recent ones. The study compared each algorithm in terms of the number of comparisons performed and the running times.The main object is to analyze the running time performance to do the job. The limiting distribution of the normalized number of comparisons required by the partial Quicksort algorithm is studied. It is known to be the unique fixed point of a certain distributional transformation T with zero mean and finite variance.

Philipp Skavantzos: Strictly fundamental cycle bases in graphs: Algorithms and complexity

The task of finding a strictly fundamental cycle basis of minimum weight (MSFCB) in an undirected graph G=(V,E) is NP-complete in general. A typical way to deal with such problems is to look at them regarding approximability. We present a proof for showing MSFCB is APX-hard. Thus, there exists no PTAS for this problem on arbitrary graphs. However, we can show that there is a PTAS for complete graphs. The basic idea for that proof is based on a similar result for the minimum routing cost spanning tree problem. These two major results are discussed in "On the approximability of the minimum strictly fundamental cycle basis problem". Furthermore, for cographs and series parallel graphs the complexity status of MSFCB is yet unknown. We give some first ideas on how to tackle this problem on these graph classes.

Navigation

Quick Access

Schnellnavigation zur Seite über Nummerneingabe