Abstract. We study Dominating Set and Independent Set for dynamic graphs in the vertex-arrival model. We say that a dynamic algorithm for one of these problems is [Formula: see text]- stable when it makes at most [Formula: see text] changes to its output independent set or dominating set upon the arrival of each vertex. We study trade-offs between the stability parameter [Formula: see text] of the algorithm and the approximation ratio it achieves. We obtain the following results: (i) We show that there is a constant [Formula: see text] such that any dynamic [Formula: see text]-approximation algorithm for Dominating Set has stability parameter [Formula: see text], even for bipartite graphs of maximum degree 4. (ii) We present algorithms with very small stability parameters for Dominating Set in the setting where the arrival degree of each vertex is upper bounded by [Formula: see text]. In particular, we give a 1-stable [Formula: see text]-approximation algorithm, a 3-stable [Formula: see text]-approximation algorithm, and an [Formula: see text]-stable [Formula: see text]-approximation algorithm. (iii) We show that there is a constant [Formula: see text] such that any dynamic [Formula: see text]-approximation algorithm for Independent Set has stability parameter [Formula: see text], even for bipartite graphs of maximum degree 3. (iv) Finally, we present a 2-stable [Formula: see text]-approximation algorithm for Independent Set, in the setting where the average degree of the graph is upper bounded by some constant [Formula: see text] at all times. We extend this latter algorithm to the fully dynamic model where vertices can also be deleted, achieving a 6-stable [Formula: see text]-approximation algorithm.

Abstract. Let [Formula: see text] be a set of points in [Formula: see text], where each point [Formula: see text] has an associated transmission range, denoted [Formula: see text]. The range assignment [Formula: see text] induces a directed communication graph [Formula: see text] on [Formula: see text], which contains an edge [Formula: see text] iff [Formula: see text]. In the broadcast range-assignment problem, the goal is to assign the ranges such that [Formula: see text] contains an arborescence rooted at a designated root node and the cost [Formula: see text] of the assignment is minimized. We study the dynamic version of this problem. In particular, we study trade-offs between the stability of the solution—the number of ranges that are modified when a point is inserted into or deleted from [Formula: see text]—and its approximation ratio. To this end we study [Formula: see text]- stable algorithms, which are algorithms that modify the range of at most [Formula: see text] points when they update the solution. We also introduce the concept of a stable approximation scheme, or SAS for short. A SAS is an update algorithm [Formula: see text] that, for any given fixed parameter [Formula: see text], is [Formula: see text]-stable and that maintains a solution with approximation ratio [Formula: see text], where the stability parameter [Formula: see text] only depends on [Formula: see text] and not on the size of [Formula: see text]. We study such trade-offs in three settings. (1) For the problem in [Formula: see text], we present a SAS with [Formula: see text]. Furthermore, we prove that this is tight in the worst case: any SAS for the problem must have [Formula: see text]. We also present 1-, 2-, and 3-stable algorithms with constant approximation ratio. (2) For the problem in [Formula: see text] (that is, when the underlying space is a circle) we prove that no SAS exists. This is in spite of the fact that, for the static problem in [Formula: see text], we prove that an optimal solution can always be obtained by cutting the circle at an appropriate point and solving the resulting problem in [Formula: see text]. (3) For the problem in [Formula: see text], we also prove that no SAS exists, and we present a [Formula: see text]-stable [Formula: see text]-approximation algorithm. Most results generalize to the setting where, for any given constant [Formula: see text], the range-assignment cost is [Formula: see text].

Finding minimum dominating set and maximum independent set for graphs in the classical online setup are notorious due to their disastrous $Ω(n)$ lower bound of the competitive ratio that even holds for interval graphs, where $n$ is the number of vertices. In this paper, inspired by Newton number, first, we introduce the independent kissing number $ζ$ of a graph. We prove that the well known online greedy algorithm for dominating set achieves optimal competitive ratio $ζ$ for any graph. We show that the same greedy algorithm achieves optimal competitive ratio $ζ$ for online maximum independent set of a class of graphs with independent kissing number $ζ$. For minimum connected dominating set problem, we prove that online greedy algorithm achieves an asymptotic competitive ratio of $2(ζ-1)$, whereas for a family of translated convex objects the lower bound is $\frac{2ζ-1}{3}$. Finally, we study the value of $ζ$ for some specific families of geometric objects: fixed and arbitrary oriented unit hyper-cubes in $I\!\!R^d$, congruent balls in $I\!\!R^3$, fixed oriented unit triangles, fixed and arbitrary oriented regular polygons in $I\!\!R^2$. For each of these families, we also present lower bounds of the minimum connected dominating set problem.