Research Seminar

The M9 Research Seminar is a weekly seminar in which our guests as well as our group discuss recent research advances and interesting open problems in applied geometry and discrete mathematics.

Usual time: Monday 15:15

Usual room: 02.04.011

Past and Upcoming Talks

Date Speaker Title
Mar 13, 2017, 14:00 Tina Schmidt tba
Feb 27, 2017, 14:45 Wolfgang Riedl tba
| Feb 21, 2017, 14:00 | Tina Schmidt | [[#AnchorAb201702211400][Approximation des Minimum k-Section Problems in Bäumen mit linearem Durchmesser]] |
Feb 20, 2017, 14:00 Tina Schmidt Über die Struktur von Bäumen ohne kleine Bisektion
Jan 23, 2017, 14:00 Yossi Luzon (Technion) tba
Dec 19, 2016, 14:00 Michele Garraffa (Université Paris 13) An Exact Exponential Branch-and-Merge Algorithm for the Single Machine Total Tardiness Problem
Dec 07, 2016, 13:00 Matthias Silbernagl tba
Dec 07, 2016, 11:00 Jiehua Chen (TU Berlin) Teams in Online Scheduling Polls: Game-Theoretic Aspects

Abstracts

Tina Schmidt

Wolfgang Riedl

Tina Schmidt: Approximation des Minimum k-Section Problems in Bäumen mit linearem Durchmesser

Minimum k-Section bezeichnet das Problem, die Knotenmenge eines gegebenen Graphen in k gleich große Klassen aufzuteilen, sodass die Anzahl der Kanten zwischen diesen Klassen kleinst möglich ist. Selbst für Bäume auf n Knoten ist es NP-schwer, eine optimale Lösung des Minimum k-Section Problems bis auf einen Faktor von n^c zu approximieren, für jedes beliebige c<1. Ziel dieses Vortrags ist es zu zeigen, dass jeder Baum T auf n Knoten eine k-Sektion der Weite (k-1) (2 + 16n / diam(T)) * Delta(T) erlaubt. Diese Schranke impliziert einen polynomialen Algorithmus, der für Bäume mit beschränktem Grad und linearem Durchmesser eine optimale Lösung des Minimum k-Section Problem bis auf einen konstanten Faktor approximiert. Außerdem wird erläutert, wie die Methoden mit Hilfe von Baumzerlegungen verallgemeinert werden können.

Tina Schmidt: Über die Struktur von Bäumen ohne kleine Bisektion

Titel: Über die Struktur von Bäumen ohne kleine Bisektion

Eine Bisektion eines Graphen ist eine Partition seiner Knotenmenge in zwei gleich große Klassen, wobei die Weite angibt, wie viele Kanten des Graphens zwischen diesen Klassen verlaufen. Minimum Bisection ist das NP-schwere Problem, in einem gegebenen Graphen eine Bisektion mit kleinst möglicher Weite zu finden. Ziel dieses Vortrags ist es, die Struktur von Bäumen mit beschränktem Grad, die keine Bisektion mit konstanter Weite erlauben, zu untersuchen. Zuerst wird gezeigt, dass Bäume auf n Knoten mit einem Pfad der Länge n/4 eine Bisektion mit konstanter Weite erlauben. Danach wird erläutert, wie diese Ideen für beliebige Bäume verallgemeinert werden können um Bisektionen zu konstruieren, deren Weite vom Durchmesser des Baumes abhängt. Dies wiederum kann mit Hilfe von Baumzerlegungen für beliebige Graphen verallgemeinert werden.

Yossi Luzon (Technion)

Title: Scheduling and Control of Two Fundamental Processing Systems

Yossi Luzon, Ph.D Dept. of Industrial Engineering, Tel Aviv University, Israel

Abstract: Scheduling is a decision-making process that exists in most manufacturing and production systems as well as in most information-processing environments. It also exists in transportation and distribution settings and in other types of service industries. In this talk we discuss two fundamental scheduling problems; one is motivated by the most modern manufacturing processing platform, while the other deals with a well-established problem, first introduced back in the 1950s, and since then have been attracting researchers’ attention as a basic element of various manufacturing systems. The first scheduling problem that we study considers an Additive Manufacturing (AM) process. The term additive manufacturing is used to describe the most recent manufacturing technologies in which successive layers of matter are formed to create an object, e.g., 3D printing. The involvement of AM processes in mass-production increases rapidly and the importance of their operational analysis becomes evident. Since AM processes are more flexible than in traditional manufacturing, the search for their best schedule is essential for their effectiveness. In this talk we will addresses the problem of scheduling an AM process, while considering its particular properties. Due to a complex combination of hardware, software and matter that take part in their implementation, AM processes are subject to failures. The time of a consequent failure is significantly affected by the system past performance. In addition, if a failure occurs during the printing of an object, then its printing will repeat from the start as the work resumes. We model an AM process by considering a sequence of uptimes and downtimes which are assumed independently and identically distributed (i.i.d) random variables of general distributions, and incorporate the process age, which indicates the time since the system last recovery. We also present and analyze a more complicated model where work may arrive over time. The formalization of two main measures of a given schedule is developed and proved: the expected completion-time (i.e., the time required to complete the processing of all jobs), which also refers to the expected system utilization, and the expected flow-time, which indicates the expected time a job spends in the system. Our formalization enables the search for a schedule that minimizes these measures for any uptime and downtime distributions. For exponentially distributed uptimes, closed form expressions for the two measures are derived. The next problem we consider involves one of the earliest machine environments ever studied in scheduling theory, the flow-shop network (FSN). In this talk we will suggest a new, intuitive, and simple method for scheduling jobs in a two server FSN with the minimum makespan objective. Multiple types of jobs with corresponding constant service times arrive at the network at various times over a finite time interval. An analog fluid network is proposed and its optimal fluid control policy determined. We make use of this optimal control policy to suggest a new method for scheduling jobs in the original discrete FSN and prove its asymptotic optimality. The method is particularly attractive because it falls into the class of easy-to-implement and computationally inexpensive on-line algorithms. Numerical simulations are used to evaluate the performance of the suggested method and show that it performs optimally in almost all simulated instances. Some additional properties of the network are discussed and illustrated.

Host: Andreas S. Schulz

Michele Garraffa (Université Paris 13): An Exact Exponential Branch-and-Merge Algorithm for the Single Machine Total Tardiness Problem

Abstract: The design of exact methods for NP-hard combinatorial optimization problems has always been a challenging issue. Researchers have focused on the design of practical methods for years, such as branch-and-bound algorithms, in order to solve instances whose size is as large as possible. Although these methods may work well in practice, their general worst-case complexity usually coincides with the one obtained by enumerating all the feasible solutions. An alternative research direction consists in finding the best exact algorithm with respect to the worst case complexity. The origin of this research field dates back to the 60s, but recent progress regarding the development of new techniques have led to many important theoretical results. In spite of the growing interest on the field, few results are yet known for NP-hard scheduling problems. This work proposes a branching algorithm for the single machine total tardiness problem, a classical scheduling problem where the aim is minimizing the sum of the jobs' tardiness. While the trivial enumeration of all the possible solutions has a time complexity of O(n!), we propose an exact algorithm whose time complexity converges to O*(2^n) and whose space complexity is polynomial. The proposed approach uses a brand new technique, called Branch-and-Merge, that is able to avoid the solution of redundant subproblems in the search tree. Branch-and-Merge is likely to be used to design exact exponential algorithms for other combinatorial problems with a similar structure. Furthermore, the proposed algorithm is somehow related with the best computational approach for solving the problem to optimality. Analogies and differences between the two approaches will be highlighted during the talk and the possibility to improve the computational results by means of the merging technique will be discussed.

Matthias Silbernagl

Jiehua Chen (TU Berlin): Teams in Online Scheduling Polls: Game-Theoretic Aspects

Title: Teams in Online Scheduling Polls: Game-Theoretic Aspects

Abstract: Consider an important meeting to be held in a team-based organization. Taking availability constraints into account, an online scheduling poll is used to decide upon the exact time of the meeting. Decisions are to be taken during the meeting, therefore each team wants to maximize its relative attendance in the meeting (that is, the proportional number of its participating team members).

We introduce a corresponding game, where each team can declare (in the scheduling poll) a lower total availability, in order to improve its relative attendance---the pay-off. We are especially interested in situations where teams can form coalitions:

1. We provide an efficient algorithm that, given a coalition, finds an optimal way for each team in the coalition to improve its pay-off. 2. In contrast, we show that deciding whether a coalition with improvement exists is NP-hard. 3. We also study the existence of Nash equilibria: Finding Nash equilibria for various small sizes of teams and coalitions can be done in polynomial time while it is coNP-hard if the coalition size is unbounded.

* This is a joint work with Robert Bredereck, Rolf Niedermeier, Svetlana Obraztsova, and Nimrod Talmon.