Source author record

Nachshon Cohen

Explore this author’s publications, collaborators and research topics. This catalog record has not been claimed by its author.

ResearcherUnclaimed source record

Data Structures and Algorithms

Catalog footprint

Research overview

2works

1topics

1close collaborators

Actions

Is this your work?

Open graph Browse papers

preprint2013arXiv

Approximating {0,1,2}-Survivable Networks with Minimum Number of Steiner Points

We consider low connectivity variants of the Survivable Network with Minimum Number of Steiner Points (SN-MSP) problem: given a finite set $R$ of terminals in a metric space (M,d), a subset $B \subseteq R$ of "unstable" terminals, and connectivity requirements {r_{uv}: u,v \in R}, find a minimum size set $S \subseteq M$ of additional points such that the unit-disc graph of $R \cup S$ contains $r_{uv}$ pairwise internally edge-disjoint and $(B \cup S)$ -disjoint $uv$ -paths for all $u,v \in R$ . The case when $r_{uv}=1$ for all $u,v \in R$ is the {\sf Steiner Tree with Minimum Number of Steiner Points} (ST-MSP) problem, and the case $r_{uv} \in \{0,1\}$ is the {\sf Steiner Forest with Minimum Number of Steiner Points} (SF-MSP) problem. Let $Δ$ be the maximum number of points in a unit ball such that the distance between any two of them is larger than 1. It is known that $Δ=5$ in $\mathbb{R}^2$ The previous known approximation ratio for {\sf ST-MSP} was $\lfloor (Δ+1)/2 \rfloor+1+ε$ in an arbitrary normed space \cite{NY}, and $2.5+ε$ in the Euclidean space $\mathbb{R}^2$ \cite{cheng2008relay}. Our approximation ratio for ST-MSP is $1+\ln(Δ-1)+ε$ in an arbitrary normed space, which in $\mathbb{R}^2$ reduces to $1+\ln 4+ε< 2.3863 +ε$ . For SN-MSP with $r_{uv} \in \{0,1,2\}$ , we give a simple $Δ$ -approximation algorithm. In particular, for SF-MSP, this improves the previous ratio $2Δ$ .

preprint2011arXiv

Approximating minimum-power edge-multicovers

Given a graph with edge costs, the {\em power} of a node is themaximum cost of an edge incident to it, and the power of a graph is the sum of the powers of its nodes. Motivated by applications in wireless networks, we consider the following fundamental problem in wireless network design. Given a graph $G=(V,E)$ with edge costs and degree bounds $\{r(v):v \in V\}$ , the {\sf Minimum-Power Edge-Multi-Cover} ({\sf MPEMC}) problem is to find a minimum-power subgraph $J$ of $G$ such that the degree of every node $v$ in $J$ is at least $r(v)$ . We give two approximation algorithms for {\sf MPEMC}, with ratios $O(\log k)$ and $k+1/2$ , where $k=\max_{v \in V} r(v)$ is the maximum degree bound. This improves the previous ratios $O(\log n)$ and $k+1$ , and implies ratios $O(\log k)$ for the {\sf Minimum-Power $k$ -Outconnected Subgraph} and $O(\log k \log \frac{n}{n-k})$ for the {\sf Minimum-Power $k$ -Connected Subgraph} problems; the latter is the currently best known ratio for the min-cost version of the problem.

Inspect adjacent papers, topics, institutions and collaborators without losing the researcher page.

Building this map preview

BZPEER is loading the nearby papers, people, topics and institutions for this page.