We consider the k-Directed Steiner Forest (k-DSF) problem: Given a directed graph G = (V, E) with edge costs, a collection D subset of V x V of ordered node pairs, and an integer k <= vertical bar D vertical bar, f...
详细信息
We consider the k-Directed Steiner Forest (k-DSF) problem: Given a directed graph G = (V, E) with edge costs, a collection D subset of V x V of ordered node pairs, and an integer k <= vertical bar D vertical bar, find a minimum cost subgraph H of G that contains an st-path for (at least) k pairs (s, t) is an element of D. When k = vertical bar D vertical bar, we get the Directed Steiner Forest (DSF) problem. The best known approximation ratios for these problems are: (O) over tilde (k(2/3)) for k-DSF by Charikar et al. (1999)[6], and O(k(1/2+epsilon)) for DSF by Chekuri et al. (2008)[7]. Our main result is achieving the first sub-linear in terms of n = vertical bar V vertical bar approximation ratio for DSF. Specifically, we give an O(n(epsilon).min{n(4/5), m(2/3)})-approximation scheme for DSF. For k-DSF we give a simple greedy O(k(1/2+epsilon))-approximation algorithm. This improves upon the best known ratio (O) over tilde (k(2/3)) by Charikar et al. (1999) [6], and (almost) matches, in terms of k, the best ratio known for the undirected variant (Gupta et al., 2010 [18]). This algorithm uses a new structure called start-junction tree which may be of independent interest. (C) 2011 Elsevier Inc. All rights reserved.
In this note,we provide an almost tight lower bound for the scheduling problem to meet two min-sum objectives considered by Angel et *** ***.35(1):69–73,2007.
In this note,we provide an almost tight lower bound for the scheduling problem to meet two min-sum objectives considered by Angel et *** ***.35(1):69–73,2007.
Given a simple polygon Q drawn on a piece of planar material R, we cut Q out of R by a circular saw with a total number of cuts no more than twice the optimal. This improves the previous approximation ratio of 2.5 obt...
详细信息
Given a simple polygon Q drawn on a piece of planar material R, we cut Q out of R by a circular saw with a total number of cuts no more than twice the optimal. This improves the previous approximation ratio of 2.5 obtained by Demaine et *** 2001.
Establishing consistent correspondences between two sets of features is a fundamental problem in computer vision. This problem can be well formulated as graph matching in which nodes and edges represent feature points...
详细信息
Establishing consistent correspondences between two sets of features is a fundamental problem in computer vision. This problem can be well formulated as graph matching in which nodes and edges represent feature points and pairwise relationships between feature points, respectively. Spectral matching [19] is the state-of-the-art eigenvector-based method for graph matching. The spectral matching algorithm has been used successfully for small data, but its heavy memory requirement limited the maximum data sizes and contexts it can be used. In this paper, we propose FASM, a fast and scalable approximate spectral matching algorithm. The main ideas are twofold. First, we exploit the redundancy in the data generation process to approximate the affinity matrix with the linear combination of Kronecker products between bases and index matrices. The bases and index matrices are highly compressed representation of the approximated affinity matrix, requiring much smaller memory than in previous works which store the whole affinity matrix. Second, we compute the eigenvector of the approximated affinity matrix using the small bases and index matrices without explicitly materializing the approximated matrix. Experimental results show that our proposed method is up to 33 x faster, requiring up to 645x smaller memory than the exact algorithm, with little or no loss of accuracy. (C) 2012 Elsevier Inc. All rights reserved.
While it is known that the d-dimensional Steiner minimum tree problem in Hamming metric is NP-complete if d is part of the input, it is an open question whether this also holds for fixed dimensions. In this paper, thi...
详细信息
While it is known that the d-dimensional Steiner minimum tree problem in Hamming metric is NP-complete if d is part of the input, it is an open question whether this also holds for fixed dimensions. In this paper, this question is answered by showing that the Steiner minimum tree problem in Hamming metric is already NP-complete in 3 dimensions. Furthermore, we show that, the minimum spanning tree gives a 2 - 2/d approximation on the Steiner minimum tree for d >= 2. Using this result, we analyse the so-called k-LCA and A(k) approximation algorithms and show improved approximation guarantees for low dimensions. (C) 2013 Elsevier B.V. All rights reserved.
Relay Stations (RSs) can be deployed in a wireless network to extend its coverage and improve its capacity. Smart (directional) antennas can enhance the functionalities of RSs by forming the beam only towards intended...
详细信息
ISBN:
(纸本)9781467359467
Relay Stations (RSs) can be deployed in a wireless network to extend its coverage and improve its capacity. Smart (directional) antennas can enhance the functionalities of RSs by forming the beam only towards intended receiving Subscriber Stations (SSs). In this paper, we study a joint problem of selecting a beam width and direction for the smart antenna at each RS and determining the RS assignment for SSs in each scheduling period. The objective is to maximize a utility function that can lead to a stable and high-throughput system. We define this as the Beam Scheduling and Relay Assignment Problem (BS-RAP). We show that BS-RAP is NP-hard, present a Mixed Integer Linear Programming (MILP) formulation to provide optimal solutions and present two polynomial-time greedy algorithms, one of which is shown to have a constant factor approximation ratio.
A balanced V-shape is a polygonal region in the plane contained in the union of two crossing equal-width strips. It is delimited by two pairs of parallel rays that emanate from two points x, y, are contained in the st...
详细信息
A balanced V-shape is a polygonal region in the plane contained in the union of two crossing equal-width strips. It is delimited by two pairs of parallel rays that emanate from two points x, y, are contained in the strip boundaries, and are mirror-symmetric with respect to the line xy. The width of a balanced V-shape is the width of the strips. We first present an O (n(2) log n) time algorithm to compute, given a set of n points P. a minimum-width balanced V-shape covering P. We then describe a PTAS for computing a (1 + epsilon)-approximation of this V-shape in time O((n/epsilon) log n + (n/epsilon(3/2))log(2)(1/epsilon)). A much simpler constant-factor approximation algorithm is also described. (C) 2012 Elsevier B.V. All rights reserved.
We consider the following simple network design problem. The input consists of n weighted nodes, and the output is an edge-weighted connected network such that the total weight of the edges incident to a node is at le...
详细信息
We consider the following simple network design problem. The input consists of n weighted nodes, and the output is an edge-weighted connected network such that the total weight of the edges incident to a node is at least the given weight of the node. We aim to design the cheapest connected network;that is, the reachability of the network should be guaranteed, and the network is better if its total weight is less. In this article, we first show an efficient algorithm that produces an optimal network with minimum weight. The algorithm runs in linear time, and the resulting network contains at most n edges, where n is the number of nodes. To construct a connected network, at least n - 1 edges are required. However, the algorithm sometimes outputs n edges. Next, we aim to minimize not only the weight but also the number of edges. That is, for given n weighted nodes, we aim to design a cheapest tree. Then, the problem becomes NP-complete. We also propose efficient approximation algorithms for constructing a cheapest tree. (c) 2013 Wiley Periodicals, Inc.
A subset L subset of V of a graph G = (V, E) is called a connected liar's dominating set of G if (i) for all v. V, |NG[v] n L| >= 2, ( ii) for every pair u, v is an element of V of distinct vertices, |(N-G[u]. ...
详细信息
A subset L subset of V of a graph G = (V, E) is called a connected liar's dominating set of G if (i) for all v. V, |NG[v] n L| >= 2, ( ii) for every pair u, v is an element of V of distinct vertices, |(N-G[u]. N-G[v]) boolean AND L| >= 3, and ( iii) the induced subgraph of G on L is connected. In this paper, we initiate the algorithmic study of minimum connected liar's domination problem by showing that the corresponding decision version of the problem is NP-complete for general graph. Next we study this problem in subclasses of chordal graphs where we strengthen the NP-completeness of this problem for undirected path graph and prove that this problem is linearly solvable for block graphs. Finally, we propose an approximation algorithm for minimum connected liar's domination problem and investigate its hardness of approximation in general graphs.
In many real-world scenarios, social network serves as a platform for information diffusion, alongside with positive information (truth) dissemination, negative information (rumor) also spread among the public. To mak...
详细信息
ISBN:
(纸本)9780769550008
In many real-world scenarios, social network serves as a platform for information diffusion, alongside with positive information (truth) dissemination, negative information (rumor) also spread among the public. To make the social network as a reliable medium, it is necessary to have strategies to control rumor diffusion. In this article, we address the Least Cost Rumor Blocking (LCRB) problem where rumors originate from a community C-r in the network and a notion of protectors are used to limit the bad influence of rumors. The problem can be summarized as identifying a minimal subset of individuals as initial protectors to minimize the number of people infected in neighbor communities of C-r at the end of both diffusion processes. Observing the community structure property, we pay attention to a kind of vertex set, called bridge end set, in which each node has at least one direct in-neighbor in C-r and is reachable from rumors. Under the OOAO model, we study LCRB-P problem, in which alpha (0 < alpha < 1) fraction of bridge ends are required to be protected. We prove that the objective function of this problem is submodular and a greedy algorithm is adopted to derive a (1-1/e)-approximation. Furthermore, we study LCRB-D problem over the DOAA model, in which all the bridge ends are required to be protected, we prove that there is no polynomial time 0(ln n)-approximation for the LCRB-D problem unless P = NP and propose a Set Cover Based Greedy (SCBG) algorithm which achieves a O(ln n)-approximation ratio. Finally, to evaluate the efficiency and effectiveness of our algorithm, we conduct extensive comparison simulations in three real-world datasets, and the results show that our algorithm outperforms other heuristics.
暂无评论