DROPS

Document

APPROX

DOI: 10.4230/LIPIcs.APPROX/RANDOM.2023.27

Stable Approximation Algorithms for Dominating Set and Independent Set

Authors: Mark de Berg, Arpan Sadhukhan, and Frits Spieksma

Published in: LIPIcs, Volume 275, Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2023)

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 k-stable when it makes at most k changes to its output independent set or dominating set upon the arrival of each vertex. We study trade-offs between the stability parameter k of the algorithm and the approximation ratio it achieves. We obtain the following results. - We show that there is a constant ε^* > 0 such that any dynamic (1+ε^*)-approximation algorithm for Dominating Set has stability parameter Ω(n), even for bipartite graphs of maximum degree 4. - 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 d. In particular, we give a 1-stable (d+1)²-approximation, and a 3-stable (9d/2)-approximation algorithm. - We show that there is a constant ε^* > 0 such that any dynamic (1+ε^*)-approximation algorithm for Independent Set has stability parameter Ω(n), even for bipartite graphs of maximum degree 3. - Finally, we present a 2-stable O(d)-approximation algorithm for Independent Set, in the setting where the average degree of the graph is upper bounded by some constant d at all times.

Cite as

Mark de Berg, Arpan Sadhukhan, and Frits Spieksma. Stable Approximation Algorithms for Dominating Set and Independent Set. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 275, pp. 27:1-27:19, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)

Copy BibTex To Clipboard

@InProceedings{deberg_et_al:LIPIcs.APPROX/RANDOM.2023.27,
  author =	{de Berg, Mark and Sadhukhan, Arpan and Spieksma, Frits},
  title =	{{Stable Approximation Algorithms for Dominating Set and Independent Set}},
  booktitle =	{Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2023)},
  pages =	{27:1--27:19},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-296-9},
  ISSN =	{1868-8969},
  year =	{2023},
  volume =	{275},
  editor =	{Megow, Nicole and Smith, Adam},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.APPROX/RANDOM.2023.27},
  URN =		{urn:nbn:de:0030-drops-188527},
  doi =		{10.4230/LIPIcs.APPROX/RANDOM.2023.27},
  annote =	{Keywords: Dynamic algorithms, approximation algorithms, stability, dominating set, independent set}
}

Document

DOI: 10.4230/LIPIcs.SWAT.2022.15

Stable Approximation Algorithms for the Dynamic Broadcast Range-Assignment Problem

Authors: Mark de Berg, Arpan Sadhukhan, and Frits Spieksma

Published in: LIPIcs, Volume 227, 18th Scandinavian Symposium and Workshops on Algorithm Theory (SWAT 2022)

Abstract

Let P be a set of points in ℝ^d (or some other metric space), where each point p ∈ P has an associated transmission range, denoted ρ(p). The range assignment ρ induces a directed communication graph G_{ρ}(P) on P, which contains an edge (p,q) iff |pq| ⩽ ρ(p). In the broadcast range-assignment problem, the goal is to assign the ranges such that G_{ρ}(P) contains an arborescence rooted at a designated root node and the cost ∑_{p ∈ P} ρ(p)² 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 P - and its approximation ratio. To this end we introduce the concept of k-stable algorithms, which are algorithms that modify the range of at most k 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 alg that, for any given fixed parameter ε > 0, is k(ε)-stable and that maintains a solution with approximation ratio 1+ε, where the stability parameter k(ε) only depends on ε and not on the size of P. We study such trade-offs in three settings. - For the problem in ℝ¹, we present a SAS with k(ε) = O(1/ε). Furthermore, we prove that this is tight in the worst case: any SAS for the problem must have k(ε) = Ω(1/ε). We also present algorithms with very small stability parameters: a 1-stable (6+2√5)-approximation algorithm - this algorithm can only handle insertions - a (trivial) 2-stable 2-approximation algorithm, and a 3-stable 1.97-approximation algorithm. - For the problem in 𝕊¹ (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 𝕊¹, we prove that an optimal solution can always be obtained by cutting the circle at an appropriate point and solving the resulting problem in ℝ¹. - For the problem in ℝ², we also prove that no SAS exists, and we present a O(1)-stable O(1)-approximation algorithm. Most results generalize to when the range-assignment cost is ∑_{p ∈ P} ρ(p)^{α}, for some constant α > 1. All omitted theorems and proofs are available in the full version of the paper [Mark de Berg et al., 2021].

Cite as

Mark de Berg, Arpan Sadhukhan, and Frits Spieksma. Stable Approximation Algorithms for the Dynamic Broadcast Range-Assignment Problem. In 18th Scandinavian Symposium and Workshops on Algorithm Theory (SWAT 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 227, pp. 15:1-15:21, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)

Copy BibTex To Clipboard

@InProceedings{deberg_et_al:LIPIcs.SWAT.2022.15,
  author =	{de Berg, Mark and Sadhukhan, Arpan and Spieksma, Frits},
  title =	{{Stable Approximation Algorithms for the Dynamic Broadcast Range-Assignment Problem}},
  booktitle =	{18th Scandinavian Symposium and Workshops on Algorithm Theory (SWAT 2022)},
  pages =	{15:1--15:21},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-236-5},
  ISSN =	{1868-8969},
  year =	{2022},
  volume =	{227},
  editor =	{Czumaj, Artur and Xin, Qin},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SWAT.2022.15},
  URN =		{urn:nbn:de:0030-drops-161756},
  doi =		{10.4230/LIPIcs.SWAT.2022.15},
  annote =	{Keywords: Computational geometry, online algorithms, broadcast range assignment, stable approximation schemes}
}

Search Results

Documents authored by Sadhukhan, Arpan

Stable Approximation Algorithms for Dominating Set and Independent Set

Abstract

Cite as

Stable Approximation Algorithms for the Dynamic Broadcast Range-Assignment Problem

Abstract

Cite as

Thanks for your feedback!

Could not send message