Zobrazeno 1 - 10
of 274
pro vyhledávání: '"NUTOV, ZEEV"'
Autor:
Nutov, Zeev
A classic result of Williamson, Goemans, Mihail, and Vazirani [STOC 1993: 708-717] states that the problem of covering an uncrossable set family by a min-cost edge set admits approximation ratio $2$, by a primal-dual algorithm with a reverse delete p
Externí odkaz:
http://arxiv.org/abs/2404.00683
Autor:
Nutov, Zeev
In the Activation Edge-Multicover problem we are given a multigraph $G=(V,E)$ with activation costs $\{c_{e}^u,c_{e}^v\}$ for every edge $e=uv \in E$, and degree requirements $r=\{r_v:v \in V\}$. The goal is to find an edge subset $J \subseteq E$ of
Externí odkaz:
http://arxiv.org/abs/2308.02901
Autor:
Nutov, Zeev, Kahba, Dawod
In the $Activation$ $k$ $Disjoint$ $st$-$Paths$ ($Activation$ $k$-$DP$) problem we are given a graph $G=(V,E)$ with activation costs $\{c_{uv}^u,c_{uv}^v\}$ for every edge $uv \in E$, a source-sink pair $s,t \in V$, and an integer $k$. The goal is to
Externí odkaz:
http://arxiv.org/abs/2307.12646
Autor:
Nutov, Zeev
A set family ${\cal F}$ is $uncrossable$ if $A \cap B,A \cup B \in {\cal F}$ or $A \setminus B,B \setminus A \in {\cal F}$ for any $A,B \in {\cal F}$. A classic result of Williamson, Goemans, Mihail, and Vazirani [STOC 1993:708-717] states that the p
Externí odkaz:
http://arxiv.org/abs/2307.08270
Autor:
Nutov, Zeev
We consider the following two variants of the Capacitated $k$-Edge Connected Subgraph} (Cap-k-ECS) problem. Near Min-Cuts Cover: Given a graph $G=(V,E)$ with edge costs and $E_0 \subseteq E$, find a min-cost edge set $J \subseteq E \setminus E_0$ tha
Externí odkaz:
http://arxiv.org/abs/2307.01650
One of the most important and well-studied settings for network design is edge-connectivity requirements. This encompasses uniform demands such as the Minimum $k$-Edge-Connected Spanning Subgraph problem as well as nonuniform demands such as the Surv
Externí odkaz:
http://arxiv.org/abs/2304.06656
Autor:
Nutov, Zeev
A graph $G$ is $k$-out-connected from its node $s$ if it contains $k$ internally disjoint $sv$-paths to every node $v$; $G$ is $k$-connected if it is $k$-out-connected from every node. In connectivity augmentation problems the goal is to augment a gr
Externí odkaz:
http://arxiv.org/abs/2209.06695
Autor:
Nutov, Zeev
In minimum power network design problems we are given an undirected graph $G=(V,E)$ with edge costs $\{c_e:e \in E\}$. The goal is to find an edge set $F\subseteq E$ that satisfies a prescribed property of minimum power $p_c(F)=\sum_{v \in V} \max \{
Externí odkaz:
http://arxiv.org/abs/2208.09373
Autor:
Nutov, Zeev
In activation network design problems we are given an undirected graph $G=(V,E)$ and a pair of activation costs $\{c_e^u,c_e^v\}$ for each $e=uv \in E$. The goal is to find an edge set $F \subseteq E$ that satisfies a prescribed property of minimum a
Externí odkaz:
http://arxiv.org/abs/2111.04011
Autor:
Nutov, Zeev
Let $\kappa(s,t)$ denote the maximum number of internally disjoint $st$-paths in an undirected graph $G$. We consider designing a compact data structure that answers $k$-bounded node connectivity queries: given $s,t \in V$ return $\min\{\kappa(s,t),k
Externí odkaz:
http://arxiv.org/abs/2110.09102