Efficient approximation algorithms for computing <Emphasis Type="Italic">k</Emphasis> disjoint constrained shortest paths

Let \(G=(V,\, E)\) be a given directed graph in which every edge e is associated with two nonnegative costs: a weight w(e) and a length l(e). For a pair of specified distinct vertices \(s,\, t\in V\), the k-(edge) disjoint constrained shortest path (kCSP) problem is to compute k (edge) disjoint paths between s and t, such that the total length of the paths is minimized and the weight is bounded by a given weight budget \(W\in \mathbb {R}_{0}^{+}\). The problem is known to be \({\mathcal {NP}}\)-hard, even when \(k=1\) (Garey and Johnson in Computers and intractability, 1979). Approximation algorithms with bifactor ratio \(\left( 1\,+\,\frac{1}{r},\, r\left( 1\,+\,\frac{2(\log r\,+\,1)}{r}\right) (1\,+\,\epsilon )\right) \) and \((1\,+\,\frac{1}{r},\,1\,+\,r)\) have been developed for \(k=2\) in Orda and Sprintson (IEEE INFOCOM, pp. 727–738, 2004) and Chao and Hong (IEICE Trans Inf Syst 90(2):465–472, 2007), respectively. For general k, an approximation algorithm with ratio \((1,\, O(\ln n))\) has been developed for a weaker version of kCSP, the k bi-constraint path problem which is to compute k disjoint st-paths satisfying a given length constraint and a weight constraint simultaneously (Guo et al. in COCOON, pp. 325–336, 2013). This paper first gives an approximation algorithm with bifactor ratio \((2,\,2)\) for kCSP using the LP-rounding technique. The algorithm is then improved by adopting a more sophisticated method to round edges. It is shown that for any solution output by the improved algorithm, there exists a real number \(0\le \alpha \le 2\) such that the weight and the length of the solution are bounded by \(\alpha \) times and \(2-\alpha \) times of that of an optimum solution, respectively. The key observation of the ratio proof is to show that the fractional edges, in a basic solution against the proposed linear relaxation of kCSP, exactly compose a graph in which the degree of every vertex is exactly two. At last, by a novel enhancement of the technique in Guo et al. (COCOON, pp. 325–336, 2013), the approximation ratio is further improved to \((1,\,\ln n)\).     

Approximation guarantees for parallelized maximization of monotone non-submodular function with a cardinality constraint

Journal of Combinatorial Optimization - Emerging applications in machine learning have imposed the problem of monotone non-submodular maximization subject to a cardinality constraint. Meanwhile,...