Abstract: Ist derzeit nicht verfügbar.

Abstract: Die lokale Suche in variabler Tiefe, von Kernighan und Lin vorgestellt, ist eines der erfolgreichsten Paradigmen für die schnelle Bestimmung guter Lösungen für das Graph Partitionierung und das Traveling Salesman Problem. Der für das Problem der Graph Partitionierung 1970 vorgestellte Algorithmus und seine 1973 vorgestellte Adaption für das Traveling Salesman Problem sind die Basis diverser Varianten und Verbesserungen. Obwohl die Laufzeiten der verschiedenen, auf dem Kernighan-Lin Paradigma basierenden Algorithmen im Detail untersucht wurden, so blieb die Approximationsleistung der beiden Verfahren bisher ungeklärt.
In diesem Vortrag stellen wir das Paradigma der lokalen Suche in variable Tiefe vor und besprechen abgeleitete Heuristiken und Erweiterungen. Desweiteren konstruieren wir planare Graphen mit N Knoten und Approximationsfaktor \Omega(N) für das Problem der Graphpartitionierung. Die Analyse belegt. dass der Kernighan-Lin Algorithmus für eine große Klasse von Graphen, beschrieben durch einige wenige Eigenschaften ebenfalls nur eine sehr schwache Approximationsleistung aufweist. Unsere Ergebnisse gelten bei zufälliger Wahl der Startzerlegung mit extrem hoher Wahrscheinlichkeit obwohl sogar intelligentes Tie-Breaking erlaubt ist. Abschließend werfen wir noch einen kurzen Blick auf empirische Ergebnisse, um die Schärfe der analytischen Schranke zu betonen.

Abstract: We propose a variation of online paging in two-level memory systems where pages in the fast cache get modified and therefore have to be explicitly written back to the slow memory upon evictions. For increased performance, up to $\alpha$ arbitrary pages can be moved from the cache to the slow memory within a single joint eviction, whereas fetching pages from the slow memory is still performed on a one-by-one basis. The main objective in this new $\alpha$-paging scenario is to bound the number of evictions. After providing experimental evidence that $\alpha$-paging can adequately model flash-memory devices in the context of translation layers we turn to the theoretical connections between $\alpha$-paging and standard paging. We give lower bounds for deterministic and randomized $\alpha$-paging algorithms. For deterministic algorithms, we show that an adaptation of LRU is strongly competitive, while for the randomized case we show that by adapting the classical Mark algorithm we get an algorithm with a competitive ratio larger than the lower bound by a multiplicative factor of approximately 1.7.

Abstract: We consider first-order formulas which, in addition to the symbols in the vocabulary, may use two designated symbols < and + that must be interpreted as a linear order and its associated addition. Such a formula is called addition-invariant if, for each fixed interpretation of the initial vocabulary, its result is independent of the particular interpretation of < and +. We study the expressive power of addition-invariant first-order logic, +-inv-FO, on the class of finite strings. Our first main result gives a characterization of the regular languages definable in +-inv-FO: we show that these are exactly the languages definable in FO with extra predicates, denoted by "lm" for short, for testing the length of the string modulo some fixed number. Our second main result shows that every language definable in +-inv-FO, that is bounded or commutative or deterministic context-free, is regular. As an immediate consequence of these two main results, we obtain that +-inv-FO is equivalent to FO(lm) on the class of finite colored sets. Our proof methods involve Ehrenfeucht-Fraissé games, tools from algebraic automata theory, and reasoning about semi-linear sets.

[This is joint work with Luc Segoufin.]

Abstract: Scheduling on related machines (Q||C_max) is one of the most important problems in the field of Algorithmic Mechanism Design. Each machine is controlled by a selfish agent and her valuation can be expressed via a single parameter, her speed. Archer and Tardos (FOCS01) showed that, in contrast to other similar problems, a (non-polynomial) allocation that minimizes the makespan can be truthfully implemented. On the other hand, if we leave out the game-theoretic issues, the complexity of the problem has been completely settled --- the problem is strongly NP-hard, while there exists a PTAS.

This problem is the most well-studied in single-parameter Algorithmic Mechanism Design. It gives an excellent ground to explore the boundary between truthfulness and efficient computation. Since the work of Archer and Tardos, quite a lot of deterministic and randomized mechanisms have been suggested. Recently, a breakthrough result of Dhangwatnotai et al. (FOCS08) showed that a randomized, truthful-in-expectation PTAS exists. On the other hand, for the deterministic case, the best known approximation factor is 2.8.

It has been a major open question whether there exists a deterministic truthful PTAS, or whether truthfulness has an essential, negative impact on the computational complexity of the problem. We give a definitive answer to this important question by providing a truthful deterministic PTAS.