Department of Computer Science | Institute of Theoretical Computer Science | CADMO

Theory of Combinatorial Algorithms

Prof. Emo Welzl and Prof. Bernd Gärtner

Location: IFW A32

Wednesday, February 27

8:15 - 9:00 Bernhard Beckert Integrating Object-Oriented Design and Formal Verification
9:15 - 10:00 Peter Braß Algorithmic Problems in Point Pattern Matching
  Coffee break  
10:45 - 11:30 Nicol N. Schraudolph Rapid Stochastic Gradient Descent
11:45 - 12:30 Berthold Vöcking Multiple-Choice Algorithms

Friday, March 1

8:15 - 9:00 Benjamin Doerr Discrepancy Theory
9:15 - 10:00 Markus Bläser Approximation Algorithms for Asymmetric Traveling Salesperson Problems
10:15 - 11:00 Artur Czumaj Efficient Property Testers and Abstract Combinatorial Programming


Integrating Object-Oriented Design and Formal Verification

Bernhard Beckert, Univ. Karlsruhe

The importance of software verification is increasing as more and more safety and security critical applications emerge. Currently, however, tools and methods for software verification do not adequately support the programming languages used in practice. In my talk, I give an overview of the KeY project, which aims to overcome this problem.
The central idea of KeY is to enhance a commercial CASE tool with functionality for formal specification and deductive verification. The ultimate goal of the project is to facilitate and promote the use of formal methods as an integral part of real-world software development processes.
An important part of the KeY project is the development of a Dynamic Logic calculus for the programming language Java Card. I describe the main ideas and principles of this calculus, present some of its rules, and demonstrate how it is used to reason about properties of Java Card programs and verify them.

Approximation Algorithms for Asymmetric Traveling Salesperson Problems

Markus Bläser, Medizinische Univ. Lübeck

The Traveling Salesperson Problem (TSP) is a well known and fundamental problem in computer science with a lot of practical applications. Since it is NP-hard (at least most of its variants), much effort has been spent on designing good approximation algorithms for this problem. In our talk, we will mainly discuss the following two variants.
The first variant is the asymmetric TSP with distances one and two. This problem is of particular interest, since despite its simplicity, it is already APX-complete.
The second variant is the asymmetric maximum TSP. Here our goal is to find a maximum weight (i.e., longest) Hamiltonian tour instead of a minimum weight (i.e., shortest) Hamiltonian tour. Algorithms for this problem frequently occur as blackboxes in algorithms for the shortest common superstring problem. The latter problem arises in data compression and DNA sequence assembly.
Finally, we will briefly discuss relaxations of the above two problems, namely the problem of computing k-restricted cycle covers.

Algorithmic Problems in Point Pattern Matching

Peter Braß, Freie Univ. Berlin

Geometric pattern matching is an important subject that, depending on the model of patterns and geometric objects, can lead to quite diverse problems. In this talk I will discuss some algorithmic aspects of the point pattern model, where the objects and patterns are finite point sets. This model is especially suited for the use of methods of computational geometry. The general question `Does pattern A occur in the background B' then becomes, e.g., `Does the set B contain a subset congruent to A?'. I will discuss this and related problems, and present results on several exact, approximate, and preprocessing variants.

Efficient Property Testers and Abstract Combinatorial Programming

Artur Czumaj, New Jersey Inst. of Technology, Newark

A property tester is an algorithm that aims at determining whether a given object O satisfies a predefined property P or O is far from any object having property P. The power of this approach is that since the goal is to give only an "approximate" answer to the decision problem, many properties can be tested (by a randomized algorithm) in a sublinear or even constant time. For example, one can test in a constant time whether a given graph is bipartite or is "far" from any bipartite graph.
In this talk we present some efficient property testers for various combinatorial and geometric problems. We discuss also a novel framework for analyzing property testing algorithms that is based on a connection of property testing with a generalization of linear programming which we call Abstract Combinatorial Programming.

Discrepancy Theory

Benjamin Doerr, Univ. Kiel

Can you distribute n points in the unit square such that each rectangle contains a fraction of the points proportional to its volume? Can you round a non-integral solution of a linear program to an integer one without violating the constraints? Can you split a collection of objects having some specified properties into two in such a way that the properties are evenly split among the resulting two parts? In general, this is not possible. More over, discrepancy theory teaches us that usually one is even far from reaching these objectives. Nevertheless, for a number of problems interesting algorithmic solutions exist. In this talk we study a discrepancy problem arising in digital image processing. We use a modification of the well-known randomized rounding technique to obtain significant progress over previous solutions.

Rapid Stochastic Gradient Descent

Nicol N. Schraudolph, ETH Zürich

As Machine Learning tackles increasingly complex real-world phenomena, there is a growing need for scalable algorithms that can fit large, nonlinear, differentiable models to vast amounts of noisy, often non-stationary data. Conventional optimisation algorithms, however, are inadequate for this purpose: simple gradient descent is unacceptably slow to converge, conjugate gradient and truncated quasi-Newton methods do not tolerate noise, and the cost of an extended Kalman filter rises quadratically with the size of the system.
We are developing new ways to accelerate stochastic gradient descent by using second-order information obtained through the efficient computation of curvature matrix-vector products. This cheap curvature information can be used directly for diagonal adaptive conditioning of the system, or iteratively to build up a stochastic approximation of second-order gradient steps. The resulting algorithms approach the rapid convergence of second-order methods at only linear cost per iteration, and can thus be used to efficiently optimise extremely large nonlinear systems.

Multiple-Choice Algorithms

Berthold Vöcking, Max-Planck-Inst. Informatik, Saarbrücken

Multiple-choice allocation algorithms have been studied intensively over the last decade. These algorithms have several applications in the areas of load balancing, routing, resource allocation and hashing. The underlying idea is simple and can be explained best in the balls-and-bins model: Instead of assigning balls (jobs, requests, or keys) simply at random to bins (machines, servers, or positions in a hash table), choose first a small set of bins at random, inspect these bins, and place the ball into one of the bins containing the smallest number of balls among them.
The simple idea of first selecting a small set of alternatives at random and then making the final choice after careful inspection of these alternatives leads to great improvements against algorithms that place their decisions simply at random. We illustrate the power of this principle in terms of simple balls-and-bins processes. In particular, we study recently presented algorithms that treat bins asymmetrically in order to obtain a better load balancing. We compare the behavior of these asymmetric schemes with symmetric schemes and prove that the asymmetric schemes achieve a better load balancing than their symmetric counterparts.