Approximation Algorithms for Minimum-Cost $k\hbox{-}(S, T)$ Connected Digraphs.
Joseph CheriyanBundit LaekhanukitPublished in: SIAM J. Discret. Math. (2013)
Keyphrases
- approximation algorithms
- minimum cost
- undirected graph
- np hard
- network flow
- special case
- vertex cover
- worst case
- network flow problem
- spanning tree
- network design problem
- directed graph
- combinatorial auctions
- capacity constraints
- disjoint paths
- linear programming
- constant factor
- approximation ratio
- upper bound
- search algorithm
- scheduling problem
- randomized algorithms
- weighted sum
- convex optimization