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.

A local 2-approximation algorithm for the vertex cover problem

We present a distributed 2-approximation algorithm for the minimum vertex cover problem. The algorithm is deterministic, and it runs in (Δ + 1)2 synchronous communication rounds, where Δ is the maximum degree of the graph. For Δ = 3, we give a 2-approximation algorithm also for the weighted version of the problem.

A simple local 3-approximation algorithm for vertex cover

We present a local algorithm (constant-time distributed algorithm) for finding a 3-approximate vertex cover in bounded-degree graphs. The algorithm is deterministic, and no auxiliary information besides port numbering is required. (c) 2009 Elsevier B.V. All rights reserved.

A local 2-approximation algorithm for the vertex cover problem

We present a distributed 2-approximation algorithm for the minimum vertex cover problem. The algorithm is deterministic, and it runs in (Δ + 1)2 synchronous communication rounds, where Δ is the maximum degree of the graph. For Δ = 3, we give a 2-approximation algorithm also for the weighted version of the problem.

On the Rademacher maximal function

Tools known as maximal functions are frequently used in harmonic analysis when studying local behaviour of functions. Typically they measure the suprema of local averages of non-negative functions. It is essential that the size (more precisely, the L^p-norm) of the maximal function is comparable to the size of the original function. When dealing with families of operators between Banach spaces we are often forced to replace the uniform bound with the larger R-bound. Hence such a replacement is also needed in the maximal function for functions taking values in spaces of operators. More specifically, the suprema of norms of local averages (i.e. their uniform bound in the operator norm) has to be replaced by their R-bound. This procedure gives us the Rademacher maximal function, which was introduced by Hytönen, McIntosh and Portal in order to prove a certain vector-valued Carleson's embedding theorem. They noticed that the sizes of an operator-valued function and its Rademacher maximal function are comparable for many common range spaces, but not for all. Certain requirements on the type and cotype of the spaces involved are necessary for this comparability, henceforth referred to as the “RMF-property”. It was shown, that other objects and parameters appearing in the definition, such as the domain of functions and the exponent p of the norm, make no difference to this. After a short introduction to randomized norms and geometry in Banach spaces we study the Rademacher maximal function on Euclidean spaces. The requirements on the type and cotype are considered, providing examples of spaces without RMF. L^p-spaces are shown to have RMF not only for p greater or equal to 2 (when it is trivial) but also for 1 < p < 2. A dyadic version of Carleson's embedding theorem is proven for scalar- and operator-valued functions. As the analysis with dyadic cubes can be generalized to filtrations on sigma-finite measure spaces, we consider the Rademacher maximal function in this case as well. It turns out that the RMF-property is independent of the filtration and the underlying measure space and that it is enough to consider very simple ones known as Haar filtrations. Scalar- and operator-valued analogues of Carleson's embedding theorem are also provided. With the RMF-property proven independent of the underlying measure space, we can use probabilistic notions and formulate it for martingales. Following a similar result for UMD-spaces, a weak type inequality is shown to be (necessary and) sufficient for the RMF-property. The RMF-property is also studied using concave functions giving yet another proof of its independence from various parameters.

On the ecology of cold-water phytoplankton in the Baltic Sea

Increased anthropogenic loading of nitrogen (N) and phosphorus (P) has led to an eutrophication problem in the Baltic Sea, and the spring bloom is a key component in the biological uptake of increased nutrient concentrations. The spring bloom in the Baltic Sea is dominated by both diatoms and dinoflagellates. However, the sedimentation of these groups is different: diatoms tend to sink to the sea floor at the end of the bloom, while dinoflagellates to a large degree are been remineralized in the euphotic zone. Understanding phytoplankton competition and species specific ecological strategies is thus of importance for assessing indirect effects of phytoplankton community composition on eutrophication problems. The main objective of this thesis was to describe some basic physiological and ecological characteristics of the main cold-water diatoms and dinoflagellates in the Baltic Sea. This was achieved by specific studies of: (1) seasonal vertical positioning, (2) dinoflagellate life cycle, (3) mixotrophy, (4) primary production, respiration and growth and (5) diatom silicate uptake, using cultures of common cold-water diatoms: Chaetoceros wighamii, C. gracilis, Pauliella taeniata, Thalassiosira baltica, T. levanderi, Melosira arctica, Diatoma tenuis, Nitzschia frigida, and dinoflagellates: Peridiniella catenata, Woloszynskia halophila and Scrippsiella hangoei. The diatoms had higher primary production capacity and lower respiration rate compared with the dinoflagellates. This difference was reflected in the maximum growth rate, which for the examined diatoms range from 0.6 to 1.2 divisions d-1, compared with 0.2 to 0.3 divisions d-1 for the dinoflagellates. Among diatoms there were species specific differences in light utilization and uptake of silicate, and C. wighamii had the highest carbon assimilation capacity and maximum silicate uptake. The physiological properties of diatoms and dinoflagellates were used in a model of the onset of the spring bloom: for the diatoms the model could predict the initiation of the spring bloom; S. hangoei, on the other hand, could not compete successfully and did not obtain positive growth in the model. The other dinoflagellates did not have higher growth rates or carbon assimilation rates and would thus probably not perform better than S. hangoei in the model. The dinoflagellates do, however, have competitive advantages that were not included in the model: motility and mixotrophy. Previous investigations has revealed that the chain-forming P. catenata performs diurnal vertical migration (DVM), and the results presented here suggest that active positioning in the water column, in addition to DVM, is a key element in this species' life strategy. There was indication of mixotrophy in S. hangoei, as it produced and excreted the enzyme leucine aminopeptidase (LAP). Moreover, there was indirect evidence that W. halophila obtains carbon from other sources than photosynthesis when comparing increase in cell numbers with in situ carbon assimilation rates. The results indicate that mixotrophy is a part of the strategy of vernal dinoflagellates in the Baltic Sea. There were also indications that the seeding of the spring bloom is very important for the dinoflagellates to succeed. In mesocosm experiments dinoflagellates could not compete with diatoms when their initial numbers were low. In conclusion, this thesis has provided new information about the basic physiological and ecological properties of the main cold-water phytoplankton in the Baltic Sea. The main phytoplankton groups, diatoms and dinoflagellates, have different physiological properties, which clearly separate their life strategies. The information presented here could serve as further steps towards better prognostic models of the effects of eutrophication in the Baltic Sea.

Search for Maximal Flavor Violating Scalars in Same-Charge Lepton Pairs in pp̅ Collisions at √s=1.96 TeV

Models of Maximal Flavor Violation (MxFV) in elementary particle physics may contain at least one new scalar SU$(2)$ doublet field $\Phi_{FV} = (\eta^0,\eta^+)$ that couples the first and third generation quarks ($q_1,q_3$) via a Lagrangian term $\mathcal{L}_{FV} = \xi_{13} \Phi_{FV} q_1 q_3$. These models have a distinctive signature of same-charge top-quark pairs and evade flavor-changing limits from meson mixing measurements. Data corresponding to 2 fb$^{-1}$ collected by the CDF II detector in $p\bar{p}$ collisions at $\sqrt{s} = 1.96$ TeV are analyzed for evidence of the MxFV signature. For a neutral scalar $\eta^0$ with $m_{\eta^0} = 200$ GeV/$c^2$ and coupling $\xi_{13}=1$, $\sim$ 11 signal events are expected over a background of $2.1 \pm 1.8$ events. Three events are observed in the data, consistent with background expectations, and limits are set on the coupling $\xi_{13}$ for $m_{\eta^0} = 180-300$ GeV/$c^2$.

Studies on Stone Age Housepits in Fennoscandia (4000 - 2000 cal BC) : Changes in ground plan, site location and degree of sedentism

Housepits have a remarkably short research history as compared to Fennoscandian archaeological research on the Stone Age in general. The current understanding of the numbers and the distribution of Stone Age housepits in the Nordic countries has, for the most part, been shaped by archaeological studies carried out over the last twenty to thirty years. The main subjects of this research are Neolithic housepits, which are archaeological remains of semi-subterranean pithouses. This dissertation consists of five peer-reviewed articles and a synthesis paper. The articles deal with the development of housepits as seen in the data gathered from Finland (the Lake Saimaa area and south-eastern Finland) and Russia (the Karelian Isthmus). This synthesis expands the discussion of the changes observed in the Papers to include Fennoscandian housepit research as a whole. Certain changes in the size, shape, environmental location, and clustering of housepits extended into various cultures and ecological zones in northern Fennoscandia. Previously, the evolution of housepits has been interpreted to have been caused by the adaptation of Neolithic societies to prevailing environmental circumstances or to re-organization following contacts with the agrarian Corded Ware/Battle Axe Cultures spreading to North. This dissertation argues for two waves of change in the pithouse building tradition. Both waves brought with them certain changes in the pithouses themselves and in the practices of locating the dwellings in the environment/landscape. The changes in housepits do not go hand in hand with other changes in material culture, nor are the changes restricted to certain ecological environments. Based on current information, it appears that the changes relate primarily to the spread of new concepts of housing and possibly to new technology, as opposed to representing merely a local response to environmental factors. This development commenced already before the birth of the Corded Ware/Battle Axe Cultures. Therefore, the changes are argued to have resulted from the spreading of new ideas through the same networks that actively distributed commodities, exotic goods, and raw materials over vast areas between the southern Baltic Sea, the north-west Russian forest zone, and Fennoscandia.

Attitudes towards suicide among Master’s degree students: a cross-cultural comparison between China and Finland

Attitudes towards suicide among Master’s degree students in Chang Sha (China) and Helsinki (Finland) were compared in order to explore possible cross-cultural differences. The sample included 206 Master’s degree students, 101 Chinese and 105 Finnish. Data were collected using the 30-item Multi-Attitudes Suicide Tendency Scale (MAST) and a demographic information form. According to the results, both Chinese and Finnish students held positive attitudes towards life, they held contradictory attitudes towards suicide, with Finnish students having more permissive and liberal attitudes towards suicide than their Chinese counterparts. In addition, three socio-demographic characteristics, namely religion, family structure, and economic status, associated with attitudes towards suicide among the Chinese Master’s degree students; meanwhile, all socio-demographic characteristics, including gender, religion, major subject, family structure, economic status, and received social support related to attitudes towards suicide among the Finnish Master’s degree students. However, after examining the interaction effect between socio-demographics and cultural backgrounds on attitudes towards suicide, the attitudes of Chinese students were more related to gender, marital status, family economic status, and received social support, whereas Finnish students were more influenced by religion. These findings suggest that culture plays an important role in shaping country-specific differences in attitudes towards suicide and their association with socio-demographic characteristics. Understanding individual attitudes towards suicide could help in intervention to prevent the development of suicidal ideation and in providing appropriate psychological counseling to reduce mental problems. Therefore, these cross-cultural differences may provide indications on how to conduct suicide prevention programs while considering culture-specific contexts.

Planar subgraphs without low-degree nodes

We study the following problem: given a geometric graph G and an integer k, determine if G has a planar spanning subgraph (with the original embedding and straight-line edges) such that all nodes have degree at least k. If G is a unit disk graph, the problem is trivial to solve for k = 1. We show that even the slightest deviation from the trivial case (e.g., quasi unit disk graphs or k = 1) leads to NP-hard problems.

A maximal operator, Carleson's embedding, and tent spaces for vector-valued functions

This thesis is concerned with the area of vector-valued Harmonic Analysis, where the central theme is to determine how results from classical Harmonic Analysis generalize to functions with values in an infinite dimensional Banach space. The work consists of three articles and an introduction. The first article studies the Rademacher maximal function that was originally defined by T. Hytönen, A. McIntosh and P. Portal in 2008 in order to prove a vector-valued version of Carleson's embedding theorem. The boundedness of the corresponding maximal operator on Lebesgue-(Bochner) -spaces defines the RMF-property of the range space. It is shown that the RMF-property is equivalent to a weak type inequality, which does not depend for instance on the integrability exponent, hence providing more flexibility for the RMF-property. The second article, which is written in collaboration with T. Hytönen, studies a vector-valued Carleson's embedding theorem with respect to filtrations. An earlier proof of the dyadic version assumed that the range space satisfies a certain geometric type condition, which this article shows to be also necessary. The third article deals with a vector-valued generalizations of tent spaces, originally defined by R. R. Coifman, Y. Meyer and E. M. Stein in the 80's, and concerns especially the ones related to square functions. A natural assumption on the range space is then the UMD-property. The main result is an atomic decomposition for tent spaces with integrability exponent one. In order to suit the stochastic integrals appearing in the vector-valued formulation, the proof is based on a geometric lemma for cones and differs essentially from the classical proof. Vector-valued tent spaces have also found applications in functional calculi for bisectorial operators. In the introduction these three themes come together when studying paraproduct operators for vector-valued functions. The Rademacher maximal function and Carleson's embedding theorem were applied already by Hytönen, McIntosh and Portal in order to prove boundedness for the dyadic paraproduct operator on Lebesgue-Bochner -spaces assuming that the range space satisfies both UMD- and RMF-properties. Whether UMD implies RMF is thus an interesting question. Tent spaces, on the other hand, provide a method to study continuous time paraproduct operators, although the RMF-property is not yet understood in the framework of tent spaces.