We consider a network, where a special data called certificate is issued between two users, and all certificates issued by the users in the network can be represented by a directed graph. For any two users u and v, wh...
详细信息
We consider a network, where a special data called certificate is issued between two users, and all certificates issued by the users in the network can be represented by a directed graph. For any two users u and v, when u needs to send a message to u securely, v's public-key is needed. The user u can obtain v's public-key using the certificates stored in u and v. We need to disperse the certificates to the users such that when a user wants to send a message to the other user securely, there are enough certificates in them to get the reliable public-key. In this paper, when a certificate graph and a set of communication requests are given, we consider the problem to disperse the certificates among the nodes in the network, such that the communication requests are satisfied and the total number of certificates stored in the nodes is minimized. We formulate this problem as MINIMUM CERTIFICATE DISPERSAL (MCD for short). We show that MCD is NP-Complete, even if its input graph is restricted to a strongly connected graph. We also present a polynomial-time 2-approximation algorithm MinPivot for strongly connected graphs, when the communication requests satisfy some restrictions. We introduce some graph classes for which MinPivot can compute optimal dispersals, such as trees, rings, and some Cartesian products of graphs.
Given a weighted directed graph G = (V, E, c), where c : E -> R+ is an edge cost function, a subset X of vertices (terminals), and a root vertex v(r), the directed Steiner tree problem (DSP) asks for a minimum-cost...
详细信息
Given a weighted directed graph G = (V, E, c), where c : E -> R+ is an edge cost function, a subset X of vertices (terminals), and a root vertex v(r), the directed Steiner tree problem (DSP) asks for a minimum-cost tree which spans the paths from root vertex v(r) to each terminal. Charikar et al.'s algorithm is well-known for this problem. It achieves an approximation guarantee of l(l - 1)k(1/l) in O(n(l)k(2l)) time for any fixed level l > 1, where 1 is the level of the tree produced by the algorithm, n is the number of vertices, vertical bar V vertical bar, and k is the number of terminals, vertical bar X vertical bar. However, it requires a great amount of computing power, and there are some problems in the proof of the approximation guarantee of the algorithm. This paper provides a faster approximation algorithm improving Charikar et al.'s DSP algorithm with a better time complexity, O(n(l)K(l) + n(2)k + nm), where m is the number of edges, and an amended root 8k - delta In k factor for the 2-level Steiner tree, where delta = root 6 - 2 = 0.4494.
The connected dominating set （CDS） problem, which consists of finding a smallest connected dominating set for graphs is an NP-hard problem in the unit disk graphs （UDGs）. This paper focuses on the CDS problem in w...
详细信息
The connected dominating set （CDS） problem, which consists of finding a smallest connected dominating set for graphs is an NP-hard problem in the unit disk graphs （UDGs）. This paper focuses on the CDS problem in wireless networks. Investigation of some properties of independent set （IS） in UDGs shows that geometric features of nodes distribution like angle and area can be used to design efficient heuristics for the approximation algorithms. Several constant factor approximation algorithms are presented for the CDS problem in UDGs. Simulation results show that the proposed algorithms perform better than some known ones.
Non-preemptive scheduling of n independent jobs on m unrelated machines so as to minimize the maximal job completion time is considered. A polynomial algorithm with the worst-case absolute error of min{(1 - 1/m)p(max)...
详细信息
Non-preemptive scheduling of n independent jobs on m unrelated machines so as to minimize the maximal job completion time is considered. A polynomial algorithm with the worst-case absolute error of min{(1 - 1/m)p(max), p'(max)) is presented, where p(max) is the largest job processing time and p'(max) is the mth element from the non-increasing list of job processing times. This is better than the earlier known best absolute error of p(max). The algorithm is based on the rounding of acyclic multiprocessor distributions. An O(nm(2)) algorithm for the construction of an acyclic multiprocessor distribution is also presented. (C) 2006 Wiley Periodicals, Inc.
This paper presents an approximation algorithm for a vehicle routing problem on a tree-shaped network with a single depot where there are two types of demands, pickup demand and delivery demand. Customers are located ...
详细信息
This paper presents an approximation algorithm for a vehicle routing problem on a tree-shaped network with a single depot where there are two types of demands, pickup demand and delivery demand. Customers are located on nodes of the tree, and each customer has a positive demand of pickup and/or delivery. Demands of customers are served by a fleet of identical vehicles with unit capacity. Each vehicle can serve pickup and delivery demands. It is assumed that the demand of a customer is splittable, i.e., it can be served by more than one vehicle. The problem we are concerned with in this paper asks to find a set of tours of the vehicles with minimum total lengths. In each tour, a vehicle begins at the depot with certain amount of goods for delivery, visits a subset of the customers in order to deliver and pick up goods and returns to the depot. At any time during the tour, a vehicle must always satisfy the capacity constraint, i.e., at any time the sum of goods to be delivered and that of goods that have been picked up is not allowed to exceed the vehicle capacity. We propose a 2-approximation algorithm for the problem. (c) 2006 Elsevier B.V. All rights reserved.
We study the NP-hard problem of labeling points with maximum-radius circle pairs: given n point sites in the plane, find a placement for 2n interior-disjoint uniform circles, such that each site touches two circles an...
详细信息
We study the NP-hard problem of labeling points with maximum-radius circle pairs: given n point sites in the plane, find a placement for 2n interior-disjoint uniform circles, such that each site touches two circles and the circle radius is maximized. We present a new approximation algorithm for this problem that runs in O(n log n + n log epsilon\1) time and O(n) space and achieves an approximation factor of (2 + root 3 + 2 root 4 + root 3)/(4 + root 3) + epsilon (approximate to 1.486 + epsilon), which improves the previous best bound of 1.491 + epsilon. (c) 2006 Elsevier B.V. All rights reserved.
Software product lines(SPLs) technology produce software by integrating reusable software components based on customer *** researchers pay great attention to feature modeling technology that can represent SPLs' pr...
详细信息
Software product lines(SPLs) technology produce software by integrating reusable software components based on customer *** researchers pay great attention to feature modeling technology that can represent SPLs' production requirements and functionalities.A key challenge is selecting valid and optimal feature combinations from the feature model to satisfy various requirements of customers and vendors, including various value and cost *** paper experimentally studies a knapsack approximation algorithm of feature selection for automated product derivation in *** approach generates an approximation solution by a modified Filtered Cartesian Flattening algorithm and obtains the optimal solution with a greed *** performed experiments on randomly generated feature models with different characteristics. Experiments show that our approach can select highly optimal feature combinations effectively.
Broadcast scheduling is a mechanism for performing interference-aware broadcasting in multi-hop wireless sensor networks (WSNs). Existing studies assume all the WSN nodes lie on a 2D plane. This assumption is not alwa...
详细信息
ISBN:
(纸本)9783642034169
Broadcast scheduling is a mechanism for performing interference-aware broadcasting in multi-hop wireless sensor networks (WSNs). Existing studies assume all the WSN nodes lie on a 2D plane. This assumption is not always appropriate, as in practice the sensor nodes may acquire positions in the 3D space. In this paper, we study the broadcast scheduling problem in which we consider two different models of the transmission graph: Disk Graph (DG) in 2D and Ball Graph (BG) in 3D. We consider each node may have different transmission ranges and the interference range is a time of the transmission range (where alpha > 1). We devise efficient coloring methods for coloring a hexagonal tiling in 2D and truncated octahedragonal tiling in 3D, which leads to O(1)-approximation ratio for broadcast scheduling problem in 2D and 3D, respectively.
In the Densest k-Subgraph problem, given a graph G and a parameter k, one needs to find a subgraph of G induced on k vertices that contains the largest number of edges. There is a significant gap between the best know...
详细信息
ISBN:
(纸本)9781450300506
In the Densest k-Subgraph problem, given a graph G and a parameter k, one needs to find a subgraph of G induced on k vertices that contains the largest number of edges. There is a significant gap between the best known upper and lower bounds for this problem. It is NP-hard, and does not have a PTAS unless NP has subexponential time algorithms. On the other hand, the current best known algorithm of Feige, Kortsarz and Peleg, gives an approximation ratio of n1/3 - c for some fixed c>0 (later estimated at around c= 1/90).We present an algorithm that for every ε> 0 approximates the Densest k-Subgraph problem within a ratio of n¼ + ε in time nO(1/ε). If allowed to run for time nO(log n), the algorithm achieves an approximation ratio of O(n¼). Our algorithm is inspired by studying an average-case version of the problem where the goal is to distinguish random graphs from random graphs with planted dense subgraphs -- the approximation ratio we achieve for the general case matches the "distinguishing ratio" we obtain for this planted *** a high level, our algorithms involve cleverly counting appropriately defined trees of constant size in G, and using these counts to identify the vertices of the dense subgraph. We say that a graph G(V,E) has log-density α if its average degree is Θ(|V|α). The algorithmic core of our result is a procedure to output a k-subgraph of 'nontrivial' density whenever the log-density of the densest k-subgraph is larger than the log-density of the host *** outline an extension to our approximation algorithm which achieves an O(n¼ -ε)-approximation in O(2nO(ε)) time. We also show that, for certain parameter ranges, eigenvalue and SDP based techniques can outperform our basic distinguishing algorithm for random instances (in polynomial time), though without improving upon the O(n¼) guarantee overall.
Given a weighted directed hypergraph H =（V,E;w）,where w:E→R,we consider the problem of embedding all weighted directed hyperedges on a mixed cycle,which consists of undirected and directed *** objective is to minim...
详细信息
Given a weighted directed hypergraph H =（V,E;w）,where w:E→R,we consider the problem of embedding all weighted directed hyperedges on a mixed cycle,which consists of undirected and directed *** objective is to minimize the maximum congestion of any undirected or directed link in the mixed *** this paper,we first formulate this new problem as an integer linear program,and by utilizing a nontrivial LP-rounding technique,we design a 2- approximation ***,we design a combinatorial algorithm with approximation ratio 3 for the problem,whose running time is 0（nm）.Finally,we present a polynomial time approximation scheme（PTAS） for the special version where each directed hyperedge only contains one sink.
暂无评论