Reed [J. Comb. Theory B, 1999] showed that graphs of maximum degree Δ ⩾ 10^14 without Δ-cliques are (Δ-1)-colorable. We design a one-pass semi-streaming algorithm for computing such a coloring. Additionally, we prove that any one-pass (Δ-k)-coloring algorithm for 0 ⩽ k < (Δ+1)/2 requires Ω(n(k+1)) space.

We consider the Unit Interval Selection problem in the one-pass random order streaming model. In this setting, an algorithm is presented with a sequence of n unit-length intervals on the line that arrive in uniform random order, one at a time, and the objective is to output (an approximation of) a largest set of disjoint intervals using space linear in the size of an optimal solution. Previous work only considered adversarially ordered streams and established that, within these space constraints, a (2/3)-approximation can be achieved in such streams, and this is best possible, in that going beyond such an approximation factor requires space Ω(n) [Emek et al., TALG'16]. In this work, we show that an improved expected approximation factor can be achieved if the input stream is in uniform random order, where the expectation is taken over the stream order. More specifically, we give a one-pass streaming algorithm with expected approximation factor 0.7401 that uses space O(|OPT|), where OPT denotes an optimal solution. We also show that random order algorithms with expected approximation factor above 8/9 require space Ω(n), and algorithms that compute a better than 2/3-approximation with probability above 2/3 also require Ω(n) space. On a technical level, we design an algorithm for the restricted domain [0, Δ), for some constant Δ, and use standard techniques to obtain an algorithm for unrestricted domains. For the restricted domain [0, Δ), we run O(Δ) recursive instances of our algorithm, with each instance targeting the situation where a specific interval of an optimal solution arrives first. We establish the interesting property of our algorithm that it performs worst when the input stream consists solely of a set of independent intervals. It then remains to analyse the algorithm on these simple instances. Our lower bound is proved via communication complexity arguments, similar in spirit to the robust communication lower bounds established by [Chakrabarti et al., Theory Comput. 2016].

Publisher Copyright: © 2026 Copyright held by the owner/author(s).

We improve the space bound for streaming approximation of Diameter but also of Farthest Neighbor queries, Minimum Enclosing Ball and its Coreset, in high-dimensional Euclidean spaces. In particular, our deterministic streaming algorithms store $\mathcal{O}(\varepsilon^{-2}\log(\frac{1}{\varepsilon}))$ points. This improves by a factor of $\varepsilon^{-1}$ the previous space bound of Agarwal and Sharathkumar (SODA 2010), while offering a simpler and more complete argument. We also show that storing $Ω(\varepsilon^{-1})$ points is necessary for a $(\sqrt{2}+\varepsilon)$-approximation of Farthest Pair or Farthest Neighbor queries.

We consider the problem of maintaining a proper $(Δ+ 1)$-vertex coloring in a graph on $n$-vertices and maximum degree $Δ$ undergoing edge insertions and deletions. We give a randomized algorithm with amortized update time $\widetilde{O}( n^{2/3} )$ against adaptive adversaries, meaning that updates may depend on past decisions by the algorithm. This improves on the very recent $\widetilde{O}( n^{8/9} )$-update-time algorithm by Behnezhad, Rajaraman, and Wasim (SODA 2025) and matches a natural barrier for dynamic $(Δ+1)$-coloring algorithms. The main improvements are in the densest regions of the graph, where we use structural hints from the study of distributed graph algorithms.

Graph coloring is fundamental to distributed computing. We give the first sub-logarithmic distributed algorithm for coloring cluster graphs. These graphs are obtained from the underlying communication network by contracting nodes and edges, and they appear frequently as components in the study of distributed algorithms. In particular, we give a O (log* n)-round algorithm to (Δ + 1)-color cluster graphs of at least polylogarithmic degree. The previous best bound known was poly(log n) [Flin et al., SODA'24]. This properly generalizes results in the CONGEST model and shows that distributed graph problems can be solved quickly even when the node itself is decentralized.

The celebrated palette sparsification result of [Assadi, Chen, and Khanna SODA’19] shows that to compute a Δ + 1 coloring of the graph, where Δ denotes the maximum degree, it suffices if each node limits its color choice to O(log n) independently sampled colors in {1, 2,…, Δ + 1}. They showed that it is possible to color the resulting sparsified graph—the spanning subgraph with edges between neighbors that sampled a common color, which are only Õ(n) edges—and obtain a Δ + 1 coloring for the original graph. However, to compute the actual coloring, that information must be gathered at a single location for centralized processing. We seek instead a local algorithm to compute such a coloring in the sparsified graph. The question is if this can be achieved in poly (log n) distributed rounds with small messages.

Graph coloring is fundamental to distributed computing. We give the first general treatment of the coloring of virtual graphs, where the graph $H$ to be colored is locally embedded within the communication graph $G$. Besides generalizing classical distributed graph coloring (where $H=G$), this captures other previously studied settings, including cluster graphs and power graphs. We find that the complexity of coloring a virtual graph depends on the edge congestion of its embedding. The main question of interest is how fast we can color virtual graphs of constant congestion. We find that, surprisingly, these graphs can be colored nearly as fast as ordinary graphs. Namely, we give a $O(\log^4\log n)$-round algorithm for the deg+1-coloring problem, where each node is assigned more colors than its degree. This can be viewed as a case where a distributed graph problem can be solved even when the operation of each node is decentralized.

We consider the problem of coloring graphs of maximum degree $Δ$ with $Δ$ colors in the distributed setting with limited bandwidth. Specifically, we give a $\mathsf{poly}\log\log n$-round randomized algorithm in the CONGEST model. This is close to the lower bound of $Ω(\log \log n)$ rounds from [Brandt et al., STOC '16], which holds also in the more powerful LOCAL model. The core of our algorithm is a reduction to several special instances of the constructive Lovász local lemma (LLL) and the $deg+1$-list coloring problem.

Abstract We study the Online Multiset Submodular Cover problem (OMSC), where we are given a universe U of elements and a collection of subsets $$\mathcal {S}\subseteq 2^U$$ S ⊆ 2 U . Each element $$u_j \in U$$ u j ∈ U is associated with a nonnegative, nondecreasing, submodular polynomially computable set function $$f_j$$ f j . Initially, the elements are uncovered, and therefore we pay a penalty per each unit of uncovered element. Subsets with various coverage and cost arrive online. Upon arrival of a new subset, the online algorithm must decide how many copies of the arriving subset to add to the solution. This decision is irrevocable, in the sense that the algorithm will not be able to add more copies of this subset in the future. On the other hand, the algorithm can drop copies of a subset, but such copies cannot be retrieved later. The goal is to minimize the total cost of subsets taken plus penalties for uncovered elements. We present an $$O(\sqrt{\rho _{\max }})$$ O ( ρ max ) -competitive algorithm for OMSC that does not dismiss subset copies that were taken into the solution, but relies on prior knowledge of the value of $$\rho _{\max }$$ ρ max , where $$\rho _{\max }$$ ρ max is the maximum ratio, over all subsets, between the penalties covered by a subset and its cost. We provide an $$O\left( \log (\rho _{\max }) \sqrt{\rho _{\max }} \right) $$ O log ( ρ max ) ρ max -competitive algorithm for OMSC that does not rely on advance knowledge of $$\rho _{\max }$$ ρ max but uses dismissals of previously taken subsets. Finally, for the capacitated versions of the Online Multiset Multicover problem, we obtain an $$O(\sqrt{\rho _{\max }'})$$ O ( ρ max ′ ) -competitive algorithm when $$\rho _{\max }'$$ ρ max ′ is known and an $$O\left( \log (\rho _{\max }') \sqrt{\rho _{\max }'} \right) $$ O log ( ρ max ′ ) ρ max ′ -competitive algorithm when $$\rho _{\max }'$$ ρ max ′ is unknown, where $$\rho _{\max }'$$ ρ max ′ is the maximum ratio over all subset incarnations between the penalties covered by this incarnation and its cost.

We give a randomized Δ-coloring algorithm in the LOCAL model that runs in poly log log n rounds, where n is the number of nodes of the input graph and Δ is its maximum degree. This means that randomized Δ-coloring is a rare distributed coloring problem with an upper and lower bound in the same ballpark, poly log log n, given the known Ω(logΔ logn) lower bound [Brandt et al., STOC '16].

We present an O(log3 log n)-round distributed algorithm for the (Δ + 1)-coloring problem, where each node broadcasts only one O(log n)-bit message per round to its neighbors. Previously, the best such broadcast-based algorithm required O(log n) rounds. If Δ ∈ Ω(log 3 n), our algorithm runs in O(log* n) rounds. Our algorithm's round complexity matches the state-of-the-art in the much more powerful CONGEST model [Halldórsson et al., STOC'21 & PODC'22], where each node sends one different message to each of its neighbors, thus sending up to Θ(n log n) bits per round. This is the best complexity known, even if message sizes are unbounded.

We provide a $O(\log^6 \log n)$-round randomized algorithm for distance-2 coloring in CONGEST with $Δ^2+1$ colors. For $Δ\gg\operatorname{poly}\log n$, this improves exponentially on the $O(\logΔ+\operatorname{poly}\log\log n)$ algorithm of [Halldórsson, Kuhn, Maus, Nolin, DISC'20]. Our study is motivated by the ubiquity and hardness of local reductions in CONGEST. For instance, algorithms for the Local Lovász Lemma [Moser, Tardos, JACM'10; Fischer, Ghaffari, DISC'17; Davies, SODA'23] usually assume communication on the conflict graph, which can be simulated in LOCAL with only constant overhead, while this may be prohibitively expensive in CONGEST. We hope our techniques help tackle in CONGEST other coloring problems defined by local relations.

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 (degree +1)-list-coloring (D1LC), this allows us to solve D1LC in O(log5 logn) Congest rounds, and in only O(log* n) rounds when the graph has minimum degree Ω(log7 n), w.h.p.

We present a new approach to randomized distributed graph coloring that is simpler and more efficient than previous ones. In particular, it allows us to tackle the (deg+1)-list-coloring (D1LC) problem, where each node v of degree dv is assigned a palette of dv+1 colors, and the objective is to find a proper coloring using these palettes. While for (Δ+1)-coloring (where Δ is the maximum degree), there is a fast randomized distributed O(log3logn)-round algorithm due to Chang, Li, and Pettie, no o(logn)-round algorithms are known for the D1LC problem.

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.

Distributed vertex coloring is one of the classic problems and probably also the most widely studied problems in the area of distributed graph algorithms. We present a new randomized distributed vertex coloring algorithm for the standard CONGEST model, where the network is modeled as an n-node graph G, and where the nodes of G operate in synchronous communication rounds in which they can exchange O(logn)-bit messages over all the edges of G. For graphs with maximum degree Δ, we show that the (Δ+1)-list coloring problem (and therefore also the standard (Δ+1)-coloring problem) can be solved in O(log5logn) rounds. Previously such a result was only known for the significantly more powerful LOCAL model, where in each round, neighboring nodes can exchange messages of arbitrary size. The best previous (Δ+1)-coloring algorithm in the CONGEST model had a running time of O(logΔ + log6logn) rounds. As a function of n alone, the best previous algorithm therefore had a round complexity of O(logn), which is a bound that can also be achieved by a na'ive folklore algorithm. For large maximum degree Δ, our algorithm hence is an exponential improvement over the previous state of the art.

An overarching issue in resource management of wireless networks is assessing their capacity: How much communication can be achieved in a network, utilizing all the tools available: power control, scheduling, routing, channel assignment, and rate adjustment? We propose the first framework for approximation algorithms in the physical model of wireless interference that addresses these questions in full in interference-limited networks. The approximations obtained are at most doubly logarithmic in the link length and rate diversity. Where previous bounds are known, this gives an exponential improvement or better. The key insight is the discovery that a properly chosen power assignment infers a form of locality, or tolerance to the interference of both shorter and longer communication links. This allows us to simplify the complex interference relationship of the physical model into a new form of conflict graphs, at a small cost. We also show that the approximation obtained is provably the best possible for any conflict graph formulation.

We develop randomized distributed algorithms for many of the most fundamental communication problems in wireless networks under the Signal to Interference and Noise Ratio (SINR) model of communication, including (multi-message) broadcast, local broadcast, coloring, Maximal Independent Set, and aggregation. The complexity of our algorithms is optimal up to polylogarithmic preprocessing time. It shows—contrary to expectation—that the plain vanilla SINR model is just as powerful and fast (modulo the preprocessing) as various extensions studied, including power control, carrier sense, collision detection, free acknowledgements, and geolocation knowledge. Central to these results is an efficient construction of a constant-density backbone structure over the network, which is of independent interest. This is achieved using an indirect sensing technique, where message non-reception is used to deduce information about relative node-distances.

We give efficient randomized and deterministic distributed algorithms for computing a distance-2 vertex coloring of a graph G in the CONGEST model. In particular, if Δ is the maximum degree of G, we show that there is a randomized CONGEST model algorithm to compute a distance-2 coloring of G with Δ2 + 1 colors in O(log Δ · log n) rounds. Further if the number of colors is slightly increased to (1 + ∈)Δ2 for some ∈ > 1/polylog n, we show that it is even possible to compute a distance-2 coloring deterministically in polylog n time in the CONGEST model. Finally, we give a O(Δ2 + log* n)-round deterministic CONGEST algorithm to compute distance-2 coloring with Δ2 + 1 colors.

We give an improved randomized CONGEST algorithm for distance-$2$ coloring that uses $Δ^2+1$ colors and runs in $O(\log n)$ rounds, improving the recent $O(\log Δ\cdot \log n)$-round algorithm in [Halldórsson, Kuhn, Maus; PODC '20]. We then improve the time complexity to $O(\log Δ) + 2^{O(\sqrt{\log\log n})}$.

We study the problem of sorting under incomplete information, when queries are used to resolve uncertainties. Each of n data items has an unknown value, which is known to lie in a given interval. We can pay a query cost to learn the actual value, and we may allow an error threshold in the sorting. The goal is to find a nearly-sorted permutation by performing a minimum-cost set of queries. We show that an offline optimum query set can be found in polynomial time, and that both oblivious and adaptive problems have simple query-competitive algorithms. The query-competitiveness for the oblivious problem is n for uniform query costs, and unbounded for arbitrary costs; for the adaptive problem, the ratio is 2. We then present a unified adaptive strategy for uniform query costs that yields: (i) a 3/2-query-competitive randomized algorithm; (ii) a 5/3-query-competitive deterministic algorithm if the dependency graph has no 2-components after some preprocessing, which has query-competitive ratio 3/2 + O(1/k) if the components obtained have size at least k; (iii) an exact algorithm if the intervals constitute a laminar family. The first two results have matching lower bounds, and we have a lower bound of 7/5 for large components. We also show that the advice complexity of the adaptive problem is floor[n/2] if no error threshold is allowed, and ceil[n/3 * lg 3] for the general case.

The minimum degree spanning tree (MDST) problem requires the construction of a spanning tree T for graph G, such that the maximum degree of T is the smallest among all spanning trees of G. Let d be this MDST degree for a given graph. In this paper, we present a randomized distributed approximation algorithm for the MDST problem that constructs a spanning tree with maximum degree in O(d+log n ). With high probability in n, the algorithm runs in O((D + √n) log4 n) rounds, in the broadcast-CONGEST model, where D is the graph diameter and n is the graph size. We then show how to derandomize this algorithm, obtaining the same asymptotic guarantees on degree and time complexity, but now requiring the standard CONGEST model. Although efficient approximation algorithms for the MDST problem have been known in the sequential setting since the 1990's (finding an exact solution is NP-hard), our algorithms are the first efficient distributed solutions. We conclude by proving a lower bound that establishes that any randomized MDST algorithm that guarantees a maximum degree in ∼Ω (d) requires &Ø#8764;Ω (n1/3) rounds, and any deterministic solution requires ∼Ω (n1/2) rounds. These bounds proves our deterministic algorithm to be asymptotically optimal, and eliminates the possibility of significantly more efficient randomized solutions.

We develop randomized distributed algorithms for many of the most fundamental communication problems in the wireless SINR model, including (multi-message) broadcast, local broadcast, coloring, MIS, and aggregation. The complexity of the algorithms is optimal up to polylogarithmic preprocessing time. It shows -- contrary to expectation -- that the plain vanilla SINR model is just as powerful and fast (modulo the preprocessing) as various extensions studied, including power control, carrier sense, collision detection, free acknowledgements, and GPS location. A key component of the algorithms is an efficient simulation of CONGEST algorithms on a constant-density SINR backbone.

We study three capacity problems in the mobile telephone model, a network abstraction that models the peer-to-peer communication capabilities implemented in most commodity smartphone operating systems. The capacity of a network expresses how much sustained throughput can be maintained for a set of communication demands, and is therefore a fundamental bound on the usefulness of a network. Because of this importance, wireless network capacity has been active area of research for the last two decades. The three capacity problems that we study differ in the structure of the communication demands. The first problem is pairwise capacity, where the demands are (source, destination) pairs. Pairwise capacity is one of the most classical definitions, as it was analyzed in the seminal paper of Gupta and Kumar on wireless network capacity. The second problem we study is broadcast capacity, in which a single source must deliver packets to all other nodes in the network. Finally, we turn our attention to all-to-all capacity, in which all nodes must deliver packets to all other nodes. In all three of these problems we characterize the optimal achievable throughput for any given network, and design algorithms which asymptotically match this performance. We also study these problems in networks generated randomly by a process introduced by Gupta and Kumar, and fully characterize their achievable throughput. Interestingly, the techniques that we develop for all-to-all capacity also allow us to design a one-shot gossip algorithm that runs within a polylogarithmic factor of optimal in every graph. This largely resolves an open question from previous work on the one-shot gossip problem in this model.

We study the effects of stochastic shadowing on scheduling in wireless networks. Previous work has generally assumed that shadowing affects different signals independently. Concentrating on “compact” networks, where very little or no spatial reuse is possible, such as in indoor environments, we form a model of correlation between the shadowing components for different signals. We analyze two fundamental measures: the maximum number of simultaneous transmitting links, and the fewest time/frequency slots or channels needed to schedule all the links. Based on the correlation model, we characterize (up to constant factors) how these measures scale with correlation strength and the number of links. We also give nearly optimal algorithms to compute such schedules, as well as to optimize the maximum weighted sum of simultaneously transmitting links. The latter can as well be extended to arbitrary sets of similar length links, under a suitable model of correlations, by partitioning them into compact subsets.

We introduce the problem of finding a spanning tree along with a partition of the tree edges into fewest number of feasible sets, where constraints on the edges define feasibility. The motivation comes from wireless networking, where we seek to model the irregularities seen in actual wireless environments. Not all node pairs may be able to communicate, even if geographically close --- thus, the available pairs are modeled with a link graph $\mathcal{L}=(V,E)$. Also, signal attenuation need not follow a nice geometric formulas --- hence, interference is modeled by a conflict (hyper)graph $\mathcal{C}=(E,F)$ on the links. The objective is to maximize the efficiency of the communication, or equivalently minimizing the length of a schedule of the tree edges in the form of a coloring. We find that in spite of all this generality, the problem can be approximated linearly in terms of a versatile parameter, the inductive independence of the interference graph. Specifically, we give a simple algorithm that attains a $O(ρ\log n)$-approximation, where $n$ is the number of nodes and $ρ$ is the inductive independence, and show that near-linear dependence on $ρ$ is also necessary. We also treat an extension to Steiner trees, modeling multicasting, and obtain a comparable result. Our results suggest that several canonical assumptions of geometry, regularity and "niceness" in wireless settings can sometimes be relaxed without a significant hit in algorithm performance.

One of the most fundamental tasks in sensor networks is the computation of a (compressible) aggregation function of the input measurements. What rate of computation can be maintained, by properly choosing the aggregation tree, the TDMA schedule of the tree edges, and the transmission powers? This can be viewed as the convergecast capacity of a wireless network. We show here that the optimal rate is effectively a constant. This holds even in arbitrary networks, under the physical model of interference. This compares with previous bounds that are logarithmic (e.g., Ω(1/log n)). Namely, we show that a rate of Ω(1/log* Δ) is possible, where Δ is the length diversity (ratio between the furthest to the shortest distance between nodes). It also implies that the scheduling complexity of wireless connectivity is O(log* Δ). This is achieved using the natural minimum spanning tree (MST). Our method crucially depends on choosing the appropriate power assignment for the instance at hand, since without power control, only a trivial O(1/n) rate can be guaranteed. We also show that there is a fixed power assignment that allows for a rate of Δ(1/log log Δ). Surprisingly, these bounds are essentially best possible. No aggregation network can guarantee a rate better than O(1/log log Δ) using fixed power assignment. Also, when using arbitrary power control, there are instances whose MSTs cannot be scheduled in fewer than Ω(1/log* Δ) slots.

We bound the performance guarantees that follow from Turán-like bounds for unweighted and weighted independent sets in bounded-degree graphs. In particular, a randomized approach of Boppana forms a simple 1-round distributed algorithm, as well as a streaming and preemptive online algorithm. We show it gives a tight (Δ+1)/2-approximation in unweighted graphs of maximum degree Δ, which is best possible for 1-round distributed algorithms. For weighted graphs, it gives only a (Δ+1)-approximation, but a simple modification results in an asymptotic expected 0.529(Δ+1)-approximation.

The physical (or SINR) model of wireless communication is more intricate than radio networks and still not well understood. If two neighbors of a node are transmitting, the node may be able to decode one of the transmissions, depending on the relative nearness of the transmitters. Thus, even the lack of proper reception carries indirect information. We explore here the power of such indirect signaling to infer the approximate topology of the network. In particular, we obtain a polylogarithmic time algorithm to compute a backbone: a set of nodes of constant density that dominates every ε-neighborhood. A backbone has wide utility for information dissemination, functioning as a sparse spanner. It also leads to fast broadcast, running in O(Diameter) time after a polylogarithmic precomputation, which previously was only known when additional features such as carrier sense, collision detection, geometric coordinates, or power control were available.

Independent sets play a central role in distributed algorithmics. We examine here the minimal requirements for computing non-trivial independent sets. In particular, we focus on algorithms that operate in a single communication round. A classic result of Linial shows that a constant number of rounds does not suffice to compute a maximal independent set. We are therefore interested in the size of the solution that can be computed, especially in comparison to the optimal. Our main result is a randomized one-round algorithm that achieves poly-logarithmic approximation on graphs of polynomially bounded-independence. Specifically, we show that the algorithm achieves the Caro-Wei bound (an extension of the Turán bound for independent sets) in general graphs up to a constant factor, and that the Caro-Wei bound yields a poly-logarithmic approximation on bounded-independence graphs. The algorithm uses only a single bit message and operates in a beeping model, where a node receives only the disjunction of the bits transmitted by its neighbors. We give limitation results that show that these are the minimal requirements for obtaining non-trivial solutions. In particular, a sublinear approximation cannot be obtained in a single round on general graphs, nor when nodes cannot both transmit and receive messages. We also show that our analysis of the Caro-Wei bound on polynomially bounded-independence graphs is tight, and that the poly-logarithmic approximation factor does not extend to $$\mathrm {O}(1)$$ -claw free graphs.

Dynamic behavior is an essential part of wireless networking, due mobility, environmental changes or failures. We analyze a natural exponential backoff procedure to manage contention in a fading channel, in the presence of both node churn and link changes. We show that it attains a fast convergence, stabilizing contention from any state in logarithmic time. We use it to obtain optimal algorithm for Local Broadcast that even improves known results for the static case. The results illustrate the utility of carrier sensing, a stock feature of wireless nodes.

We consider the following basic link capacity (a.k.a., one-shot scheduling) problem in wireless networks: Given a set of communication links, find a maximum subset of links that can successfully transmit simultaneously. Good performance guarantees are known only for deterministic models, such as the physical model with geometric (log-distance) pathloss. We treat this problem under stochastic shadowing under general distributions, bound the effects of shadowing on optimal capacity, and derive constant approximation algorithms. We also consider temporal fading under Rayleigh distribution, and show that it affects non-fading solutions only by a constant-factor. These can be combined into a constant approximation link capacity algorithm under both time-invariant shadowing and temporal fading.

One of the most fundamental tasks in sensor networks is the computation of a (compressible) aggregation function of the input measurements. What rate of computation can be maintained, by properly choosing the aggregation tree, the TDMA schedule of the tree edges, and the transmission powers? We show here that the optimal rate is effectively a constant. This holds even in arbitrary networks, under the physical model of interference. Namely, we show that a rate of Ω(1/log* Δ) and Ω(1/log log Δ) is possible in the global power control and "oblivious" power control modes, respectively, where Δ is the length diversity (ratio between the furthest to the shortest distance between nodes), while without power control, only a trivial linear rate can be guaranteed.. We further show that these (worst-case) bounds are best possible.

In this article, we study the leader election problem in the Signal-to-Interference-plus-Noise-Ratio (SINR) model where nodes can adjust their transmission power. We show that in this setting it is possible to solve the leader election problem in two communication rounds, with high probability. Previously, it was known that Omega(log n) rounds were sufficient and necessary when using uniform power, where n is the number of nodes in the network.

In this paper we study the problem of developing efficient distributed algorithms for dense wireless networks. For many problems in this setting, fast solutions must leverage the reality that radio signals fade with distance, which can be exploited to enable concurrent communication among multiple sender/receiver pairs. To simplify the development of these algorithms we describe a new communication abstraction called FadingMAC which exposes the benefits of this concurrent communication, but also hides the details of the underlying low-level radio signal behavior. This approach splits efforts between those who develop useful algorithms that run on the abstraction, and those who implement the abstraction in concrete low-level wireless models, or on real hardware. After defining FadingMAC, we describe and analyze an efficient implementation of the abstraction in a standard low-level SINR-style network model. We then describe solutions to the following problems that run on the abstraction: max, min, sum, and mean computed over input values; process renaming; consensus and leader election; and optimal packet scheduling. Combining our abstraction implementation with these applications that run on the abstraction, we obtain near-optimal solutions to these problems in our low-level SINR model - significantly advancing the known results for distributed algorithms in this setting. Of equal importance to these concrete bounds, however, is the general idea advanced by this paper: as wireless networks become more dense, both theoreticians and practitioners must explore new communication abstractions that can help tame this density.

We study a fundamental measure for wireless interference in the signal-to-interference noise ratio model known as (weighted) inductive independence. This measure characterizes the effectiveness of using oblivious power---when the power used by a transmitter only depends on the distance to the receiver---as a mechanism for improving wireless capacity. We prove optimal bounds for inductive independence, implying a number of algorithmic applications. An algorithm is provided that achieves capacity that is---due to existing lower bounds---asymptotically best possible using oblivious power assignments. Improved approximation algorithms are provided for a number of problems involving both oblivious power and arbitrary power control, including connectivity, secondary spectrum auctions, and dynamic packet scheduling. We also show that the price of oblivious power---the relative increase in capacity possible when using unconstrained power control---is only doubly logarithmic in the maximum link length.

We show that the first phase of the Linial-Saks network decomposition algorithm gives a randomized distributed O(nε)-approximation algorithm for the maximum independent set problem that operates in O(1/ε) rounds, and we give a matching lower bound that holds even for bipartite graphs.

announcement Share on Brief Announcement: Data Dissemination in Unified Dynamic Wireless Networks Authors: Magnus M. Halldórsson Reykjavik University, Reykjavik, Iceland Reykjavik University, Reykjavik, IcelandView Profile , Tigran Tonoyan Reykjavik University, Reykjavik, Iceland Reykjavik University, Reykjavik, IcelandView Profile , Yuexuan Wang Zhejiang University, Hangzhou, China Zhejiang University, Hangzhou, ChinaView Profile , Dongxiao Yu Huazhong University of Science and Technology, Wuhan, China Huazhong University of Science and Technology, Wuhan, ChinaView Profile Authors Info & Claims PODC '16: Proceedings of the 2016 ACM Symposium on Principles of Distributed ComputingJuly 2016 Pages 199–201https://doi.org/10.1145/2933057.2933065Published:25 July 2016Publication History 1citation132DownloadsMetricsTotal Citations1Total Downloads132Last 12 Months6Last 6 weeks0 Get Citation AlertsNew Citation Alert added!This alert has been successfully added and will be sent to:You will be notified whenever a record that you have chosen has been cited.To manage your alert preferences, click on the button below.Manage my AlertsNew Citation Alert!Please log in to your account Save to BinderSave to BinderCreate a New BinderNameCancelCreateExport CitationPublisher SiteGet Access

To develop algorithms and protocol for wireless mesh networks, one needs good models, especially capturing the defining aspect of the wireless medium: interference. The model should be simple and general, yet realistic. We survey here the various modeling aspects, focusing particularly on recent work involving physical models.

We study streaming algorithms for the interval selection problem: finding a maximum cardinality subset of disjoint intervals on the line. A deterministic 2-approximation streaming algorithm for this problem is developed, together with an algorithm for the special case of proper intervals, achieving improved approximation ratio of 3/2. We complement these upper bounds by proving that they are essentially the best possible in the streaming setting: It is shown that an approximation ratio of 2 − ϵ (or 3/2 − ϵ for proper intervals) cannot be achieved unless the space is linear in the input size. In passing, we also answer an open question of Adler and Azar (J. Scheduling 2003) regarding the space complexity of constant-competitive randomized preemptive online algorithms for the same problem.

We consider the problem of scheduling wireless links in the physical model, where we seek an assignment of power levels and a partition of the given set of links into the minimum number of subsets satisfying the signal-to-interference-and-noise-ratio (SINR) constraints. Specifically, we are interested in the efficiency of local power assignment schemes, or oblivious power schemes, in approximating wireless scheduling. Oblivious power schemes are motivated by networking scenarios when power levels must be decided in advance, and not as part of the scheduling computation. We present the first O(log log Delta)-approximation algorithm, which is known to be best possible (in terms of Delta) for oblivious power schemes, where Delta is the longest to shortest link length ratio. We achieve this by representing interference by a conflict graph, which allows the application of graph-theoretic results for a variety of related problems, including the weighted capacity problem. We explore further the contours of approximability and find the choice of power assignment matters; that not all metric spaces are equal; and that the presence of weak links makes the problem harder. Combined, our results resolve the price of local power for wireless scheduling, or the value of allowing unfettered power control.

We consider the k-Service Assignment problem (k-SA), defined as follows. The input consists of a network that contains servers and clients, and an integer k. Each server has a finite capacity, and each client is associated with a demand and a profit. A feasible solution is an assignment of clients to neighboring servers such that (i) the total demand assigned to a server is at most its capacity, and (ii) a client is assigned either to k servers or to none. The profit of an assignment is the total profit of clients that are assigned to k servers, and the goal is to find a maximum profit assignment. In the r-restricted version of k-SA, no client requires more than an r-fraction of the capacity of any adjacent server. The k-SA problem is motivated by backup placement in networks and by resource allocation in 4G cellular networks. It can also be viewed as machine scheduling on related machines with assignment restrictions. We present a centralized polynomial time greedy (k+1-r)/(1-r)-approximation algorithm for r-restricted k-SA. We then show that a variant of this algorithm achieves an approximation ratio of k+1 using a resource augmentation factor of 1+r. We use the latter to present a (k+1)^2-approximation algorithm for k-SA. In the distributed setting, we present: (i) a (1+epsilon)*(k +1-r)/(1-r)-approximation algorithm for r-restricted k-SA, (ii) a (1+epsilon)(k+1)-approximation algorithm that uses a resource augmentation factor of 1+r for r-restricted k-SA, both for any constant epsilon>0, and (iii) an O{k^2}-approximation algorithm for k-SA (in expectation). The three distributed algorithms compute a solution with high probability and terminate in O(k^2 *log^3(n)) rounds.

We present the first algorithm that implements an abstract MAC (absMAC) layer in the Signal-to-Interference-plus-Noise-Ratio (SINR) wireless network model. We first prove that efficient SINR implementations are not possible for the standard absMAC specification. We modify that specification to an "approximate" version that better suits the SINR model. We give an efficient algorithm to implement the modified specification, and use it to derive efficient algorithms for higher-level problems of global broadcast and consensus.

We explore the utility of multiple channels of communication in wireless networks under the SINR model of interference. The central question is whether multiple channels can result in linear speedup, up to some fundamental limit. We answer this question affirmatively for the data aggregation problem, perhaps the most fundamental problem in sensor networks. To achieve this, we form a hierarchical structure of independent interest, and illustrate its versatility by obtaining a new algorithm with linear speedup for the node coloring problem.

We consider the backup placement problem, defined as follows. Some nodes (processors) in a given network have objects (e.g., files, tasks) whose backups should be stored in additional nodes for increased fault resilience. To minimize the disturbance in case of a failure, it is required that a backup copy should be located at a neighbor of the primary node. The goal is to find an assignment of backup copies to nodes which minimizes the maximum load (number or total size of copies) over all nodes in the network. It is known that a natural selfish local improvement policy has approximation ratio Ω(log n / log log n); we show that it may take this policy Ω(√n) time to reach equilibrium in the distributed setting. Our main result in this paper is a distributed algorithm which finds a placement in polylogarithmic time and achieves approximation ratio O(log n/log log n). We obtain this result using a distributed approximation algorithm for f-matching in bipartite graphs that may be of independent interest.

Efficient use of a wireless network requires that transmissions be grouped into feasible sets, where feasibility means that each transmission can be successfully decoded in spite of the interference caused by simultaneous transmissions. Feasibility is most closely modeled by a signal-to-interference-plus-noise (SINR) formula, which unfortunately is conceptually complicated, being an asymmetric, cumulative, many-to-one relationship. We re-examine how well graphs can capture wireless receptions as encoded in SINR relationships, placing them in a framework in order to understand the limits of such modelling. We seek for each wireless instance a pair of graphs that provide upper and lower bounds on the feasibility relation, while aiming to minimize the gap between the two graphs. The cost of a graph formulation is the worst gap over all instances, and the price of (graph) abstraction is the smallest cost of a graph formulation. We propose a family of conflict graphs that is parameterized by a non-decreasing sub-linear function, and show that with a judicious choice of functions, the graphs can capture feasibility with a cost of O(log* Δ), where Δ is the ratio between the longest and the shortest link length. This holds on the plane and more generally in doubling metrics. We use this to give greatly improved O(log* Δ)-approximation for fundamental link scheduling problems with arbitrary power control. We also explore the limits of graph representations and find that our upper bound is tight: the price of graph abstraction is Ω(log* Δ). In addition, we give strong impossibility results for general metrics, and for approximations in terms of the number of links.

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.

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 framework for the maximum flow problem in wireless networks using the SINR interference model in combination with MIMO nodes. The performance ratio of our algorithm matches the best O(log n) approximation factor known for the pure flow problem, but avoids the impractical dependence on the ellipsoid method and features both simpler and more intuitive analysis. The objective of a maximum flow in wireless networks is to get as much information from a sender to a receiver using intermediate nodes in a multi-hop environment. The algorithm is based on an LP formulation of the flow problem, and handles gracefully all additional linear constraints. The set of constraints that can be included contains, among other, power limits, fairness between source-sink pairs, capacity limits and bounds, and the use of Multi-Input Multi-Output nodes for the source and the sink nodes, which are often the bottlenecks in a wireless flow.

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 the signal-to-interference-plus-noise ratio (SINR) 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 show that the interference model is robust to various factors that can influence the signal attenuation. More specifically, we prove that as long as influences on the signal attenuation are constant, they affect the capacity only by a constant factor.

We present randomized distributed algorithms for connectivity and aggregation in multi-hop wireless networks under the SINR model. The connectivity problem asks for a set of links that strongly connect a given set of wireless nodes, along with an efficient schedule. Aggregation asks for a spanning in-arborescence (converge-cast tree), along with a schedule that additionally obeys the partial order defined by the tree. Here we treat the multi-hop case, where nodes have limited power that restricts the links they can potentially form. We show that connectivity is possible for any set of n nodes in O(\log n) slots, which matches the best centralized bound known, and that aggregation is possible in O(D + log n) time (D being the maximum hop-distance), which is optimal.

We study a fundamental measure for wireless interference in the SINR model known as (weighted) inductive independence. This measure characterizes the effectiveness of using oblivious power — when the power used by a transmitter only depends on the distance to the receiver — as a mechanism for improving wireless capacity. We prove optimal bounds for inductive independence, implying a number of algorithmic applications. An algorithm is provided that achieves — due to existing lower bounds — capacity that is asymptotically best possible using oblivious power assignments. Improved approximation algorithms are provided for a number of problems for oblivious power and for power control, including distributed scheduling, connectivity, secondary spectrum auctions, and dynamic packet scheduling.

No abstract available.

In Gandhi et al. [2006], we gave an algorithm for the data migration and non-deterministic open shop scheduling problems in the minimum sum version, that was claimed to achieve a 5.06-approximation. Unfortunately, it was pointed to us by Maxim Sviridenko that the argument contained an unfounded assumption that has eluded all of its readers until now. We detail in this document how this error can be amended. A side effect is an improved approximation ratio of 4.96.

We give algorithms with constant-factor performance guarantees for several capacity and throughput problems in the SINR model. The algorithms are all based on a novel LP formulation for capacity problems. First, we give a new constant-factor approximation algorithm for selecting the maximum subset of links that can be scheduled simultaneously, under any non-decreasing and sublinear power assignment. For the case of uniform power, we extend this to the case of variable QoS requirements and link-dependent noise terms. Second, we approximate a problem related to cognitive radio: find a maximum set of links that can be simultaneously scheduled without affecting a given set of previously assigned links. Finally, we obtain constant-factor approximation of weighted capacity under linear power assignment.

No abstract available.

We consider the problem of constructing a communication infrastructure from scratch, for a collection of identical wireless nodes. Combinatorially, this means a) finding a set of links that form a strongly connected spanning graph on a set of n points in the plane, and b) scheduling it efficiently in the SINR model of interference. The nodes must converge on a solution in a distributed manner, having no means of communication beyond the sole wireless channel.

Given n wireless transceivers located in a plane, a fundamental problem in wireless communications is to construct a strongly connected digraph on them such that the constituent links can be scheduled in fewest possible time slots, assuming the SINR model of interference. In this paper, we provide an algorithm that connects an arbitrary point set in O(log n) slots, improving on the previous best bound of O(log2 n) due to Moscibroda. This is complemented with a super-constant lower bound on our approach to connectivity. An important feature is that the algorithms allow for bi-directional (half-duplex) communication. One implication of this result is an improved bound of Ω(1/ log n) on the worst-case capacity of wireless networks, matching the best bound known for the extensively studied average-case. We explore the utility of oblivious power assignments, and show that essentially all such assignments result in a worst case bound of Ω(n) slots for connectivity. This rules out a recent claim of a O(log n) bound using oblivious power. On the other hand, using our result we show that O(min(log Δ, log n · (log n + log log Δ))) slots suffice, where Δ is the ratio between the largest and the smallest links in a minimum spanning tree of the points. Our results extend to the related problem of minimum latency aggregation scheduling, where we show that aggregation scheduling with O(log n) latency is possible, improving upon the previous best known latency of O(log3 n). We also initiate the study of network design problems in the SINR model beyond strong connectivity, obtaining similar bounds for biconnected and k-edge connected structures.

In online set packing (OSP), elements arrive online, announcing which sets they belong to, and the algorithm needs to assign each element, upon arrival, to one of its sets. The goal is to maximize the number of sets that are assigned all their elements: a set that misses even a single element is deemed worthless. This is a natural online optimization problem that abstracts allocation of scarce compound resources, e.g., multipacket data frames in communication networks. We present a randomized competitive online algorithm for the weighted case with general capacity (namely, where sets may have different values, and elements arrive with different multiplicities). We prove a matching lower bound on the competitive ratio for any randomized online algorithm. Our bounds are expressed in terms of the maximum set size and the maximum number of sets an element belongs to. We also present refined bounds that depend on the uniformity of these parameters.

We consider the scheduling of arbitrary wireless links in the physical model of interference to minimize the time for satisfying all requests. We study here the combined problem of scheduling and power control, where we seek both an assignment of power settings and a partition of the links so that each set satisfies the signal-to-interference-plus-noise (SINR) constraints. We give an algorithm that attains an approximation ratio of O (log n ċ log log Δ), where n is the number of links and Δ is the ratio between the longest and the shortest link length. Under the natural assumption that lengths are represented in binary, this gives the first approximation ratio that is polylogarithmic in the size of the input. The algorithm has the desirable property of using an oblivious power assignment, where the power assigned to a sender depends only on the length of the link. We give evidence that this dependence on Δ is unavoidable, showing that any reasonably behaving oblivious power assignment results in a Ω(log log Δ)-approximation. These results hold also for the (weighted) capacity problem of finding a maximum (weighted) subset of links that can be scheduled in a single time slot. In addition, we obtain improved approximation for a bidirectional variant of the scheduling problem, give partial answers to questions about the utility of graphs for modeling physical interference, and generalize the setting from the standard 2-dimensional Euclidean plane to doubling metrics. Finally, we explore the utility of graph models in capturing wireless interference.

The capacity of a wireless network is the maximum possible amount of simultaneous communication, taking interference into account. Formally, we treat the following problem. Given is a set of links, each a sender-receiver pair located in a metric space, and an assignment of power to the senders. We seek a maximum subset of links that are feasible in the SINR model: namely, the signal received on each link should be larger than the sum of the interferences from the other links. We give a constant-factor approximation that holds for any length-monotone, sub-linear power assignment and any distance metric. We use this to give essentially tight characterizations of capacity maximization under power control using oblivious power assignments. Specifically, we show that the mean power assignment is optimal for capacity maximization of bi-directional links, and give a tight θ(log n)-approximation of scheduling bi-directional links with power control using oblivious power. For uni-directional links we give a nearly optimal O(log n + log log Δ)-approximation to the power control problem using mean power, where Δ is the ratio of longest and shortest links. Combined, these results clarify significantly the centralized complexity of wireless communication problems.

In the problem of Scheduling with Interval Conflicts, there is a ground set of items indexed by integers, and the input is a collection of conflicts, each containing all the items whose index lies within some interval on the real line. Conflicts arrive in an online fashion. A scheduling algorithm must select, from each conflict, at most one survivor item, and the goal is to maximize the number (or weight) of items that survive all the conflicts they are involved in. We present a centralized deterministic online algorithm whose competitive ratio is O(log sigma), where sigma is the size of the largest conflict. For the distributed setting, we present another deterministic algorithm whose competitive ratio is 2 log sigma, in the special contiguous case, in which the item indices constitute a contiguous interval of integers. Our upper bounds are complemented by two lower bounds: one that shows that even in the contiguous case, all deterministic algorithms (centralized or distributed) have competitive ratio Omega(log sigma), and that in the non-contiguous case, no deterministic oblivious algorithm (i.e., a distributed algorithm that does not use communication) can have a bounded competitive ratio.

We consider the scheduling of biprocessor jobs under sum objective (BPSMSM). Given a collection of unit-length jobs where each job requires the use of two processors, find a schedule such that no two jobs involving the same processor run concurrently. The objective is to minimize the sum of the completion times of the jobs. Equivalently, we would like to find a sum edge coloring of a given multigraph, that is, a partition of its edge set into matchings M 1 ,…, M t minimizing Σ i =1 t i | M i |. This problem is APX-hard, even in the case of bipartite graphs [Marx 2009]. This special case is closely related to the classic open shop scheduling problem. We give a 1.8298-approximation algorithm for BPSMSM improving the previously best ratio known of 2 [Bar-Noy et al. 1998]. The algorithm combines a configuration LP with greedy methods, using nonstandard randomized rounding on the LP fractions. We also give an efficient combinatorial 1.8886-approximation algorithm for the case of simple graphs, which gives an improved 1.79568 + O (log d¯/d¯)-approximation in graphs of large average degree d¯.

We consider a scenario where large data frames are broken into a few packets and transmitted over the network. Our focus is on a bottleneck router: the model assumes that in each time step, a set of packets (a burst) arrives, from which only one packet can be served, and all other packets are lost. A data frame is considered useful only if none of its constituent packets is lost, and otherwise it is worthless. We abstract the problem as a new type of online set packing, present a randomized distributed algorithm and a matching lower bound on the competitive ratio for any randomized online algorithm. Our bounds are expressed in terms of the maximal burst size and the maximal number of packets per frame. We also present refined bounds that depend on the uniformity of these parameters.

In this work we study the problem of determining the throughput capacity of a wireless network. We propose a scheduling algorithm to achieve this capacity within an approximation factor. Our analysis is performed in the physical interference model, where nodes are arbitrarily distributed in Euclidean space. We consider the problem separately from the routing problem and the power control problem, i.e., all requests are single-hop, and all nodes transmit at a fixed power level. The existing solutions to this problem have either concentrated on special-case topologies, or presented optimality guarantees which become arbitrarily bad (linear in the number of nodes) depending on the network's topology. We propose the first scheduling algorithm with approximation guarantee independent of the topology of the network. The algorithm has a constant approximation guarantee for the problem of maximizing the number of links scheduled in one time-slot. Furthermore, we obtain a O(log n) approximation for the problem of minimizing the number of time slots needed to schedule a given set of requests. Simulation results indicate that our algorithm does not only have an exponentially better approximation ratio in theory, but also achieves superior performance in various practical network scenarios. Furthermore, we prove that the analysis of the algorithm is extendable to higher-dimensional Euclidean spaces, and to more realistic bounded-distortion spaces, induced by non-isotropic signal distortions. Finally, we show that it is NP-hard to approximate the scheduling problem to within n1-epsivfactor, for any constant epsiv > 0, in the non-geometric SINR model, in which path-loss is independent of the Euclidean coordinates of the nodes.

We consider a general class of scheduling problems where a set of conflicting jobs needs to be scheduled (preemptively or nonpreemptively) on a set of machines so as to minimize the weighted sum of completion times. The conflicts among jobs are formed as an arbitrary conflict graph. Building on the framework of Queyranne and Sviridenko [2002b], we present a general technique for reducing the weighted sum of completion-times problem to the classical makespan minimization problem. Using this technique, we improve the best-known results for scheduling conflicting jobs with the min-sum objective, on several fundamental classes of graphs, including line graphs, ( k + 1)-claw-free graphs, and perfect graphs. In particular, we obtain the first constant-factor approximation ratio for nonpreemptive scheduling on interval graphs. We also improve the results of Kim [2003] for scheduling jobs on line graphs and for resource-constrained scheduling.

The stable marriage problem has recently been studied in its general setting, where both ties and incomplete lists are allowed. It is NP-hard to find a stable matching of maximum size, while any stable matching is a maximal matching and thus trivially we can obtain a 2-approximation algorithm. In this article, we give the first nontrivial result for approximation of factor less than two. Our algorithm achieves an approximation ratio of 2/(1 + L −2 ) for instances in which only men have ties of length at most L . When both men and women are allowed to have ties but the lengths are limited to two, then we show a ratio of 13/7(<1.858). We also improve the lower bound on the approximation ratio to 21/19(>1.1052).

We consider the problem of scheduling jobs that are given as groups of nonintersecting segments on the real line. Each job $J_j$ is associated with an interval, $I_j$, which consists of up to t segments, for some $t \geq 1$, and a weight (profit), $w_j$; two jobs are in conflict if their intervals intersect. Such jobs show up in a wide range of applications, including the transmission of continuous-media data, allocation of linear resources (e.g., bandwidth in linear processor arrays), and computational biology/geometry. The objective is to schedule a subset of nonconflicting jobs of maximum total weight. Our problem can be formulated as the problem of finding a maximum weight independent set in a t-interval graph (the special case of $t=1$ is an ordinary interval graph). We show that, for $t \geq 2$, this problem is APX-hard, even for highly restricted instances. Our main result is a $2t$-approximation algorithm for general instances. This is based on a novel fractional version of the Local Ratio technique. One implication of this result is the first constant factor approximation for nonoverlapping alignment of genomic sequences. We also derive a bicriteria polynomial time approximation scheme for a restricted subclass of t-interval graphs.

The data migration problem is to compute an efficient plan for moving data stored on devices in a network from one configuration to another. We consider this problem with the objective of minimizing the sum of completion times of all storage devices. It is modeled by a transfer graph, where vertices represent the storage devices, and the edges indicate the data transfers required between pairs of devices. Each vertex has a nonnegative weight, and each edge has a release time and a processing time. A vertex completes when all the edges incident on it complete; the constraint is that two edges incident on the same vertex cannot be processed simultaneously. The objective is to minimize the sum of weighted completion times of all vertices. Kim ( Journal of Algorithms, 55:42--57, 2005 ) gave a 9-approximation algorithm for the problem when edges have arbitrary processing times and are released at time zero. We improve Kim's result by giving a 5.06-approximation algorithm. We also address the open shop scheduling problem, O | r j | ∑ w j C j , and show that it is a special case of the data migration problem. Queyranne and Sviridenko ( Journal of Scheduling, 5:287-305, 2002 ) gave a 5.83-approximation algorithm for the nonpreemptive version of the open shop problem. They state as an obvious open question whether there exists an algorithm for open shop scheduling that gives a performance guarantee better than 5.83. Our 5.06 algorithm for data migration proves the existence of such an algorithm. Crucial to our improved result is a property of the linear programming relaxation for the problem. Similar linear programs have been used for various other scheduling problems. Our technique may be useful in obtaining improved results for these problems as well.

Each access point (AP) in a WiFi network must be assigned a channel for it to service users. There are only finitely many possible channels that can be assigned. Moreover, neighboring access points must use different channels so as to avoid interference. Currently these channels are assigned by administrators who carefully consider channel conflicts and network loads. Channel conflicts among APs operated by different entities are currently resolved in an ad hoc manner or not resolved at all. We view the channel assignment problem as a game, where the players are the service providers and APs are acquired sequentially. We consider the price of anarchy of this game, which is the ratio between the total coverage of the APs in the worst Nash equilibrium of the game and what the total coverage of the APs would be if the channel assignment were done by a central authority. We provide bounds on the price of anarchy depending on assumptions on the underlying network and the type of bargaining allowed between service providers. The key tool in the analysis is the identification of the Nash equilibria with the solutions to a maximal coloring problem in an appropriate graph. We relate the price of anarchy of these games to the approximation factor of local optimization algorithms for the maximum k-colorable subgraph problem. We also study the speed of convergence in these games.

We give nontrivial boundsfor the inductiveness or degeneracy of power graphs G k of a planar graph G. This implies bounds for the chromatic number as well, since the inductiveness naturally relates to a greedy algorithm for vertex-coloring the given graph. The inductiveness moreover yields bounds for the choosability of the graph. We show that the inductiveness of a square of a planar graph G is at most $\lceil 9\Delta /5 \rceil$, for the maximum degree $\Delta$ sufficiently large, and that it is sharp. In general, we show for a fixed integer $k\geq1$ the inductiveness, the chromatic number, and the choosability of G k to be $O(\Delta^{\lfloor k/2 \rfloor})$, which is tight.

A set of vertices in a graph is a dominating set if every vertex outside the set has a neighbor in the set. The domatic number problem is that of partitioning the vertices of a graph into the maximum number of disjoint dominating sets. Let n denote the number of vertices, $\delta$ the minimum degree, and $\Delta$ the maximum degree. We show that every graph has a domatic partition with $(1 - o(1))(\delta + 1)/\ln n$ dominating sets and, moreover, that such a domatic partition can be found in polynomial-time. This implies a $(1 + o(1))\ln n$-approximation algorithm for domatic number, since the domatic number is always at most $\delta + 1$. We also show this to be essentially best possible. Namely, extending the approximation hardness of set cover by combining multiprover protocols with zero-knowledge techniques, we show that for every $\epsilon > 0$, a $(1 - \epsilon)\ln n$-approximation implies that $NP \subseteq DTIME(n^{O(\log\log n)})$. This makes domatic number the first natural maximization problem (known to the authors) that is provably approximable to within polylogarithmic factors but no better. We also show that every graph has a domatic partition with $(1 - o(1))(\delta + 1)/\ln \Delta$ dominating sets, where the "o(1)" term goes to zero as $\Delta$ increases. This can be turned into an efficient algorithm that produces a domatic partition of $\Omega(\delta/\ln \Delta)$ sets.

A set of vertices in a graph is a dominating set if every vertex outside the set has aneighbor in the set. The domatic number problem is that of partitioning the vertices of a graph into the maximum number of disjoint dominating sets. Let n denote the number ofvertices, ffi the minimum degree, and \\Delta the maximum degree.We show that every graph has a domatic partition with (1-o(1))(ffi + 1) / ln n dominatingsets, and moreover, that such a domatic partition can be found in polynomial time. This implies a (1 + o(1)) ln n approximation algorithm for domatic number, since the domaticnumber is always at most ffi + 1. We also show this to be essentially best possible. Namely,extending the approximation hardness of set cover by combining multi-prover protocols with zero-knowledge techniques, we show that for every ffl> 0, a (1- ffl) ln n-approximation impliesthat N P ` DT IM E(nO(log log n)). This makes domatic number the first natural maximiza-tion problem (known to the authors) that is provably approximable to within polylogarithmic factors but no better.We also show that every graph has a domatic partition with (1-o(1))(ffi + 1) / ln \\Delta dominating sets, where the " o(1) " term goes to zero as \\Delta increases. This can be turned intoan efficient algorithm that produces a domatic partition of \\Omega ( ffi / ln \\Delta) sets.

We consider the problem of finding a set of k vertices in a graph that are in some sense remote. Stated more formally, given a graph G and an integer k, find a set P of k vertices for which the total weight of a minimum structure on P is maximized. In particular, we are interested in three problems of this type, where the structure to be minimized is a spanning tree ({\sc Remote-MST}), Steiner tree, or traveling salesperson tour. We study a natural greedy algorithm that simultaneously approximates all three problems on metric graphs. For instance, its performance ratio for {\sc Remote-MST} is exactly 4, while this problem is NP-hard to approximate within a factor of less than 2. We also give a better approximation for graphs induced by Euclidean points in the plane, present an exact algorithm for graphs whose distances correspond to shortest-path distances in a tree, and prove hardness and approximability results for general graphs.

We analyze the approximation ratio of the average distance heuristic for the Steiner tree problem on graphs and prove nearly tight bounds for the cases of complete graphs with binary weights {1, d} or weights in the interval [1, d], where d ≤ 2. The improvement over other analyzed algorithms is a factor of about e ≈ 2.718. © 1998 John Wiley & Sons, Inc. Networks 31: 283–292, 1998

Theminimum-degree greedy algorithm, or Greedy for short, is a simple and well-studied method for finding independent sets in graphs. We show that it achieves a performance ratio of (Δ+2)/3 for approximating independent sets in graphs with degree bounded by Δ. The analysis yields a precise characterization of the size of the independent sets found by the algorithm as a function of the independence number, as well as a generalization of Turan’s bound. We also analyze the algorithm when run in combination with a known preprocessing technique, and obtain an improved\((2\bar d + 3)/5\) performance ratio on graphs with average degree\(\bar d\), improving on the previous best\((\bar d + 1)/2\) of Hochbaum. Finally, we present an efficient parallel and distributed algorithm attaining the performance guarantees of Greedy.

An algorithm for vertex-coloring graphs is said to be on-line if each vertex is irrevocably assigned a color before later vertices are considered. We show that for every such algorithm there exists a log n-colorable graph for which the algorithm uses at least 2n/log n colors. This also holds for randomized algorithms, to within a constant factor, against an oblivious adversary. We then show that various means of relaxing the constraints of the on-line model do not reduce these lower bounds. The features include presenting the input in blocks of up to log2 n vertices, recoloring any fraction of the vertices, presorting vertices by degree, and disclosing the adversary's previous coloring.

We consider the problem of computing threshold functions using directed and undirected monotone contact networks. Our main results are the following. First, we show that there exist directed monotone contact networks that compute T/sub k//sup n/, 2/spl les/k/spl les/n-1, of size O(k(n-k+2)log(n-k+2)). This bound is almost optimal for small thresholds, since there exists an /spl Omega/(knlog (n/(k-1))) lower bound. Our networks are described explicitly; the previously best upper bound known, obtained from the undirected networks of Dubiner and Zwick, used non-constructive arguments and gave directed networks of size O(k/sup 3.99/nlog n). Second, we show a lower bound of O(nlogloglog n) on the size of undirected monotone contact networks computing T/sub n-1//sup n/, improving the 2(n-1) lower bound of Markov. Combined with our upper bound result, this shows that directed monotone contact networks compute some threshold functions more easily than undirected networks.>