Source author record

Magnús M. Halldórsson

Explore this author’s publications, collaborators and research topics. This catalog record has not been claimed by its author.

ResearcherUnclaimed source record

Data Structures and Algorithms Distributed, Parallel, and Cluster Computing Networking and Internet Architecture math.CO Discrete Mathematics

Catalog footprint

Research overview

9works

5topics

4close collaborators

Actions

Is this your work?

Open graph Browse papers

preprint2022arXiv

Fast Distributed Vertex Splitting with Applications

We present ${\rm poly\log\log n}$ -round randomized distributed algorithms to compute vertex splittings, a partition of the vertices of a graph into $k$ parts such that a node of degree $d(u)$ has $\approx d(u)/k$ neighbors in each part. Our techniques can be seen as the first progress towards general ${\rm poly\log\log n}$ -round algorithms for the Lovász Local Lemma. As the main application of our result, we obtain a randomized ${\rm poly\log\log n}$ -round CONGEST algorithm for $(1+ε)Δ$ -edge coloring $n$ -node graphs of sufficiently large constant maximum degree $Δ$ , for any $ε>0$ . Further, our results improve the computation of defective colorings and certain tight list coloring problems. All the results improve the state-of-the-art round complexity exponentially, even in the LOCAL model.

preprint2022arXiv

Overcoming Congestion in Distributed Coloring

We present a new technique to efficiently sample and communicate a large number of elements from a distributed sampling space. When used in the context of a recent LOCAL algorithm for $(\operatorname{degree}+1)$ -list-coloring (D1LC), this allows us to solve D1LC in $O(\log^5 \log n)$ CONGEST rounds, and in only $O(\log^* n)$ rounds when the graph has minimum degree $Ω(\log^7 n)$ , w.h.p. The technique also has immediate applications in testing some graph properties locally, and for estimating the sparsity/density of local subgraphs in $O(1)$ CONGEST rounds, w.h.p.

preprint2021arXiv

Superfast Coloring in CONGEST via Efficient Color Sampling

We present a procedure for efficiently sampling colors in the {\congest} model. It allows nodes whose number of colors exceeds their number of neighbors by a constant fraction to sample up to $Θ(\log n)$ semi-random colors unused by their neighbors in $O(1)$ rounds, even in the distance-2 setting. This yields algorithms with $O(\log^* Δ)$ complexity for different edge-coloring, vertex coloring, and distance-2 coloring problems, matching the best possible. In particular, we obtain an $O(\log^* Δ)$ -round CONGEST algorithm for $(1+ε)Δ$ -edge coloring when $Δ\ge \log^{1+1/\log^*n} n$ , and a poly( $\log\log n$ )-round algorithm for $(2Δ-1)$ -edge coloring in general. The sampling procedure is inspired by a seminal result of Newman in communication complexity.

preprint2020arXiv

Tight Bounds on Subexponential Time Approximation of Set Cover and Related Problems

We show that Set Cover on instances with $N$ elements cannot be approximated within $(1-γ)\ln N$ -factor in time exp( $N^{γ-δ})$ , for any $0 < γ< 1$ and any $δ> 0$ , assuming the Exponential Time Hypothesis. This essentially matches the best upper bound known by Cygan et al.\ (IPL, 2009) of $(1-γ)\ln N$ -factor in time $exp(O(N^γ))$ . The lower bound is obtained by extracting a standalone reduction from Label Cover to Set Cover from the work of Moshkovitz (Theory of Computing, 2015), and applying it to a different PCP theorem than done there. We also obtain a tighter lower bound when conditioning on the Projection Games Conjecture. We also treat three problems (Directed Steiner Tree, Submodular Cover, and Connected Polymatroid) that strictly generalize Set Cover. We give a $(1-γ)\ln N$ -approximation algorithm for these problems that runs in $exp(\tilde{O}(N^γ))$ time, for any $1/2 \le γ< 1$ .

preprint2015arXiv

Max Point-Tolerance Graphs

A graph $G$ is a \emph{max point-tolerance (MPT)} graph if each vertex $v$ of $G$ can be mapped to a \emph{pointed-interval} $(I_v, p_v)$ where $I_v$ is an interval of $\mathbb{R}$ and $p_v \in I_v$ such that $uv$ is an edge of $G$ iff $I_u \cap I_v \supseteq \{p_u, p_v\}$ . MPT graphs model relationships among DNA fragments in genome-wide association studies as well as basic transmission problems in telecommunications. We formally introduce this graph class, characterize it, study combinatorial optimization problems on it, and relate it to several well known graph classes. We characterize MPT graphs as a special case of several 2D geometric intersection graphs; namely, triangle, rectangle, L-shape, and line segment intersection graphs. We further characterize MPT as having certain linear orders on their vertex set. Our last characterization is that MPT graphs are precisely obtained by intersecting special pairs of interval graphs. We also show that, on MPT graphs, the maximum weight independent set problem can be solved in polynomial time, the coloring problem is NP-complete, and the clique cover problem has a 2-approximation. Finally, we demonstrate several connections to known graph classes; e.g., MPT graphs strictly contain interval graphs and outerplanar graphs, but are incomparable to permutation, chordal, and planar graphs.

preprint2015arXiv

Semi-Transitive Orientations and Word-Representable Graphs

A graph $G=(V,E)$ is a \emph{word-representable graph} if there exists a word $W$ over the alphabet $V$ such that letters $x$ and $y$ alternate in $W$ if and only if $(x,y)\in E$ for each $x\neq y$ . In this paper we give an effective characterization of word-representable graphs in terms of orientations. Namely, we show that a graph is word-representable if and only if it admits a \emph{semi-transitive orientation} defined in the paper. This allows us to prove a number of results about word-representable graphs, in particular showing that the recognition problem is in NP, and that word-representable graphs include all 3-colorable graphs. We also explore bounds on the size of the word representing the graph. The representation number of $G$ is the minimum $k$ such that $G$ is a representable by a word, where each letter occurs $k$ times; such a $k$ exists for any word-representable graph. We show that the representation number of a word-representable graph on $n$ vertices is at most $2n$ , while there exist graphs for which it is $n/2$ .

preprint2014arXiv

Beyond Geometry : Towards Fully Realistic Wireless Models

Signal-strength models of wireless communications capture the gradual fading of signals and the additivity of interference. As such, they are closer to reality than other models. However, nearly all theoretic work in the SINR model depends on the assumption of smooth geometric decay, one that is true in free space but is far off in actual environments. The challenge is to model realistic environments, including walls, obstacles, reflections and anisotropic antennas, without making the models algorithmically impractical or analytically intractable. We present a simple solution that allows the modeling of arbitrary static situations by moving from geometry to arbitrary decay spaces. The complexity of a setting is captured by a metricity parameter Z that indicates how far the decay space is from satisfying the triangular inequality. All results that hold in the SINR model in general metrics carry over to decay spaces, with the resulting time complexity and approximation depending on Z in the same way that the original results depends on the path loss term alpha. For distributed algorithms, that to date have appeared to necessarily depend on the planarity, we indicate how they can be adapted to arbitrary decay spaces. Finally, we explore the dependence on Z in the approximability of core problems. In particular, we observe that the capacity maximization problem has exponential upper and lower bounds in terms of Z in general decay spaces. In Euclidean metrics and related growth-bounded decay spaces, the performance depends on the exact metricity definition, with a polynomial upper bound in terms of Z, but an exponential lower bound in terms of a variant parameter phi. On the plane, the upper bound result actually yields the first approximation of a capacity-type SINR problem that is subexponential in alpha.

preprint2014arXiv

Wireless Scheduling Algorithms in Complex Environments

Efficient spectrum use in wireless sensor networks through spatial reuse requires effective models of packet reception at the physical layer in the presence of interference. Despite recent progress in analytic and simulations research into worst-case behavior from interference effects, these efforts generally assume geometric path loss and isotropic transmission, assumptions which have not been borne out in experiments. Our paper aims to provide a methodology for grounding theoretical results into wireless interference in experimental reality. We develop a new framework for wireless algorithms in which distance-based path loss is replaced by an arbitrary gain matrix, typically obtained by measurements of received signal strength (RSS). Gain matrices allow for the modeling of complex environments, e.g., with obstacles and walls. We experimentally evaluate the framework in two indoors testbeds with 20 and 60 motes, and confirm superior predictive performance in packet reception rate for a gain matrix model over a geometric distance-based model. At the heart of our approach is a new parameter $ζ$ called metricity which indicates how close the gain matrix is to a distance metric, effectively measuring the complexity of the environment. A powerful theoretical feature of this parameter is that all known SINR scheduling algorithms that work in general metric spaces carry over to arbitrary gain matrices and achieve equivalent performance guarantees in terms of $ζ$ as previously obtained in terms of the path loss constant. Our experiments confirm the sensitivity of $ζ$ to the nature of the environment. Finally, we show analytically and empirically how multiple channels can be leveraged to improve metricity and thereby performance. We believe our contributions will facilitate experimental validation for recent advances in algorithms for physical wireless interference models.

preprint2012arXiv

Algorithms for Wireless Capacity

In this paper we address two basic questions in wireless communication: First, how long does it take to schedule an arbitrary set of communication requests? Second, given a set of communication requests, how many of them can be scheduled concurrently? Our results are derived in an interference model with geometric path loss and consist of efficient algorithms that find a constant approximation for the second problem and a logarithmic approximation for the first problem. In addition, we analyze some important properties of the interference model and show that it is robust to various factors that can influence the signal attenuation. More specifically, we prove that as long as such influences on the signal attenuation are constant, they affect the capacity only by a constant factor.

Inspect adjacent papers, topics, institutions and collaborators without losing the researcher page.

Building this map preview

BZPEER is loading the nearby papers, people, topics and institutions for this page.