Exact bounds for distributed graph colouring

A distributed system is a collection of networked autonomous processing units which must work in a cooperative manner. Currently, large-scale distributed systems, such as various telecommunication and computer networks, are abundant and used in a multitude of tasks. The field of distributed computing studies what can be computed efficiently in such systems. Distributed systems are usually modelled as graphs where nodes represent the processors and edges denote communication links between processors. This thesis concentrates on the computational complexity of the distributed graph colouring problem. The objective of the graph colouring problem is to assign a colour to each node in such a way that no two nodes connected by an edge share the same colour. In particular, it is often desirable to use only a small number of colours. This task is a fundamental symmetry-breaking primitive in various distributed algorithms. A graph that has been coloured in this manner using at most k different colours is said to be k-coloured. This work examines the synchronous message-passing model of distributed computation: every node runs the same algorithm, and the system operates in discrete synchronous communication rounds. During each round, a node can communicate with its neighbours and perform local computation. In this model, the time complexity of a problem is the number of synchronous communication rounds required to solve the problem. It is known that 3-colouring any k-coloured directed cycle requires at least ½(log* k - 3) communication rounds and is possible in ½(log* k + 7) communication rounds for all k ≥ 3. This work shows that for any k ≥ 3, colouring a k-coloured directed cycle with at most three colours is possible in ½(log* k + 3) rounds. In contrast, it is also shown that for some values of k, colouring a directed cycle with at most three colours requires at least ½(log* k + 1) communication rounds. Furthermore, in the case of directed rooted trees, reducing a k-colouring into a 3-colouring requires at least log* k + 1 rounds for some k and possible in log* k + 3 rounds for all k ≥ 3. The new positive and negative results are derived using computational methods, as the existence of distributed colouring algorithms corresponds to the colourability of so-called neighbourhood graphs. The colourability of these graphs is analysed using Boolean satisfiability (SAT) solvers. Finally, this thesis shows that similar methods are applicable in capturing the existence of distributed algorithms for other graph problems, such as the maximal matching problem.

Fast distributed approximation algorithms for vertex cover and set cover in anonymous networks

We present a distributed algorithm that finds a maximal edge packing in O(Δ + log* W) synchronous communication rounds in a weighted graph, independent of the number of nodes in the network; here Δ is the maximum degree of the graph and W is the maximum weight. As a direct application, we have a distributed 2-approximation algorithm for minimum-weight vertex cover, with the same running time. We also show how to find an f-approximation of minimum-weight set cover in O(f2k2 + fk log* W) rounds; here k is the maximum size of a subset in the set cover instance, f is the maximum frequency of an element, and W is the maximum weight of a subset. The algorithms are deterministic, and they can be applied in anonymous networks.

Seasonal variation in nitrification and nitrate-reduction pathways in coastal sediments in the Gulf of Finland, Baltic Sea

The Baltic Sea is one of the most eutrophic marine areas in the world. The role of nitrogen as a eutrophicating nutrient in the Baltic Sea has remained controversial, due to lack of understanding of nitrogen cycling in the area. We investigated the seasonal variation in sediment nitrification, denitrification, anaerobic ammonium oxidation (anammox), and dissimilatory nitrate reduction to ammonium (DNRA) at two coastal sites in the Gulf of Finland. In addition to the in situ rates, we assessed the potential for these processes in different seasons. The nitrification and nitrogen removal processes were maximal during the warm summer months, when the sediment organic content was highest. In colder seasons, the in situ rates of the nitrification and nitrate reduction processes decreased, but the potential for nitrification remained equal to or higher than that during the warm months. The denitrification and nitrification rates were usually higher in the accumulation basin, where the organic content of the sediment was higher, but the transportation area, despite lower denitrification rates and potential, typically had higher potential for nitrification than the accumulation basin. Anammox and DNRA were not significant nitrate sinks in any of the seasons sampled. The results also show that the denitrification rates in the coastal Gulf of Finland sediment have decreased, and that benthic denitrification might be a less important sink for fixed nitrogen than previously assumed.

Optimal multispecies fishery management in the Baltic Sea: A bioeconomic analysis

The aim of the thesis is to assess the fishery of Baltic cod, herring and sprat by simulation over 50 years time period. We form a bioeconomic multispecies model for the species. We include species interactions into the model because especially cod and sprat stocks have significant effects on each other. We model the development of population dynamics, catches and profits of the fishery with current fishing mortalities, as well as with the optimal profit maximizing fishing mortalities. Thus, we see how the fishery would develop with current mortalities, and how the fishery should be developed in order to yield maximal profits. Especially cod stock has been quite low recently and by optimizing the fishing mortality it could get recovered. In addition, we assess what would happen to the fisheries of the species if more favourable environmental conditions for cod recruitment dominate in the Baltic Sea. The results may yield new information for the fisheries management. According to the results the fishery of Baltic cod, herring and sprat are not at the most profitable level. The fishing mortalities of each species should be lower in order to maximize the profits. By fishing mortality optimizing the net present value would be almost three times higher in the simulation period. The lower fishing mortality of cod would result in a cod stock recovery. If the environmental conditions in the Baltic Sea improved, cod stock would recover even without a decrease in the fishing mortality. Then the increased cod stock would restrict herring and sprat stock remarkably, and harvesting of these species would not be as profitable anymore.

Global, Local and Vector-Valued Tb Theorems on Non-Homogeneous Metric Spaces

Various Tb theorems play a key role in the modern harmonic analysis. They provide characterizations for the boundedness of Calderón-Zygmund type singular integral operators. The general philosophy is that to conclude the boundedness of an operator T on some function space, one needs only to test it on some suitable function b. The main object of this dissertation is to prove very general Tb theorems. The dissertation consists of four research articles and an introductory part. The framework is general with respect to the domain (a metric space), the measure (an upper doubling measure) and the range (a UMD Banach space). Moreover, the used testing conditions are weak. In the first article a (global) Tb theorem on non-homogeneous metric spaces is proved. One of the main technical components is the construction of a randomization procedure for the metric dyadic cubes. The difficulty lies in the fact that metric spaces do not, in general, have a translation group. Also, the measures considered are more general than in the existing literature. This generality is genuinely important for some applications, including the result of Volberg and Wick concerning the characterization of measures for which the analytic Besov-Sobolev space embeds continuously into the space of square integrable functions. In the second article a vector-valued extension of the main result of the first article is considered. This theorem is a new contribution to the vector-valued literature, since previously such general domains and measures were not allowed. The third article deals with local Tb theorems both in the homogeneous and non-homogeneous situations. A modified version of the general non-homogeneous proof technique of Nazarov, Treil and Volberg is extended to cover the case of upper doubling measures. This technique is also used in the homogeneous setting to prove local Tb theorems with weak testing conditions introduced by Auscher, Hofmann, Muscalu, Tao and Thiele. This gives a completely new and direct proof of such results utilizing the full force of non-homogeneous analysis. The final article has to do with sharp weighted theory for maximal truncations of Calderón-Zygmund operators. This includes a reduction to certain Sawyer-type testing conditions, which are in the spirit of Tb theorems and thus of the dissertation. The article extends the sharp bounds previously known only for untruncated operators, and also proves sharp weak type results, which are new even for untruncated operators. New techniques are introduced to overcome the difficulties introduced by the non-linearity of maximal truncations.