TU Berlin

FG Kombinatorische Optimierung und GraphenalgorithmenAbstracts COGA-Seminar

COGA 5-Wheel

Inhalt des Dokuments

zur Navigation

Abstracts for COGA-Seminar SS2014

René van Bevern: Fixed-Parameter Linear-Time Algorithms for NP-hard Graph and Hypergraph Problems Arising in Industrial Applications

We show fixed-parameter linear-time algorithms for optimally solving large instances of various NP-hard graph and hypergraph problems arising in industrial applications. Fixed-parameter linear-time algorithms are algorithms that run in linear time when certain parameters of the input instances are constant.

More specifically, we develop fixed-parameter linear-time algorithms and linear-time executable data reduction and experimentally evaluate them for the following problems.

- Independent Set on 2-union graphs, which models various scheduling tasks.

- Dag Partitioning, which is used in observing the rise and fall of trends, ideas, and topics on the internet.

- Hitting Set, which is applied in fault diagnosis and can be applied in noise-free radio frequency allocation.

We complement our algorithmic results by lower bounds on the running time of exact algorithms and on the effectiveness of data reduction.

Finally, we present a general method to derive linear-time algorithms for hypergraph problems on hypergraphs whose incidence graphs have constant treewidth.

Max Klimm: Optimal Impartial Selection

We study the problem of selecting a member of a set of agents based on nominations by agents from that set. A selection mechanism is called impartial if the nominations of an agent do not influence the probability of selecting it. Designing impartial mechanisms is an important problem with applications in situations where representatives are selected from within a group or where publishing or funding decisions are made based on a process of peer review. Alon et al. (2011) conjecture that it is possible to impartially select a member with in expectation at least half the maximum number of nominations. We give a randomized mechanism that achieves this ratio thus proving their conjecture. Subject to impartiality, the factor of 1/2 is best possible. (Joint work with Felix Fischer)

Roman Rischke: Two-Stage Scheduling on Unrelated Machines

We consider a natural model for two-stage scheduling on unrelated machines in which reserving a time unit for processing jobs incurs some cost. This cost depends on the time at which the reservation is made: a priori decisions, based only on distributional information, are much cheaper than on-demand decisions made when the actual scheduling scenario is known. Such a model captures for example the resource provisioning problem that users of cloud computing services face.

Our main contribution is an LP-rounding based (8+ε)-approximation algorithm for both the stochastic and the robust version of this problem with a polynomial number of scenarios. The key ingredient is a separation of jobs and time slots to be considered in either the first or the second stage only. (Joint work with Lin Chen, Nicole Megow, and Leen Stougie)

Jannik Matuschke: Fare evasion in transit networks

Fare evasion in public transit systems causes significant losses to society. In order to decrease evasion rates and minimize these losses, transportation companies conduct on-board inspections to check traveling passengers for a valid ticket. In this talk, we will discuss several variants of a new model for optimizing the distribution of fare inspections within the network.

The model is based on a bilevel program, where in the first level, the leader (the network operator) determines probabilities for inspecting passengers at different locations, while in the second level, the followers (the fare-evading passengers) respond by optimizing their routes for given inspection probabilities and travel times. We present exact, approximate, and heuristic algorithms for the followers' and the leader's problem. We also prove a tight bound on the ratio of the optimal cost between an adaptive and a non-adaptive version of the followers' behavior. Finally, we present the results of an extensive computational study on instances of the Dutch railway and the Amsterdam subway network, showing that our solutions are within 95% of upper bounds derived from an LP relaxation.

This is joint work with José R. Correa, Tobias Harks, and Vincent J.C. Kreuzen.

Martin Skutella: New results for the ring loading problem

The Ring Loading Problem is an optimal routing problem arising in the planning of optical communication networks which use bidirectional SONET rings. In mathematical terms, it is an unsplittable multicommodity flow problem on undirected ring networks. We prove that any split routing solution to the Ring Loading Problem can be turned into an unsplittable solution while increasing the load on any edge of the ring by no more than +1.4 D, where D is the maximum demand value. This improves upon a classical result of Schrijver, Seymour, and Winkler (1998) who obtained a slightly larger bound of +1.5 D. We also present an improved lower bound of +1.1 D (previously +1.01 D) on the best possible bound.

Benjamin Müller: Online Algorithms for Deadline Scheduling Problems to Minimize the Number of Machines

We consider a fundamental problem of Online Deadline Scheduling in a preemptive multiprocessor setting. Each job has a release date, deadline and a processing time. Our goal is to schedule all jobs in their time windows with as few machines as possible. To compare online algorithms for this scheduling problem we use the definition of the competitive ratio.

Our contributions are new and improved bounds on the competitive ratio for special subproblems. We show a load based technique to derive upper bounds for the case of unit and equal processing times. Additionally, we introduce a black box algorithm which transforms an online algorithm which uses the knowledge of the optimal offline value to one for the general problem. The competitive ratio increases by a factor of 4 in a deterministic and a factor of e in a randomized analysis.

Stanley Schade: Location planning under uncertainty

Assume that a company wants to build factories of different sizes in predetermined places in order to provide several target countries with their products. Our objective is to determine the sizes of these factories, such that the costs for purchasing raw materials, transport and the operating costs of the factories are minimal.

In the introductory talk for my master's thesis I will explain a linear model for the problem stated above, discuss the motivation for introducing uncertainty and briefly mention first ideas how to incorporate it into the model.

Sebastian Kamprath: Paralleles Sortieren in Stapelnetzwerken mit linearer Substruktur

Beim 1D Parallel Stack Sorting Problem muss eine Folge von eingehenden Elementen mittels einer Menge von Stapeln sortiert werden. Eine der Schwierigkeiten ist, dass sich sortierende Maschinen den Transportweg teilen und kollidieren können. Ziel ist es, möglichst schnell die Zielsequenzen zu erstellen. Solche Probleme treten in Zwischenlagern bei der Produktion von Stahlblechen auf, aber auch Containerlager und Verladeplätze in Schiffshäfen sind Beispiele dafür.

Es wird gezeigt, dass das Problem NPSPACE-schwer ist und somit kaum Hoffnung auf einen effizienten und optimalen Algorithmus besteht. Um dennoch Lösungen zu berechnen wird eine heuristische Graphenexploration vorgestellt. Anhand von Realdaten konnten für verschiedene Arten von Beispielen instanzabhängige Güten produziert und analysiert werden.

Felix Simon: Algorithmic Study of Bilevel Machine Scheduling Problems

In this thesis we consider the Bilevel Weighted Completion Time Problem, a bilevel machine scheduling problem on parallel identical machines. The task in bilevel optimization is to optimize the problem of a top level decision maker, while taking the subsequent reaction of a bottom level decision maker into account. For this reason it can be applied to many real world planning problems with hierarchical structures.

We will give some structural results for the problem and present several approaches for achieving approximation algorithms. These include a fully polynomial-time approximation scheme (FPTAS) for the case of a fixed number of machines and different algorithms processing the job in the order of a given list. Furthermore we generate solutions based on solving the one-level Weighted Completion Time Problem. Additionally an integer programming (IP) and an integer quadratic programming (IQP) formulation for the problem are given.

Fabian Wegschneider: Dynamic Bin Packing – Theory And Computational Experiments

Given a set of items with sizes between 0 and 1, the (one-dimensional) Bin Packing Problem is to store these items in as few bins of unit-capacity as possible. Since the early 70’s a lot of approaches to solve the BPP have been studied, as it models a number of problems in computer science and industry. A generalization of it, called the Dynamic Bin Packing Problem, allows for some items to be unpacked during the packing process. In other words, in the dynamic version, a list of stations has to be dealt with at each of which some already packed items are to be unloaded while new items have to be added to the bins.

While the classical Bin Packing Problem has been well studied in the past, not quite as much attention has been paid to its dynamic variant, with a particular lack of computational experiments. In this talk I will briefly summarize the content of my bachelor thesis, which includes an overview of important theoretic results for both of the problems and a presentation of the results obtained by computational experiments with algorithms for the dynamic version.

Andreas Wiese: Approximation Schemes for Maximum Weight Independent Set of Rectangles

In the Maximum Weight Independent Set of Rectangles (MWISR) problem we are given a set of n axis-parallel rectangles in the 2D-plane, and the goal is to select a maximum weight subset of pairwise non-overlapping rectangles. Due to many applications, e.g. in map labeling and admission control, the problem has received a lot of attention by various research communities. We present the first (1+eps)-approximation algorithm for the MWISR problem with quasi-polynomial running time 2^poly(log n/eps). In contrast, the best known polynomial time approximation algorithms for the problem achieve superconstant approximation ratios of O(loglog n) (unweighted case) and O(log n/loglog n) (weighted case).

Key to our results is a new geometric dynamic program which recursively subdivides the plane into polygons of bounded complexity. We provide the technical tools that are needed to analyze its performance. In particular, we present a method of partitioning the plane into small and simple areas such that the rectangles of an optimal solution are intersected in a very controlled manner. Together with a novel application of the weighted planar graph separator theorem due to Arora et al. this allows us to upper bound our approximation ratio by 1+eps.

Jan Hackfeld: Solving the matching extension problem

A simple graph G with 2n vertices is said to be k-extendable for an integer k with 0 < k < n if G contains a perfect matching and every matching of cardinality k in G can be extended to a perfect matching. The focus of the talk will be the algorithmic aspect of the problem, that is, deciding for given graphs if they are k-extendable or not. It will be shown that this problem is coNP-complete. Moreover, an integer program solving the problem is analysed.

Michael Kreutz: Flows over time and scheduling maintenance on arcs

Given a capacitated network, a planning time horizon and a list of maintenance jobs, the objective of this problem is to schedule the maintenance jobs on arcs so as to maximize the total flow that can be transported by the network over the given time horizon. Maintenance on an arc shuts down the arc for the duration of the periods in which the maintenance is scheduled, making its capacity zero for those periods. This problem has been studied in the context of maintaining an australian coal chain system comprising load points, rail tracks and different types of terminal equpiment.

In this introductory talk to my master thesis I will

  • state a problem formulation and discuss several modifications of the problem (i.e. add transit times on arcs, add storage at nodes),
  • give an overview of complexity results on this problem for different network classes,
  • discuss possible outlines of my further work.

Navigation

Direktzugang

Schnellnavigation zur Seite über Nummerneingabe