Greedy approximation for the source location problem with vertex-connectivity requirements in undirected graphs

Let $G=(V,E)$ be a simple undirected graph with a set V of vertices and a set E of edges. Each vertex $v\in V$ has a demand $d(v)\in Z_{+}$, and a cost $c(v)\in R_{+}$, where $Z_{+}$ and $R_{+}$ denote the set of nonnegative integers and the set of nonnegative reals, respectively. The source location problem with vertex-connectivity requirements in a given graph G asks to find a set S of vertices minimizing ${\sum }_{v\in S}c(v)$ such that there are at least $d(v)$ pairwise vertex-disjoint paths from S to v for each vertex $v\in V?S$. It is known that the problem is not approximable within a ratio of $O(\ln {\sum }_{v\in V}d(v))$, unless NP has an $O(N^{\log \log N})$-time deterministic algorithm. Also, it is known that even if every vertex has a uniform cost and $d^1=4$ holds, then the problem is NP-hard, where $d^1=\max \{d(v)|v\in V\}$.In this paper, we consider the problem in the case where every vertex has uniform cost. We propose a simple greedy algorithm for providing a $\max \{d^1,2d^1?6\}$-approximate solution to the problem in $O(\min \{d^1,\sqrt{|V|}\}{d}^1{|V|}^2)$ time, while we also show that there exists an instance for which it provides no better than a $(d^1?1)$-approximate solution. Especially, in the case of $d^1?4$, we give a tight analysis to show that it achieves an approximation ratio of 3. We also show the APX-hardness of the problem even restricted to $d^1?4$.     

The nonidealness index of circulant matrices

Ideal matrices are precisely those matrices M where the set covering polyhedron $Q^1(M)$ equals the polyhedron $Q(M)=\{x:Mx\ge 1,x\ge 0\}$. In a previous work (2006) we defined a nonidealness index equivalent to $\max \{t:Q(M)\subset t{Q}^1(M)\}$. Given an arbitrary matrix M the nonideal index is NP-hard to compute and for most matrices it remains unknown.A well known family of minimally nonideal matrices is the one of the incidence matrices of chordless odd cycles. A natural generalization of them is given by circulant matrices. Circulant ideal matrices have been completely identified by Cornuéjols and Novick (1994). In this work we obtain a bound for the nonidealness index of circulant matrices and determine it for some particular cases.     

Contracting an element from a cocircuit

We consider the situation that M and N are 3-connected matroids such that $|E(N)|⩾4$ and $C^1$ is a cocircuit of M with the property that $M/x_0$ has an N-minor for some $x_0\in C^1$. We show that either there is an element $x\in C^1$ such that $\mathrm{si}(M/x)$ or $\mathrm{co}(\mathrm{si}(M/x))$ is 3-connected with an N-minor, or there is a four-element fan of M that contains two elements of $C^1$ and an element x such that $\mathrm{si}(M/x)$ is 3-connected with an N-minor.