Improved approximations for buy-at-bulk and shallow-light $$k$$ k -Steiner trees and $$(k,2)$$ ( k, 2 ) -subgraph

M. Reza Khani () and Mohammad R. Salavatipour ()
Additional contact information
M. Reza Khani: University of Maryland
Mohammad R. Salavatipour: University of Alberta

Journal of Combinatorial Optimization, 2016, vol. 31, issue 2, No 12, 669-685

Abstract: Abstract In this paper we give improved approximation algorithms for some network design problems. In the bounded-diameter or shallow-light $$k$$ k -Steiner tree problem (SL $$k$$ k ST), we are given an undirected graph $$G=(V,E)$$ G = ( V , E ) with terminals $$T\subseteq V$$ T ⊆ V containing a root $$r\in T$$ r ∈ T , a cost function $$c:E\rightarrow \mathbb {R}^+$$ c : E → R + , a length function $$\ell :E\rightarrow \mathbb {R}^+$$ ℓ : E → R + , a bound $$L>0$$ L > 0 and an integer $$k\ge 1$$ k ≥ 1 . The goal is to find a minimum $$c$$ c -cost $$r$$ r -rooted Steiner tree containing at least $$k$$ k terminals whose diameter under $$\ell $$ ℓ metric is at most $$L$$ L . The input to the buy-at-bulk $$k$$ k -Steiner tree problem (BB $$k$$ k ST) is similar: graph $$G=(V,E)$$ G = ( V , E ) , terminals $$T\subseteq V$$ T ⊆ V containing a root $$r\in T$$ r ∈ T , cost and length functions $$c,\ell :E\rightarrow \mathbb {R}^+$$ c , ℓ : E → R + , and an integer $$k\ge 1$$ k ≥ 1 . The goal is to find a minimum total cost $$r$$ r -rooted Steiner tree $$H$$ H containing at least $$k$$ k terminals, where the cost of each edge $$e$$ e is $$c(e)+\ell (e)\cdot f(e)$$ c ( e ) + ℓ ( e ) · f ( e ) where $$f(e)$$ f ( e ) denotes the number of terminals whose path to root in $$H$$ H contains edge $$e$$ e . We present a bicriteria $$(O(\log ^2 n),O(\log n))$$ ( O ( log 2 n ) , O ( log n ) ) -approximation for SL $$k$$ k ST: the algorithm finds a $$k$$ k -Steiner tree with cost at most $$O(\log ^2 n\cdot \text{ opt }^*)$$ O ( log 2 n · opt ∗ ) where $$\text{ opt }^*$$ opt ∗ is the cost of an LP relaxation of the problem and diameter at most $$O(L\cdot \log n)$$ O ( L · log n ) . This improves on the algorithm of Hajiaghayi et al. (2009) (APPROX’06/Algorithmica’09) which had ratio $$(O(\log ^4 n), O(\log ^2 n))$$ ( O ( log 4 n ) , O ( log 2 n ) ) . Using this, we obtain an $$O(\log ^3 n)$$ O ( log 3 n ) -approximation for BB $$k$$ k ST, which improves upon the $$O(\log ^4 n)$$ O ( log 4 n ) -approximation of Hajiaghayi et al. (2009). We also consider the problem of finding a minimum cost $$2$$ 2 -edge-connected subgraph with at least $$k$$ k vertices, which is introduced as the $$(k,2)$$ ( k , 2 ) -subgraph problem in Lau et al. (2009) (STOC’07/SICOMP09). This generalizes some well-studied classical problems such as the $$k$$ k -MST and the minimum cost $$2$$ 2 -edge-connected subgraph problems. We give an $$O(\log n)$$ O ( log n ) -approximation algorithm for this problem which improves upon the $$O(\log ^2 n)$$ O ( log 2 n ) -approximation algorithm of Lau et al. (2009).

Keywords: Combinatorial optimization; Approximation algorithms; Network design; Steiner tree; $$k$$ k -edge connected (search for similar items in EconPapers)
Date: 2016
References: View references in EconPapers View complete reference list from CitEc
Citations:

Downloads: (external link)
http://link.springer.com/10.1007/s10878-014-9774-5 Abstract (text/html)
Access to the full text of the articles in this series is restricted.

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:spr:jcomop:v:31:y:2016:i:2:d:10.1007_s10878-014-9774-5

Ordering information: This journal article can be ordered from
https://www.springer.com/journal/10878

DOI: 10.1007/s10878-014-9774-5

Access Statistics for this article

Journal of Combinatorial Optimization is currently edited by Thai, My T.

More articles in Journal of Combinatorial Optimization from Springer
Bibliographic data for series maintained by Sonal Shukla () and Springer Nature Abstracting and Indexing ().