- tr-announce - lists.rwth-aachen.de

2008-11: Fast Convergence of Routing Games with Splittable Flows
by Peter Schneider-Kamp 06 Jun '08

06 Jun '08

The following technical report is available from http://aib.informatik.rwth-aachen.de: Fast Convergence of Routing Games with Splittable Flows George B. Mertzios AIB 2008-11 In this paper we investigate the splittable routing game in a series-parallel network with two selfish players. Every player wishes to route optimally, i.e. at minimum cost, an individual flow demand from the source to the destination, giving rise to a non-cooperative game. We allow a player to split his flow along any number of paths. One of the fundamental questions in this model is the convergence of the best response dynamics to a Nash equilibrium, as well as the time of convergence. We prove that this game converges indeed to a Nash equilibrium in a logarithmic number of steps. Our results hold for increasing and convex player-specific latency functions. Finally, we prove that our analysis on the convergence time is tight for affine latency functions.

1 0

2008-10: Preemptive Scheduling of Equal-Length Jobs in Polynomial Time
by Peter Schneider-Kamp 07 May '08

07 May '08

The following technical report is available from http://aib.informatik.rwth-aachen.de: Preemptive Scheduling of Equal-Length Jobs in Polynomial Time George B. Mertzios, Walter Unger AIB 2008-10 We study the preemptive scheduling problem of a set of $n$ jobs with release times and equal processing time on a single machine. The objective is to minimize the sum of the weighted completion times $\sum_{i=1}^{n}w_{i}C_{i}$ of the jobs, where the number $k$ of different weights is constant. We provide for this problem a first polynomial algorithm with runtime $O(\frac{n^{k+8}}{k^{k}})$.

1 0

2008-09: An optimal algorithm for the k-fixed-endpoint path cover on proper interval graphs
by Peter Schneider-Kamp 07 May '08

07 May '08

The following technical report is available from http://aib.informatik.rwth-aachen.de: An optimal algorithm for the k-fixed-endpoint path cover on proper interval graphs George B. Mertzios, Walter Unger AIB 2008-09 In this paper we consider the $k$-fixed-endpoint path cover problem on proper interval graphs, which is a generalization of the path cover problem. Given a proper interval graph $G$ and a particular set $T$ of $k$ vertices, the goal is to compute a path cover of $G$ with minimum cardinality, such that the vertices of $T$ are endpoints of these paths. We propose an optimal algorithm for this problem with runtime $O(n)$, where $n$ is the number of intervals in $G$. This algorithm is based on the \emph{Stair Normal Interval Representation (SNIR) matrix} of proper interval graphs.

1 0

2008-08: The $\lambda$-cluster Problem on Parameterized Interval Graphs
by Peter Schneider-Kamp 07 May '08

07 May '08

The following technical report is available from http://aib.informatik.rwth-aachen.de: The $\lambda$-cluster Problem on Parameterized Interval Graphs George B. Mertzios, Stavros D. Nikolopoulos AIB 2008-08 This paper is concerned with the problem of finding, for a given graph $G$ and a given natural number $\lambda$, a subgraph of $G$ on $\lambda$ vertices with a maximum number of edges. The problem is known as the $\lambda$-cluster problem and is NP-hard on general graphs; it remains NP-hard even when restricted to specific graph classes such as comparability, bipartite, chordal graphs, while it is polynomially solvable on the class of interval graphs. Here, we are interested in investigating how the $\lambda$-cluster problem behaves on input graphs that are ``close'' to interval graphs. For this purpose, we consider the class of modified interval graphs, denoted by interval$\pm ke$, which is the class of graphs obtained from interval graphs by adding at most $k_1$ edges and deleting at most $k_2$ edges, where $k=k_1+k_2$. We show that the $\lambda$-cluster problem is fixed-parameter tractable (FPT) with parameter $k$ on interval$\pm ke$ graphs. In particular, we present a dynamic programming algorithm which computes a $\lambda$-cluster of an $n$-vertex interval$\pm ke$ graph in $O(2^{k_1+2k_2} \cdot n \lambda6)$ time, where $k=k_1+k_2$. Our results imply that the $\lambda$-cluster problem is also FPT on both interval$+ke$ and interval$-ke$ classes of graphs with complexity $O(2^{k} \cdot n \lambda6)$ and $O(2^{2k} \cdot n \lambda6)$ respectively.

1 0

2008-06: A Framework for Proving Correctness of Adjoint Message Passing Programs
by Peter Schneider-Kamp 11 Apr '08

11 Apr '08

The following technical report is available from http://aib.informatik.rwth-aachen.de: A Framework for Proving Correctness of Adjoint Message Passing Programs Uwe Naumann, Laurent Hascoet, Chris Hill, Paul Hovland, Jan Riehme, Jean Utke AIB 2008-06 Adjoint programs play a central role in modern numerical algorithms such as large-scale sensitivity analysis, parameter tuning, and general nonlinear optimization. They can be generated automatically by compilers. In such cases, the data flow of the original program needs to be reversed. If message passing is used, then any communication needs to be reversed, too. Crucial properties of the original program such as deadlock-freeness and determinism must be preserved in the adjoint code. A formalism for proving the correctness of compiler-generated adjoints is required but has been missing so far, to the best of our knowledge. To rectify this situation, we propose a proof technique that relies on data dependences in partitioned global address space versions of the adjoint message-passing program. If the original program is deadlock-free, the transformation rules can be shown to be correct in the sense that the automatically generated adjoint program is also deadlock free while implementing the mathematical mapping from given independent inputs onto their corresponding adjoints correctly. As an example we discuss asynchronous unbuffered send/receive using MPI.

1 0

2007-19: Adjoints for Time-Dependent Optimal Control
by Peter Schneider-Kamp 07 Mar '08

07 Mar '08

The following technical report is available from http://aib.informatik.rwth-aachen.de: Adjoints for Time-Dependent Optimal Control Jan Riehme, Andrea Walther, Jörg Stiller, Uwe Naumann AIB 2007-19 The use of discrete adjoints in the context of a hard time-dependent optimal control problem is considered. Gradients required for the steepest descent method are computed by code that is generated automatically by the differentiation-enabled NAGWare Fortran compiler. Single time steps are taped using an overloading approach. The entire evolution is reversed based on an efficient checkpointing schedule that is computed by revolve. The feasibility of nonlinear optimization based on discrete adjoints is supported by our numerical results.

1 0

2007-18: Call Tree Reversal is NP-Complete
by Peter Schneider-Kamp 07 Mar '08

07 Mar '08

The following technical report is available from http://aib.informatik.rwth-aachen.de: Call Tree Reversal is NP-Complete Uwe Naumann AIB 2007-18 The data-flow of a numerical program is reversed in its adjoint. We discuss the combinatorial optimization problem that aims to find optimal checkpointing schemes at the level of call trees. For a given amount of persistent memory the objective is to store selected arguments and/or results of subroutine calls such that the overall computational effort (the total number of floating-point operations performed by potentially repeated forward evaluations of the program) of the data-flow reversal is minimized. Call Tree Reversal is shown to be NP-complete.

1 0

2008-04: Sensitivity Analysis in Sisyphe with the AD-Enabled NAGWare Fortran Compiler
by Peter Schneider-Kamp 05 Mar '08

05 Mar '08

The following technical report is available from http://aib.informatik.rwth-aachen.de: Sensitivity Analysis in Sisyphe with the AD-Enabled NAGWare Fortran Compiler Uwe Naumann, Jan Riehme AIB 2008-04 We present the final report for a collaborative research project with the Federal Waterways Engineering and Research Institute, Karsruhle. A numerical model of a dune implemented in Sisyphe is considered. Sensitivity analysis is performed using a tangent-linear model that is generated automatically by the differentiation-enabled NAGWare Fortran compiler.

1 0

2008-05: An Automata Theoretic Approach to the Theory of Rational Tree Relations
by Peter Schneider-Kamp 04 Mar '08

04 Mar '08

The following technical report is available from http://aib.informatik.rwth-aachen.de: An Automata Theoretic Approach to the Theory of Rational Tree Relations Frank G. Radmacher AIB 2008-05 We investigate rational relations over trees. Our starting point is the definition of rational tree relations via rational expressions by Raoult (Bull.Belg.Math.Soc. 1997). We develop a new class of automata, called asynchronous tree automata, which recognize exactly these relations. The automata theoretic approach is convenient for the solution of algorithmic problems (like the emptiness problem). The second contribution of this paper is a new subclass of the rational tree relations, called separate-rational tree relations, defined via a natural restriction on asynchronous tree automata. These relations are closed under composition, preserve regular tree languages, and generate precisely the regular sets in the unary case (all these properties fail for the general model), and they are still more powerful than, for instance, the automatic tree relations.

1 0

2008-03: Maximal Termination
by Peter Schneider-Kamp 04 Mar '08

04 Mar '08

The following technical report is available from http://aib.informatik.rwth-aachen.de: Maximal Termination Carsten Fuhs, Jürgen Giesl, Aart Middeldorp, Peter Schneider-Kamp, René Thiemann, Harald Zankl AIB 2008-03 We present a new approach for termination proofs that uses polynomial interpretations (with possibly negative coefficients) together with the "maximum" function. To obtain a powerful automatic method, we solve two main challenges: (1) We show how to adapt the latest developments in the dependency pair framework to our setting. (2) We show how to automate the search for such interpretations by integrating "max" into recent SAT-based methods for polynomial interpretations. Experimental results support our approach.

1 0