论文标题
灵活图连接性的近似算法
Approximation Algorithms for Flexible Graph Connectivity
论文作者
论文摘要
我们提出了灵活图形连接模型中几种网络设计问题的近似算法（AdjiaShvili，Hommelsheim和Mühlenthaler，“灵活的图形连接”，Math。Program。Pp。1-33（2021）和IPCO 2020：2020：pp。13-26）。 令$ k \ geq 1 $，$ p \ geq 1 $和$ q \ geq 0 $为整数。在$（p，q）$ - 灵活的图形连接问题的情况下，表示$（p，q）$ - fgc，我们有一个无方向的连接图$ g =（v，e）$，将$ e $的分区分为一组安全边缘$ s $ s $ s $ s $ s $和一组不安全的边缘$ $ $ u $ u $ u $ c：e $ c： $（p，q）$ - fgc问题的子集$ f \ subseteq e $如果对于任何子集$ f'$ f'$ f'$ f'| f'| f'| \ leq q $，subgraph $（v，f \ setminus f'| f \ setminus f'）$ p $ - p $ - edge incection。算法目标是找到一个可行的解决方案$ f $，该解决方案$ f $最小化$ c（f）= \ sum_ {e \ in f} c_e $。我们为$（1,1）$ - FGC问题提出了一种简单的$ 2 $ - APPRXIMATION ALGORITHM，通过减少至最低成本的$ 2 $ 2 $ - ARBORESCENCE问题。这改善了Adjshvili等人的$ 2.527 $ -Approximation算法。我们的$ 2 $ - Approximation算法（1,1）$ - FGC问题扩展到$（K+1）$ - 近似算法的$（1，K）$ - FGC问题。我们提出了$ 4 $ - APPRXIMATION算法（p，p，1）$ - FGC问题，以及$ O（q \ log | v |）$ - $（p，q）$ - FGC问题的近似算法。最后，我们在Axchshvili等人的结果上有所改善。对于未加权的$（1,1）$ - FGC问题，提出了$ 16/11 $ - APPRXIMATION算法。 $（p，q）$ - FGC问题与众所周知的电容$ k $连接的子图问题（表示为CAP-K-ECSS）有关，该问题在电容的网络设计区域出现。我们给出了$ \ min（k，2 u_ {max}）$ - cap-k-ecss问题的近似算法，其中$ u_ {max} $表示边缘的最大容量。
We present approximation algorithms for several network design problems in the model of Flexible Graph Connectivity (Adjiashvili, Hommelsheim and Mühlenthaler, "Flexible Graph Connectivity", Math. Program. pp. 1-33 (2021), and IPCO 2020: pp. 13-26). Let $k\geq 1$, $p\geq 1$ and $q\geq 0$ be integers. In an instance of the $(p,q)$-Flexible Graph Connectivity problem, denoted $(p,q)$-FGC, we have an undirected connected graph $G = (V,E)$, a partition of $E$ into a set of safe edges $S$ and a set of unsafe edges $U$, and nonnegative costs $c: E\to\Re$ on the edges. A subset $F \subseteq E$ of edges is feasible for the $(p,q)$-FGC problem if for any subset $F'$ of unsafe edges with $|F'|\leq q$, the subgraph $(V, F \setminus F')$ is $p$-edge connected. The algorithmic goal is to find a feasible solution $F$ that minimizes $c(F) = \sum_{e \in F} c_e$. We present a simple $2$-approximation algorithm for the $(1,1)$-FGC problem via a reduction to the minimum-cost rooted $2$-arborescence problem. This improves on the $2.527$-approximation algorithm of Adjiashvili et al. Our $2$-approximation algorithm for the $(1,1)$-FGC problem extends to a $(k+1)$-approximation algorithm for the $(1,k)$-FGC problem. We present a $4$-approximation algorithm for the $(p,1)$-FGC problem, and an $O(q\log|V|)$-approximation algorithm for the $(p,q)$-FGC problem. Finally, we improve on the result of Adjiashvili et al. for the unweighted $(1,1)$-FGC problem by presenting a $16/11$-approximation algorithm. The $(p,q)$-FGC problem is related to the well-known Capacitated $k$-Connected Subgraph problem (denoted Cap-k-ECSS) that arises in the area of Capacitated Network Design. We give a $\min(k,2 u_{max})$-approximation algorithm for the Cap-k-ECSS problem, where $u_{max}$ denotes the maximum capacity of an edge.
