In this paper, we introduce the k-generalized Steiner forest (k-GSF) problem, which is a natural generalization of the k-Steiner forest problem and the generalized Steiner forest problem. In this problem, we are given...
详细信息
In this paper, we introduce the k-generalized Steiner forest (k-GSF) problem, which is a natural generalization of the k-Steiner forest problem and the generalized Steiner forest problem. In this problem, we are given a connected graph G = (V, E) with non-negative costs c(e) for the edges e is an element of E, a set of disjoint vertex sets V = {V-1, V-2, ..., V-l} and a parameter k <= 1. The goal is to find a minimum-cost edge set F subset of E that connects at least k vertex sets in V. Our main work is to construct an O(root l)-approximation algorithm for the k-GSF problem based on a greedy approach and an lp-rounding technique.
Correlation clustering is an approach for clustering a set of objects from given pairwise information. In this approach, the given pairwise information is usually represented by an undirected graph with nodes correspo...
详细信息
Correlation clustering is an approach for clustering a set of objects from given pairwise information. In this approach, the given pairwise information is usually represented by an undirected graph with nodes corresponding to the objects, where each edge in the graph is assigned a nonnegative weight, and either the positive or negative label. Then, a clustering is obtained by solving an optimization problem of finding a partition of the node set that minimizes the disagreement or maximizes the agreement with the pairwise information. In this paper, we extend correlation clustering with disagreement minimization to deal with higher-order relationships represented by hypergraphs. We give two pivoting algorithms based on a linear programming relaxation of the problem. One achieves an O(klogn)-approximation, where n is the number of nodes and k is the maximum size of hyperedges with the negative labels. This algorithm can be applied to any hyperedges with arbitrary weights. The other is an O(r)-approximation for complete r-partite hypergraphs with uniform weights. This type of hypergraphs arise from the coclustering setting of correlation clustering.
We study the two-stage stochastic facility location problem(2-SFlp)by proposing an lp(location problem)-rounding approximation algorithm with 2.3613 per-scenario bound for this problem,improving the previously best pe...
详细信息
We study the two-stage stochastic facility location problem(2-SFlp)by proposing an lp(location problem)-rounding approximation algorithm with 2.3613 per-scenario bound for this problem,improving the previously best per-scenario bound of 2.4957.
暂无评论