ﻻ يوجد ملخص باللغة العربية
This study considers the (soft) capacitated vertex cover problem in a dynamic setting. This problem generalizes the dynamic model of the vertex cover problem, which has been intensively studied in recent years. Given a dynamically changing vertex-weighted graph $G=(V,E)$, which allows edge insertions and edge deletions, the goal is to design a data structure that maintains an approximate minimum vertex cover while satisfying the capacity constraint of each vertex. That is, when picking a copy of a vertex $v$ in the cover, the number of $v$s incident edges covered by the copy is up to a given capacity of $v$. We extend Bhattacharya et al.s work [SODA15 and ICALP15] to obtain a deterministic primal-dual algorithm for maintaining a constant-factor approximate minimum capacitated vertex cover with $O(log n / epsilon)$ amortized update time, where $n$ is the number of vertices in the graph. The algorithm can be extended to (1) a more general model in which each edge is associated with a nonuniform and unsplittable demand, and (2) the more general capacitated set cover problem.
We study the Capacitated k-Median problem, for which all the known constant factor approximation algorithms violate either the number of facilities or the capacities. While the standard LP-relaxation can only be used for algorithms violating one of t
In the Survivable Network Design problem (SNDP), we are given an undirected graph $G(V,E)$ with costs on edges, along with a connectivity requirement $r(u,v)$ for each pair $u,v$ of vertices. The goal is to find a minimum-cost subset $E^*$ of edges,
We introduce and study two natural generalizations of the Connected VertexCover (VC) problem: the $p$-Edge-Connected and $p$-Vertex-Connected VC problem (where $p geq 2$ is a fixed integer). Like Connected VC, both new VC problems are FPT, but do not
We present a massively parallel algorithm, with near-linear memory per machine, that computes a $(2+varepsilon)$-approximation of minimum-weight vertex cover in $O(loglog d)$ rounds, where $d$ is the average degree of the input graph. Our result fi
We present a local algorithm (constant-time distributed algorithm) for finding a 3-approximate vertex cover in bounded-degree graphs. The algorithm is deterministic, and no auxiliary information besides port numbering is required.