
When using reinforcement learning (RL) algorithms it is common, given a large
state space, to introduce some form of approximation architecture for the value
function (VF). The exact form of this architecture can have a significant
effect on an agent's performance, however, and determining a suitable
approximation architecture can often be a highly complex task. Consequently
there is currently interest among researchers in the potential for allowing RL
algorithms to adaptively generate (i.e. to learn) approximation architectures.
One relatively unexplored method of adapting approximation architectures
involves using feedback regarding the frequency with which an agent has visited
certain states to guide which areas of the state space to approximate with
greater detail. In this article we will: (a) informally discuss the potential
advantages offered by such methods; (b) introduce a new algorithm based on such
methods which adapts a state aggregation approximation architecture online and
is designed for use in conjunction with SARSA; (c) provide theoretical results,
in a policy evaluation setting, regarding this particular algorithm's
complexity, convergence properties and potential to reduce VF error; and
finally (d) test experimentally the extent to which this algorithm can improve
performance given a number of different test problems. Taken together our
results suggest that our algorithm (and potentially such methods more
generally) can provide a versatile and computationally lightweight means of
significantly boosting RL performance given suitable conditions which are
commonly encountered in practice.

An approximate Steiner tree is a Steiner tree on a given set of terminals in
Euclidean space such that the angles at the Steiner points are within a
specified error e from 120 degrees.This notion arises in numerical
approximations of minimum Steiner trees (W. D. Smith, Algorithmica, 7 (1992),
137177). We investigate the worstcase relative error of the length of an
approximate Steiner tree compared to the shortest tree with the same
topology.Rubinstein, Weng and Wormald (J. Global Optim. 35 (2006), 573592)
conjectured that this relative error is at most linear in $e$, independent of
the number of terminals. We verify their conjecture for the twodimensional
case as long as the error $e$ is sufficiently small in terms of the number of
terminals. We derive a lower bound linear in $e$ for the relative error in the
twodimensional case when $e$ is sufficiently small in terms of the number of
terminals. We find improved estimates of the relative error for larger values
of $e$, and calculate exact values in the plane for three and four terminals.

We first prove a onetoone correspondence between finding Hamiltonian cycles
in a cubic planar graphs and finding trees with specific properties in dual
graphs. Using this information, we construct an exact algorithm for finding
Hamiltonian cycles in cubic planar graphs. The worst case time complexity of
our algorithm is O$(2^n)$.

This paper establishes connections between the structure of a semigroup and
the minimum spans of distance labellings of its Cayley graphs. We show that
certain general restrictions on the minimum spans are equivalent to the
semigroup being combinatorial, and that other restrictions are equivalent to
the semigroup being a right zero band. We obtain a description of the structure
of all semigroups $S$ and their subsets $C$ such that $\Cay(S,C)$ is a disjoint
union of complete graphs, and show that this description is also equivalent to
several restrictions on the minimum span of $\Cay(S,C)$. We then describe all
graphs with minimum spans satisfying the same restrictions, and give examples
to show that a fairly straightforward upper bound for the minimum spans of the
underlying undirected graphs of Cayley graphs turns out to be sharp even for
the class of combinatorial semigroups.

We present the first exact polynomial time algorithm for constructing optimal
geometric bottleneck 2connected Steiner networks containing at most $k$
Steiner points, where $k>2$ is a constant. Given a set of $n$ vertices embedded
in an $L_p$ plane, the objective of the problem is to find a 2connected
network, spanning the given vertices and at most $k$ additional vertices, such
that the length of the longest edge is minimised. In contrast to the discrete
version of this problem the additional vertices may be located anywhere in the
plane. The problem is motivated by the modelling of relayaugmentation for the
optimisation of energy consumption in wireless ad hoc networks. Our algorithm
employs Voronoi diagrams and properties of blockcutvertex decompositions of
graphs to find an optimal solution in $O(n^k\log^{\frac{5k}{2}}n)$ steps when
$1<p<\infty$ and in $O(n^2\log^{\frac{7k}{2}+1}n)$ steps when
$p\in\{1,\infty\}$.

We propose a novel relay augmentation strategy for extending the lifetime of
a certain class of wireless sensor networks. In this class sensors are located
at fixed and predetermined positions and all communication takes place via
multihop paths in a fixed routing tree rooted at the base station. It is
assumed that no accumulation of data takes place along the communication paths
and that there is no restriction on where additional relays may be located.
Under these assumptions the optimal extension of network lifetime is modelled
as the Euclidean $k$bottleneck Steiner tree problem. Only two approximation
algorithms for this NPhard problem exist in the literature: a minimum spanning
tree heuristic (MSTH) with performance ratio 2, and a probabilistic 3regular
hypergraph heuristic (3RHH) with performance ratio $\sqrt{3}+\epsilon$. We
present a new iterative heuristic that incorporates MSTH and show via
simulation that our algorithm performs better than MSTH in extending lifetime,
and outperforms 3RHH in terms of efficiency.

We introduce a flowdependent version of the quadratic Steiner tree problem
in the plane. An instance of the problem on a set of embedded sources and a
sink asks for a directed tree $T$ spanning these nodes and a bounded number of
Steiner points, such that $\displaystyle\sum_{e \in E(T)}f(e)e^2$ is a
minimum, where $f(e)$ is the flow on edge $e$. The edges are uncapacitated and
the flows are determined additively, i.e., the flow on an edge leaving a node
$u$ will be the sum of the flows on all edges entering $u$. Our motivation for
studying this problem is its utility as a model for relay augmentation of
wireless sensor networks. In these scenarios one seeks to optimise power
consumption  which is predominantly due to communication and, in free space,
is proportional to the square of transmission distance  in the network by
introducing additional relays. We prove several geometric and combinatorial
results on the structure of optimal and locally optimal solutiontrees (under
various strategies for bounding the number of Steiner points) and describe a
geometric lineartime algorithm for constructing such trees with known
topologies.