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.
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}})$.
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.
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.
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.
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.
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.
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.
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.
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.