Improved approximation algorithms for computing $$k$$ k disjoint paths subject to two constraints

For a given graph $$G$$ G with distinct vertices $$s$$ s and $$t$$ t , nonnegative integral cost and delay on edges, and positive integral bound $$C$$ C and $$D$$ D on cost and delay respectively, the $$k$$ k bi-constraint path ( $$k$$ k BCP) problem is to compute $$k$$ k disjoint $$st$$ s t -paths subject to $$C$$ C and $$D$$ D . This problem is known to be NP-hard, even when $$k=1$$ k = 1 (Garey and Johnson, Computers and Intractability, 1979). This paper first gives a simple approximation algorithm with factor- $$(2,2)$$ ( 2 , 2 ) , i.e. the algorithm computes a solution with delay and cost bounded by $$2*D$$ 2 ∗ D and $$2*C$$ 2 ∗ C respectively. Later, a novel improved approximation algorithm with ratio $$(1+\beta ,\,\max \{2,\,1+\ln (1/\beta )\})$$ ( 1 + β , max { 2 , 1 + ln ( 1 / β ) } ) is developed by constructing interesting auxiliary graphs and employing the cycle cancellation method. As a consequence, we can obtain a factor- $$(1.369,\,2)$$ ( 1.369 , 2 ) approximation algorithm immediately and a factor- $$(1.567,\,1.567)$$ ( 1.567 , 1.567 ) algorithm by slightly modifying the algorithm. Besides, when $$\beta =0$$ β = 0 , the algorithm is shown to be with ratio $$(1,\, O(\ln n))$$ ( 1 , O ( ln n ) ) , i.e. it is an algorithm with only a single factor ratio $$O(\ln n)$$ O ( ln n ) on cost. To the best of our knowledge, this is the first non-trivial approximation algorithm that strictly obeys the delay constraint for the $$k$$ k BCP problem.