For a time-sensitive application, the usefulness of its end results (also called the application's accrued utility value in the paper) depends on the time when the application is completed and its results are deli...
详细信息
For a time-sensitive application, the usefulness of its end results (also called the application's accrued utility value in the paper) depends on the time when the application is completed and its results are delivered. In this paper, we address the accrued utility value maximization problem for narrow parallel and time-sensitive applications. We first consider the problem in the context of a discrete time domain and present the Spatial-Temporal Interference Based (STIB) scheduling algorithm. We formally prove that the STIB algorithm is a 2-approximation algorithm. Second, we extend our work to a continuous time domain and present a heuristic scheduling algorithm, i.e., the Continuous Spatial-Temporal Interference Based (STIB-C) algorithm to maximize the system's total accrued utility value when the system operates in a continuous time domain. The extensive empirical evaluations reveal that: (1) in a discrete time domain, the systems' total accrued utility values obtained through the STIB algorithm are consistent with the theoretic bound, i.e., they never go below 50 percent of the optimal value. In fact, on average, the STIB algorithm can achieve over 92.5 percent of the optimal value;(2) compared to other scheduling policies listed in the literature, the developed STIB and STIB-C algorithms have clear advantages in terms of the system's total accrued utility value and the profitable application ratio. In particular, in terms of the system's total accrued utility value, both the STIB and the STIB-C algorithms achieve as much as six times for both the First Come First Come Serve(FCFS) with backfilling algorithm and the Gang Earliest Deadline First (EDF) algorithm, and 4.5 times for the 0-1 Knapsack based scheduling algorithm. In terms of the profitable application ratio, both the STIB and the STIB-C algorithms obtain as much as four times for both the FCFS with backfilling algorithm and the Gang EDF algorithm, and two times for the 0-1 Knapsack based scheduling algo
It is well-known that the multiple knapsack problem is NP-hard, and does not admit an FPTAS even for the case of two identical knapsacks. Whereas the 0-1 knapsack problem with only one knapsack has been intensively st...
详细信息
It is well-known that the multiple knapsack problem is NP-hard, and does not admit an FPTAS even for the case of two identical knapsacks. Whereas the 0-1 knapsack problem with only one knapsack has been intensively studied, and some effective exact or approximation algorithms exist. A natural approach for the multiple knapsack problem is to pack the knapsacks successively by using an effective algorithm for the 0-1 knapsack problem. This paper considers such an approximation algorithm that packs the knapsacks in the nondecreasing order of their capacities. We analyze this algorithm for 2 and 3 knapsack problems by the worst-case analysis method and give all their error bounds.
Modifying the topology of a network to mitigate the spread of an epidemic with epidemiological constant. amounts to the NP-hard problem of finding a partial subgraph with maximum number of edges and spectral radius bo...
详细信息
Modifying the topology of a network to mitigate the spread of an epidemic with epidemiological constant. amounts to the NP-hard problem of finding a partial subgraph with maximum number of edges and spectral radius bounded above by.. A software-defined network capable of real-time topology reconfiguration can then use an algorithm for finding such subgraph to quickly remove spreading malware threats without deploying specific security countermeasures. In this paper, we propose a novel randomized approximation algorithm based on the relaxation and rounding framework that achieves a O(log n) approximation in the case of finding a subgraph with spectral radius bounded by.. [log n,.1(G)) where.1(G) is the spectral radius of the input graph and n is the number of nodes. We combine this algorithm with a maximum matching algorithm to obtain a O(log2 n)-approximation algorithm for all values of.. We also describe how the mathematical programming formulation we give has several advantages over previous approaches which attempted at finding a subgraph with minimum spectral radius given an edge removal budget. Finally, we show that the analysis of our randomized rounding scheme is essentially tight by relating it to classical results from random graph theory.
We give an algorithm that for an input planar graph G of n vertices and an integer k, in min{O(n log(3) n), O(nk(2))} time either constructs a branch-decomposition of G of width at most (2 + delta)k, where delta > ...
详细信息
We give an algorithm that for an input planar graph G of n vertices and an integer k, in min{O(n log(3) n), O(nk(2))} time either constructs a branch-decomposition of G of width at most (2 + delta)k, where delta > 0 is a constant, or a (k+1) x inverted right perpendicular K+1/2 inverted right perpendicular cylinder minor of G implying bw(G) > k, where bw(G) is the branchwidth of G. This is the first (O) over tilde (n) time constant-factor approximation for branchwidth/treewidth and largest grid/cylinder minors of planar graphs and improves the previous min{O(n(1 + epsilon) ), O(nk(2))} (where epsilon > 0 is a constant) time constant-factor approximations. For a planar graph G and k = bw(G), a branch-decomposition of width at most (2 + delta)k and a g x g/2 cylinder/grid minor with g = k/beta where beta > 2 is a constant, can be computed by our algorithm in min{O(n log(3) nlog k), O(nk(2) log k)} time. (C) 2018 Elsevier B.V. All rights reserved.
In the group Steiner problem we are given an edge-weighted graph G = (V, E, w) and in subsets of vertices {g(i)}(i=1)(m). Each subset gi is called a group and the vertices in boolean OR(i)g(i) are called terminals. It...
详细信息
In the group Steiner problem we are given an edge-weighted graph G = (V, E, w) and in subsets of vertices {g(i)}(i=1)(m). Each subset gi is called a group and the vertices in boolean OR(i)g(i) are called terminals. It is required to find a minimum weight tree that contains at least one terminal from every group. We present a poly-logarithmic ratio approximation for this problem when the input graph is a tree. Our algorithm is a recursive greedy algorithm adapted from the greedy algorithm for the directed Steiner tree problem [Approximating the weight of shallow Steiner trees, Discrete Appl. Math. 93 (1999) 265-285, approximation algorithms for directed Steiner problems, J. algorithms 33 (1999) 73-91]. This is in contrast to earlier algorithms that are based on rounding a linear programming based relaxation for the problem [A polylogarithmic approximation algorithm for the Group Steiner tree problem, J. algorithms 37 (2000) 66-84, preliminary version in Proceedings of SODA, 1998 pp. 253-259, On directed Steiner trees, Proceedings of SODA, 2002, pp. 59-63]. We answer in positive a question posed in [A polylogarithmic approximation algorithm for the Group Steiner tree problem, J. algorithms 37 (2000) 66-84, preliminary version in Proceedings of SODA, 1998 pp. 253-259] on whether there exist good approximation algorithms for the group Steiner problem that are not based on rounding linear programs. For every fixed constant epsilon > 0, our algorithm gives an O((log Sigma(i)vertical bar g(i)vertical bar)(1+epsilon) center dot log m) approximation in polynomial time. approximation algorithms for trees can be extended to arbitrary undirected graphs by probabilistically approximating the graph by a tree. This results in an additional multiplicative factor of O(log vertical bar V vertical bar) in the approximation ratio, where vertical bar V vertical bar is the number of vertices in the graph. The approximation ratio of our algorithm on trees is slightly worse than the ratio
Link scheduling is a fundamental problem in wireless ad hoc and sensor networks. In this paper, we focus on the shortest link scheduling (SLS) under Signal-to-Interference-plus-Noise-Ratio and hypergraph models, and p...
详细信息
Link scheduling is a fundamental problem in wireless ad hoc and sensor networks. In this paper, we focus on the shortest link scheduling (SLS) under Signal-to-Interference-plus-Noise-Ratio and hypergraph models, and propose an approximation algorithm (A link scheduling algorithm with oblivious power assignment for the shortest link scheduling) with oblivious power assignment for better performance than GOW* proposed by Blough et al. [IEEE/ACM Trans Netw 18(6):1701-1712, 2010]. For the average scheduling length of is 1 / m of GOW*, where is the expected number of the links in the set V returned by the algorithm HyperMaxLS (Maximal links schedule under hypergraph model) and is the constant. In the worst, ideal and average cases, the ratios of time complexity of our algorithm to that of GOW* are , and , respectively. Where () is a constant called the SNR diversity of an instance G.
We give a 7.18-approximation algorithm for the minimum latency problem that uses only O(n log n) calls to the prize-collecting Steiner tree (PCST) subroutine of Goemans and Williamson. This improves the previous best ...
详细信息
We give a 7.18-approximation algorithm for the minimum latency problem that uses only O(n log n) calls to the prize-collecting Steiner tree (PCST) subroutine of Goemans and Williamson. This improves the previous best algorithms in both performance guarantee and running time. A previous algorithm of Goemans and Kleinberg for the minimum latency problem requires an approximation algorithm for the k-minimum spanning tree (k-MST) problem which is called as a black box for each value of k. Their algorithm can achieve an approximation factor of 10.77 while making O(n(n + log C) log n) PCST calls, a factor of 8.98 using O(n(3)(n + log C) log n) PCST calls, or a factor of 7.18 + epsilon using n(O(1/epsilon)) log C PCST calls, via the k-MST algorithms of Garg, Arya and Ramesh, and Arora and Karakostas, respectively. Here n denotes the number of nodes in the instance, and C is the largest edge cost in the input. In all cases, the running time is dominated by the PCST calls. Since the PCST subroutine can be implemented to run in O(n(2)) time, the overall running time of our algorithm is O(n3 log n). We also give a faster randomized version of our algorithm that achieves the same approximation guarantee in expectation, but uses only O(log(2) n) PCST calls, and derandomize it to obtain a deterministic algorithm with factor 7.18 + epsilon, using O(1/epsilon log(2) n) PCST calls. The basic idea for our improvement is that we do not treat the k-MST algorithm as a black box. This allows us to take advantage of some special situations in which the PCST subroutine delivers a 2-approximate k-MST. We are able to obtain the same approximation ratio that would be given by Goemans and Kleinberg if we had access to 2-approximate k-MSTs for all values of k, even though we have them only for some values of k that we are not able to specify in advance. We also extend our algorithm to a weighted version of the minimum latency problem.
We consider the k-level capacitated facility location problem (k-CFLP), which is a natural variant of the classical facility location problem and has applications in supply chain management. We obtain the first (combi...
详细信息
We consider the k-level capacitated facility location problem (k-CFLP), which is a natural variant of the classical facility location problem and has applications in supply chain management. We obtain the first (combinatorial) approximation algorithm with a performance factor of k + 2 + root k(2) + 2k + 5 + epsilon (epsilon > 0) for this problem.
In this paper, we introduce the k-prize-collecting minimum power cover problem (k-PCPC). In this problem, we are given a point set V, a sensor set S on a plane and a parameter k with k <= |V|. Each sensor can adjus...
详细信息
In this paper, we introduce the k-prize-collecting minimum power cover problem (k-PCPC). In this problem, we are given a point set V, a sensor set S on a plane and a parameter k with k <= |V|. Each sensor can adjust its power and the covering range of sensor s with power p(D(s, r (s))) is a disk D(s, r (s)), where r (s) is the radius of disk D(s, r (s)) and p(D(s, r (s))) = c center dot r (s)(alpha). The k-PCPC determines a disk set F such that at least k points are covered, where the center of any disk in F is a sensor. The objective is to minimize the total power of the disk set F plus the penalty of R, where R is the set of points that are not covered by F. This problem generalizes the well-known minimum power cover problem, minimum power partial cover problem and prize collecting minimum power cover problem. Our main result is to present a novel two-phase primal-dual algorithm for the k-PCPC with an approximation ratio of at most 3(alpha).
In this paper we present a polynomial time approximation scheme for the most points covering problem. In the most points covering problem, n points in R-2, r > 0, and an integer m> 0 are given and the goal is to...
详细信息
In this paper we present a polynomial time approximation scheme for the most points covering problem. In the most points covering problem, n points in R-2, r > 0, and an integer m> 0 are given and the goal is to cover the maximum number of points with m disks with radius r. The dual of the most points covering problem is the partial covering problem in which n points in R-2 are given, and we try to cover at least p <= n points of these n points with the minimum number of disks. Both these problems are NP-hard. To solve the most points covering problem, we use the solution of the partial covering problem to obtain an upper bound for the problem and then we generate a valid solution for the most points covering problem by a careful modification of the partial covering solution. We first present an improved approximation algorithm for the partial covering problem which has a better running time than the previous algorithm for this problem. Using this algorithm, we attain a (1 - 2 epsilon/1+)-approximation algorithm for the most points covering problem. The running time of our algorithm is O((1 + epsilon) mn + epsilon(-1)n(4)root 2(epsilon-1) + 2) which is polynomial with respect to both m and n, whereas the previously known algorithm for this problem runs in O(n log n + n epsilon(-6m+6) log(1/epsilon)) which is exponential regarding m.
暂无评论