Analysing local algorithms in location-aware quasi-unit-disk graphs

A local algorithm with local horizon r is a distributed algorithm that runs in r synchronous communication rounds; here r is a constant that does not depend on the size of the network. As a consequence, the output of a node in a local algorithm only depends on the input within r hops from the node. We give tight bounds on the local horizon for a class of local algorithms for combinatorial problems on unit-disk graphs (UDGs). Most of our bounds are due to a refined analysis of existing approaches, while others are obtained by suggesting new algorithms. The algorithms we consider are based on network decompositions guided by a rectangular tiling of the plane. The algorithms are applied to matching, independent set, graph colouring, vertex cover, and dominating set. We also study local algorithms on quasi-UDGs, which are a popular generalisation of UDGs, aimed at more realistic modelling of communication between the network nodes. Analysing the local algorithms on quasi-UDGs allows one to assume that the nodes know their coordinates only approximately, up to an additive error. Despite the localisation error, the quality of the solution to problems on quasi-UDGs remains the same as for the case of UDGs with perfect location awareness. We analyse the increase in the local horizon that comes along with moving from UDGs to quasi-UDGs.

Local approximability of max-min and min-max linear programs

In a max-min LP, the objective is to maximise ω subject to Ax ≤ 1, Cx ≥ ω1, and x ≥ 0. In a min-max LP, the objective is to minimise ρ subject to Ax ≤ ρ1, Cx ≥ 1, and x ≥ 0. The matrices A and C are nonnegative and sparse: each row ai of A has at most ΔI positive elements, and each row ck of C has at most ΔK positive elements. We study the approximability of max-min LPs and min-max LPs in a distributed setting; in particular, we focus on local algorithms (constant-time distributed algorithms). We show that for any ΔI ≥ 2, ΔK ≥ 2, and ε > 0 there exists a local algorithm that achieves the approximation ratio ΔI (1 − 1/ΔK) + ε. We also show that this result is the best possible: no local algorithm can achieve the approximation ratio ΔI (1 − 1/ΔK) for any ΔI ≥ 2 and ΔK ≥ 2.

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.

'South-South' Remittance - Poverty reduction nexus. The Case of 'Hadiya' immigrants in South Africa, as Agents of 'Constituence development' in Ethiopia, and the policy implications of their 'remittance instrument'

This thesis explores the link between South-South remittance and development. It attempts to establish improved understanding about the role of immigrants as agents of constituency growth and development. By doing so, it illuminates the dark corners of the policy implications that the unconventional development agency of immigrants might have for countries in the Organization ft Economic Cooperation and Development (OECD). The thesis problematises the existence of state-centric international cooperation as providing the recipe for failed Aid in the face of global poverty menace. In the last half a century, the relative shi' of focus to non-state actors brought about the proliferation of NGOs. That, intrun, helped improve international access to crisis situations; however, their long-term remedial impacts on poverty and development have been contested. Major misgivings for non-governmental organizations (NGOs) are, on one hand, low level goal-bound expenditures and lack of independence from influence of the state, on the other. Therefore, the thesis enterprises to empirically verify its fundamental question whether remitting immigrants constitute an alternative development agency to the traditional players: the State and NGOs. Its main arguments are: due to state's failures in bringing sustainable development in many countries of the South, the future of poverty reduction and development also rests in immigrants' remittances. Nonetheless, in the last decade, remittance security-nexus dominated its discourse. Because of that remittance was viewed as something requiring global regime and restrictions. These temptations to tightly regulate remittance flows carry the danger of overlooking its trans-boundary nature and its strong link with livelihood of the poor. Therefore, to avoid unintended consequences of interventions, there need to be clear policy that bases itself on a discursive knowledge on the issues of North-South and South-South remittances The study involved both literature based and empirical research. It employed Discourse Analysis (C as main method for the former and snow-balling as its approach for the latter. For the first part the thesis constructed three conceptual models, these are: metrological model, police model and ecological model on remittance development-nexus. Through this modeling, the thesis achieved better deconstruction on the concepts remittance, immigrants and development agency. The protagonists of each model, the values and interests they represent, and their main arguments along various lines of dichotomies have been discussed. For instance, the main treats of meteorological model include: it sees remittance as transitional economic variable which require constant speculations and global management; it acts as meteorological station for following up or predicting the level, direction, flow and movement of global remittance. It focuses on official lines and considers the state as legitimate recipient of advic and positive consequence of remittance. On the other hand, police model views remittance as beir at best, development neutral or as an illicit activity requiring global regulations and tight control. Both immigrants and remittance viewed as subversive to establishments. It gives primacy to state stable agent of development and a partner for international cooperation. The anti-thesis to the police model is supplied by ecological model, which this thesis is a part. Ecological model on remittance and immigrants argues that, tight global regulations alone cannot be a panacea for possible abuse of informal remittance system. Ecological model, not only links remittance to poverty reduction, the main trust of development, but also considers the development agency of immigrants as critical factor for 21st century north-south development intervention. It sees immigrants as development conscious and their remittance instrument as most stable flow of finance to the developing countries. Besides, it sees remittance as effective poverty solutions than Foreign Direct Investment and international AID. This thesis focuses on the significance of South-South remittance and investigates the South Africa - Ethiopia remittance corridor, as case study; and empirically verifies the role of Ethiopian (Kembata and Hadiya) immigrants in South Africa as agents of local development back home. The study involved techniques of interview, group discussions, observations and investigative study. It also looked into the determinants of their migration to South Africa, and their remittance to Ethiopia. The theoretical models in the first part of the thesis have been operationalised throughout the empirical part to verify if the Kembata and Hadiya immigrants played the crucial role in their household poverty and local development in comparison with the Ethiopian state and the NGOs involved in the system. As evidenced by the research the thesis has made three distinct contributions to the discourse of remittance development-nexus. Fist, it systematized the debate about linkages between remittance, immigrants, development agency and policy of international cooperation by creating three conceptual models (school of thoughts); second, it singled out remitting immigrants as new agents of development in the South; third, it deconstructed concept of remittance and established South¬South remittance as additional sphere of academic investigation. In addition to the above contributions, the thesis finds that Kembata and Hadiya immigrants have engaged in various developmental activities in their locality than usually anticipated. Hence, it concludes that Ethiopian immigrants constitute an alternative development agency to the state and other non-state actors in their country, and the lesson can be applied to poverty reduction strategies in most developing countries.