### Refine

#### Has Fulltext

- yes (2) (remove)

#### Keywords

- Näherungsverfahren (2) (remove)

#### Institute

- Fachbereich 4 (1)
- Informatik (1)

This thesis considers the general task of computing a partition of a set of given objects such that each set of the partition has a cardinality of at least a fixed number k. Among such kinds of partitions, which we call k-clusters, the objective is to find the k-cluster which minimises a certain cost derived from a given pairwise difference between objects which end up the same set. As a first step, this thesis introduces a general problem, denoted by (||.||,f)-k-cluster, which models the task to find a k-cluster of minimum cost given by an objective function computed with respect to specific choices for the cost functions f and ||.||. In particular this thesis considers three different choices for f and also three different choices for ||.|| which results in a total of nine different variants of the general problem. Especially with the idea to use the concept of parameterised approximation, we first investigate the role of the lower bound on the cluster cardinalities and find that k is not a suitable parameter, due to remaining NP-hardness even for the restriction to the constant 3. The reductions presented to show this hardness yield the even stronger result which states that polynomial time approximations with some constant performance ratio for any of the nine variants of (||.||,f)-k-cluster require a restriction to instances for which the pairwise distance on the objects satisfies the triangle inequality. For this restriction to what we informally refer to as metric instances, constant-factor approximation algorithms for eight of the nine variants of (||.||,f)-k-cluster are presented. While two of these algorithms yield the provably best approximation ratio (assuming P!=NP), others can only guarantee a performance which depends on the lower bound k. With the positive effect of the triangle inequality and applications to facility location in mind, we discuss the further restriction to the setting where the given objects are points in the Euclidean metric space. Considering the effect of computational hardness caused by high dimensionality of the input for other related problems (curse of dimensionality) we check if this is also the source of intractability for (||.||,f)-k-cluster. Remaining NP-hardness for restriction to small constant dimensionality however disproves this theory. We then use parameterisation to develop approximation algorithms for (||.||,f)-k-cluster without restriction to metric instances. In particular, we discuss structural parameters which reflect how much the given input differs from a metric. This idea results in parameterised approximation algorithms with parameters such as the number of conflicts (our name for pairs of objects for which the triangle inequality is violated) or the number of conflict vertices (objects involved in a conflict). The performance ratios of these parameterised approximations are in most cases identical to those of the approximations for metric instances. This shows that for most variants of (||.||,f)-k-cluster efficient and reasonable solutions are also possible for non-metric instances.

The Harmonic Faber Operator
(2018)

P. K. Suetin points out in the beginning of his monograph "Faber
Polynomials and Faber Series" that Faber polynomials play an important
role in modern approximation theory of a complex variable as they
are used in representing analytic functions in simply connected domains,
and many theorems on approximation of analytic functions are proved
with their help [50].
In 1903, the Faber polynomials were firstly discovered by G. Faber. It was Faber's aim to find a generalisation of Taylor
series of holomorphic functions in the open unit disc D
in the following way. As any holomorphic function in D
has a Taylor series representation
f(z)=\sum_{\nu=0}^{\infty}a_{\nu}z^{\nu} (z\in\D)
converging locally uniformly inside D, for a simply connected
domain G, Faber wanted to determine a system of polynomials (Q_n)
such that each function f being holomorphic in G can be expanded
into a series
f=\sum_{\nu=0}^{\infty}b_{\nu}Q_{\nu}
converging locally uniformly inside G. Having this goal in mind,
Faber considered simply connected domains bounded by an analytic Jordan
curve. He constructed a system of polynomials (F_n)
with this property. These polynomials F_n were named after him
as Faber polynomials. In the preface of [50],
a detailed summary of results concerning Faber polynomials and results
obtained by the aid of them is given.
An important application of Faber polynomials is e.g. the transfer
of known assertions concerning polynomial approximation of functions
belonging to the disc algebra to results of the approximation of functions
being continuous on a compact continuum K which contains at least
two points and has a connected complement and being holomorphic in
the interior of K. In this field, the Faber operator
denoted by T turns out to be a powerful tool (for
an introduction, see e.g. D. Gaier's monograph). It
assigns a polynomial of degree at most n given in the monomial
basis \sum_{\nu=0}^{n}a_{\nu}z^{\nu} with a polynomial of degree
at most n given in the basis of Faber polynomials \sum_{\nu=0}^{n}a_{\nu}F_{\nu}.
If the Faber operator is continuous with respect to the uniform norms,
it has a unique continuous extension to an operator mapping the disc
algebra onto the space of functions being continuous on the whole
compact continuum and holomorphic in its interior. For all f being
element of the disc algebra and all polynomials P, via the obvious
estimate for the uniform norms
||T(f)-T(P)||<= ||T|| ||f-P||,
it can be seen that the original task of approximating F=T(f)
by polynomials is reduced to the polynomial approximation of the function
f. Therefore, the question arises under which conditions the Faber
operator is continuous and surjective. A fundamental result in this
regard was established by J. M. Anderson and J. Clunie who showed
that if the compact continuum is bounded by a rectifiable Jordan curve
with bounded boundary rotation and free from cusps, then the Faber
operator with respect to the uniform norms is a topological isomorphism.
Now, let f be a harmonic function in D.
Similar as above, we find that f has a uniquely determined representation
f=\sum_{\nu=-\infty}^{\infty}a_{\nu}p_{\nu}
converging locally uniformly inside D where p_{n}(z)=z^{n}
for n\in\N_{0} and p_{-n}(z)=\overline{z}^{n}
for n\in\N}. One may ask whether there is an analogue for
harmonic functions on simply connected domains G. Indeed, for a
domain G bounded by an analytic Jordan curve, the conjecture that
each function f being harmonic in G has a uniquely determined
representation
f=\sum_{\nu=-\infty}^{\infty}b_{\nu}F_{\nu}
where F_{-n}(z)=\overline{F_{n}(z\)} for n\inN,
converging locally uniformly inside G, holds true.
Let now K be a compact continuum containing at least two points
and having a connected complement. A main component of this thesis
will be the examination of the harmonic Faber operator mapping a harmonic
polynomial given in the basis of the harmonic monomials \sum_{\nu=-n}^{n}a_{\nu}p_{\nu}
to a harmonic polynomial given as \sum_{\nu=-n}^{n}a_{\nu}F_{\nu}.
If this operator, which is based on an idea of J. Müller,
is continuous with respect to the uniform norms, it has a unique continuous
extension to an operator mapping the functions being continuous on
\partial\D onto the continuous functions on K being
harmonic in the interior of K. Harmonic Faber polynomials and the
harmonic Faber operator will be the objects accompanying us throughout
our whole discussion.
After having given an overview about notations and certain tools we
will use in our consideration in the first chapter, we begin our studies
with an introduction to the Faber operator and the harmonic Faber
operator. We start modestly and consider domains bounded by an analytic
Jordan curve. In Section 2, as a first
result, we will show that, for such a domain G, the harmonic Faber
operator has a unique continuous extension to an operator mapping
the space of the harmonic functions in D onto the space
of the harmonic functions in G, and moreover, the harmonic Faber
operator is an isomorphism with respect to the topologies of locally
uniform convergence. In the further sections of this chapter, we illumine
the behaviour of the (harmonic) Faber operator on certain function
spaces.
In the third chapter, we leave the situation of compact continua bounded
by an analytic Jordan curve. Instead we consider closures of domains
bounded by Jordan curves having a Dini continuous curvature. With
the aid of the concept of compact operators and the Fredholm alternative,
we are able to show that the harmonic Faber operator is a topological
isomorphism.
Since, in particular, the main result of the third chapter holds true
for closures K of domains bounded by analytic Jordan curves, we
can make use of it to obtain new results concerning the approximation
of functions being continuous on K and harmonic in the interior
of K by harmonic polynomials. To do so, we develop techniques applied
by L. Frerick and J. Müller in [11] and adjust them to
our setting. So, we can transfer results about the classic Faber operator
to the harmonic Faber operator.
In the last chapter, we will use the theory of harmonic Faber polynomials
to solve certain Dirichlet problems in the complex plane. We pursue
two different approaches: First, with a similar philosophy as in [50],
we develop a procedure to compute the coefficients of a series \sum_{\nu=-\infty}^{\infty}c_{\nu}F_{\nu}
converging uniformly to the solution of a given Dirichlet problem.
Later, we will point out how semi-infinite programming with harmonic
Faber polynomials as ansatz functions can be used to get an approximate
solution of a given Dirichlet problem. We cover both approaches first
from a theoretical point of view before we have a focus on the numerical
implementation of concrete examples. As application of the numerical
computations, we considerably obtain visualisations of the concerned
Dirichlet problems rounding out our discussion about the harmonic
Faber polynomials and the harmonic Faber operator.