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.

An optimal local approximation algorithm for max-min linear programs

In a max-min LP, the objective is to maximise ω subject to Ax ≤ 1, Cx ≥ ω1, and x ≥ 0 for nonnegative matrices A and C. We present a local algorithm (constant-time distributed algorithm) for approximating max-min LPs. The approximation ratio of our algorithm is the best possible for any local algorithm; there is a matching unconditional lower bound.

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.

De "de" : Estudio histórico-comparativo de los usos y la semántica de la preposición "de" en español

El presente estudio supone un intento de describir y analizar el uso de la preposición "de" sobre la base de un corpus diacrónico, con énfasis en las diferentes relaciones semánticas que establece. Partiendo de un total de más de 16.000 casos de "de" hemos establecido 48 categorías de uso, que corresponden a cuatro tipos de construcción sintáctica, a saber, el uso de "de" como complemento de nombres (CN), verbos (CV), adjetivos (CA) y, finalmente, su uso como núcleo de expresiones adverbiales independientes (CI). El estudio consta de tres partes fundamentales. En la parte I, se introduce la Lingüística Cognitiva, que constituye la base teórica esencial del trabajo. Más exactamente, se introducen conceptos como la teoría del prototipo, la teoría de las metáforas conceptuales y la gramática cognitiva, especialmente las ideas de "punto de referencia" y "relación intrínseca" (Langacker 1995, 1999). La parte II incluye el análisis de las 48 categorías. En esta parte se presentan y comentan casi 2.000 ejemplos del uso contextual de "de" extraídos del corpus diacrónico. Los resultados más importantes del análisis pueden resumirse en los siguientes puntos: El uso de "de" sigue siendo esencialmente el mismo en la actualidad que hace 800 años, en el sentido de que todas las 48 categorías se identifican en todas las épocas del corpus. El uso de "de" como complemento nominal va aumentando, al contrario de lo que ocurre con su uso como complemento verbal. En el contexto nominal son especialmente las relaciones posesivas más abstractas las que se hacen más frecuentes, mientras que en el contexto verbal las relaciones que se hacen menos frecuentes son las de separación/alejamiento, causa, agente y partitivo indefinido. Destaca la importancia del siglo XVIII como época de transición entre un primer estado de las cosas y otro posterior, en especial en relación con el carácter cada vez más abstracto de las relaciones posesivas así como con la disminución de las categorías adverbales de causa, agente y partitivo. Pese a la variación en el contexto inmediato de uso, el núcleo semántico de "de" se mantiene inalterado. La parte III toma como punto de partida los resultados del análisis de la parte II, tratando de deslindar el aporte semántico de la preposición "de" a su contexto de uso del valor de la relación en conjunto. Así, recurriendo a la metodología para determinar el significado básico y la metodología para determinar lo que constituyen significados distintos de una preposición (Tyler , Evans 2003a, 2003b), se llega a la hipótesis de que "de" posee cuatro significados básicos, a saber, 'punto de partida', 'tema/asunto', 'parte/todo' y 'posesión'. Esta hipótesis, basada en las metodologías de Tyler y Evans y en los resultados del análisis de corpus, se intenta verificar empíricamente mediante el uso de dos cuestionarios destinados a averiguar hasta qué punto las distinciones semánticas a las que se llega por vía teórica son reconocidas por los hablantes nativos de la lengua (cf. Raukko 2003). El resultado conjunto de los dos acercamientos tanto refuerza como especifica la hipótesis. Los datos que arroja el análisis de los cuestionarios parecen reforzar la idea de que el núcleo semántico de "de" es complejo, constando de los cuatro valores mencionados. Sin embargo, cada uno de estos valores básicos constituye un prototipo local, en torno al cual se construye un complejo de matices semánticos derivados del prototipo. La idea final es que los hablantes son conscientes de los cuatro postulados valores básicos, pero que también distinguen matices más detallados, como son las ideas de 'causa', 'agente', 'instrumento', 'finalidad', 'cualidad', etc. Es decir, "de" constituye un elemento polisémico complejo cuya estructura semántica puede describirse como una semejanza de familia centrada en cuatro valores básicos en torno a los cuales se encuentra una serie de matices más específicos, que también constituyen valores propios de la preposición. Creemos, además, que esta caracterización semántica es válida para todas las épocas de la historia del español, con unas pequeñas modificaciones en el peso relativo de los distintos matices, lo cual está relacionado con la observada variación diacrónica en el uso de "de".