We address the bodyguard allocation problem （BAP）, an optimization problem that illustrates the conflict of interest between two classes of processes with contradictory preferences within a distributed system. While...
详细信息
We address the bodyguard allocation problem （BAP）, an optimization problem that illustrates the conflict of interest between two classes of processes with contradictory preferences within a distributed system. While a class of processes prefers to minimize its distance to a particular process called the root, the other class prefers to maximize it; at the same time, all the processes seek to build a communication spanning tree with the maximum social welfare. The two state-of-the-art algorithms for this problem always guarantee the generation of a spanning tree that satisfies a condition of Nash equilibrium in the system; however, such a tree does not necessarily produce the maximum social welfare. In this paper, we propose a two-player coalition cooperative scheme for BAP, which allows some processes to perturb or break a Nash equilibrium to find another one with a better social welfare. By using this cooperative scheme, we propose a new algorithm called FFC-BAPs for BAP. We present both theoretical and empirical analyses which show that this algorithm produces better quality approximate solutions than former algorithms for BAP.
A k-ranking of a graph is a labeling of the vertices with positive integers 1,2, ..., k so that every path connecting two vertices with the same label contains a vertex of larger label. An optimal ranking is one in wh...
详细信息
A k-ranking of a graph is a labeling of the vertices with positive integers 1,2, ..., k so that every path connecting two vertices with the same label contains a vertex of larger label. An optimal ranking is one in which k is minimized. Let P-n, be a path with n vertices. A greedy algorithm can be used to successively label each vertex with the smallest possible label that preserves the ranking property. We seek to show that when a greedy algorithm is used to label the vertices successively from left to right, we obtain an optimal ranking. A greedy algorithm of this type was given by Bodlaender et al. in 1998 [1] which generates an optimal k-ranking of P-n. In this paper we investigate two generalizations of rankings. We first consider bounded (k, s)-rankings in which the number of times a label can be used is bounded by a predetermined integer s. We then consider k(t)-rankings where any path connecting two vertices with the same label contains t vertices with larger labels. We show for both generalizations that when G is a path, the analogous greedy algorithms generate optimal k-rankings. We then proceed to quantify the minimum number of labels that can be used in these rankings. We define the bounded rank number (r,s)(G) to be the smallest number of labels that can be used in a (k, s)-ranking and show for n 2, (r,s)(P-n) = [ ((n (2 1))/s)] + i where i = [log(2)(s)] + 1. We define the k(t)-rank number, (t)(r)(G) to be the smallest number of labels that can be used in a k(t)-ranking. We present a recursive formula that gives the k(t)-rank numbers for paths, showing 1;.(P-j) n for all a(n-1) < j <= a(n) where {a(n)) is defined as follows: a(l) = 1 and a(n) = a(n) = [((t + 1)/t)a(n-1)] + 1. (C) 2010 Elsevier B.V. All rights reserved.
This paper studies heuristics for the bandwidth reduction of large-scale matrices in serial computations. Bandwidth optimization is a demanding subject for a large number of scientific and engineering applications. A ...
详细信息
This paper studies heuristics for the bandwidth reduction of large-scale matrices in serial computations. Bandwidth optimization is a demanding subject for a large number of scientific and engineering applications. A heuristic for bandwidth reduction labels the rows and columns of a given sparse matrix. The algorithm arranges entries with a nonzero coefficient as close to the main diagonal as possible. This paper modifies an ant colony hyper-heuristic approach to generate expert-level heuristics for bandwidth reduction combined with a Hill-Climbing strategy when applied to matrices arising from specific application areas. Specifically, this paper uses low-cost state-of-the-art heuristics for bandwidth reduction in tandem with a Hill-Climbing procedure. The results yielded on a wide-ranging set of standard benchmark matrices showed that the proposed strategy outperformed low-cost state-of-the-art heuristics for bandwidth reduction when applied to matrices with symmetric sparsity patterns.
Given a set of sensors, the strong minimum energy topology (SMET) problem is to assign transmit power to each sensor such that the sum of the transmit powers of all the sensors is minimum subject to the constraint tha...
详细信息
Given a set of sensors, the strong minimum energy topology (SMET) problem is to assign transmit power to each sensor such that the sum of the transmit powers of all the sensors is minimum subject to the constraint that the resulting topology containing only bidirectional links is strongly connected. This problem is known to be NP-hard. However, most of the wireless sensor networks are hierarchical in nature, where shorter path lengths are preferred for communication between any two nodes. Given a set of sensors and a specified sensor, say , the strong minimum energy -hop rooted topology problem (h-SMERT) is to assign transmit power to each sensor such that the sum of the transmit powers of all the sensors is minimum subject to the constraints that the resulting topology containing only bidirectional links is strongly connected and the length of the path from to any other node is at most . We prove that the h-SMERT problem is NP-hard. We also prove that h-SMERT problem is APX-hard. We then show that h-SMERT problem is not approximable within a factor of 1/2 (1 - epsilon) unless NP subset of D T I M E (n(log log n)) On the positive side, we propose a -2(1 + ln n)-approximation algorithm for the h-SMERT problem. We also study two special cases of the h-SMERT problem, namely, the -rest-h-SMERT problem and the -int-h-SMERT problem. We propose a -approximation algorithm for the -rest-h-SMERT problem. The -int-h-SMERT problem is NP-hard for arbitrary . However, for fixed constant , we propose a -approximation algorithm for the -int-h-SMERT problem and obtain a polynomial time optimal algorithm for the -int-h-SMERT problem for k = 2.
Goal recognisers attempt to infer an agent's intentions from a sequence of observed actions. This is an important component of intelligent systems that aim to assist or thwart actors;however, there are many challe...
详细信息
Goal recognisers attempt to infer an agent's intentions from a sequence of observed actions. This is an important component of intelligent systems that aim to assist or thwart actors;however, there are many challenges to overcome. For example, the initial state of the environment could be partially unknown, and agents can act suboptimally and observations could be missing. Approaches that adapt classical planning techniques to goal recognition have previously been proposed, but, generally, they assume the initial world state is accurately defined. In this paper, a state is inaccurate if any fluent's value is unknown or incorrect. Our aim is to develop a goal recognition approach that is as accurate as the current state-of-the-art algorithms and whose accuracy does not deteriorate when the initial state is inaccurately defined. To cope with this complication, we propose solving goal recognition problems by means of an Action graph. An Action graph models the dependencies, i.e. order constraints, between all actions rather than just actions within a plan. Leaf nodes correspond to actions and are connected to their dependencies via operator nodes. After generating an Action graph, the graph's nodes are labelled with their distance from each hypothesis goal. This distance is based on the number and type of nodes traversed to reach the node in question from an action node that results in the goal state being reached. For each observation, the goal probabilities are then updated based on either the distance the observed action's node is from each goal or the change in distance. Our experimental results, for 15 different domains, demonstrate that our approach is robust to inaccuracies within the defined initial state.
Parallel algorithms for the problem of finding the connected components of a simple undirected graph are examined. These algorithms can be divided into 3 classes: 1. those that generally require a shared memory sing...
详细信息
Parallel algorithms for the problem of finding the connected components of a simple undirected graph are examined. These algorithms can be divided into 3 classes: 1. those that generally require a shared memory single instruction streams, multiple data streams (SIMD) model permitting read conflicts on the same memory location, 2. parallelizations of the algorithms operating on matrices, generally using SIMD processors with local memory connected by a regular network, and 3. those that use processors arranged in a binary tree. A lighthouse algorithm is described that has no loss in efficiency and can be used on a shared memory SIMD model. Read conflicts are permitted on the model, but simultaneous write operations or simultaneous write and read operations are not. In the lighthouse algorithm, each processor cyclically reads all of its neighbors' labels and compares them with its own label. The analysis indicates that the lighthouse algorithm efficiently determines the connected components in a graph.
For a connected graph, it is known that there exists a partition of the vertex set into two dominating sets of the graph. However, for a digraph, there does not always exist such partition of the vertex set. We consid...
详细信息
For a connected graph, it is known that there exists a partition of the vertex set into two dominating sets of the graph. However, for a digraph, there does not always exist such partition of the vertex set. We consider the problem of determining whether there is a partition of the vertex set into in- and out-dominating sets of the digraph. In this paper, we obtain the following results: (1) The decision problem is NP-complete even if a given digraph is acyclic, and (2) for an oriented tree, there is a polynomial time algorithm for deciding the existence of such partition. (C) 2020 Elsevier B.V. All rights reserved.
Given a directed graph G = (V, A) with a capacity function c : A --> R+, two demand functions d(-), d(+) : V --> R+, and a cost function w : V --> R+, we consider the problem of computing a minimum-cost set S...
详细信息
Given a directed graph G = (V, A) with a capacity function c : A --> R+, two demand functions d(-), d(+) : V --> R+, and a cost function w : V --> R+, we consider the problem of computing a minimum-cost set S subset of or equal to V such that, for each vertex v is an element of V - S, the arc-connectivity from S to v is at least d(-)(v) and the arc-connectivity from v to S is at least d(+)(v). We present a polynomial time algorithm for the problem where d(-) and d(+) are uniformly fixed and w is uniform. Furthermore, we show that the problem is NP-hard, even if either the cost function or the demand function is uniform.
An L(2,1)-labeling of a graph G is an assignment f from the vertex set V(G) to the set of nonnegative integers such that |f(x)-f(y)|a parts per thousand yen2 if x and y are adjacent and |f(x)-f(y)|a parts per thousand...
详细信息
An L(2,1)-labeling of a graph G is an assignment f from the vertex set V(G) to the set of nonnegative integers such that |f(x)-f(y)|a parts per thousand yen2 if x and y are adjacent and |f(x)-f(y)|a parts per thousand yen1 if x and y are at distance 2, for all x and y in V(G). A k-L(2,1)-labeling is an L(2,1)-labeling f:V(G)->{0,aEuro broken vertical bar,k}, and the L(2,1)-labeling problem asks the minimum k, which we denote by lambda(G), among all possible assignments. It is known that this problem is NP-hard even for graphs of treewidth 2, and tree is one of very few classes for which the problem is polynomially solvable. The running time of the best known algorithm for trees had been O(Delta (4.5) n) for more than a decade, and an O(min{n (1.75),Delta (1.5) n})-time algorithm has appeared recently, where Delta and n are the maximum degree and the number of vertices of an input tree, however, it has been open if it is solvable in linear time. In this paper, we finally settle this problem by establishing a linear time algorithm for L(2,1)-labeling of trees. Furthermore, we show that it can be extended to a linear time algorithm for L(p,1)-labeling with a constant p.
Consider a puzzle consisting of n tokens on an n-vertex graph, where each token has a distinct starting vertex and a distinct target vertex it wants to reach, and the only allowed transformation is to swap the tokens ...
详细信息
Consider a puzzle consisting of n tokens on an n-vertex graph, where each token has a distinct starting vertex and a distinct target vertex it wants to reach, and the only allowed transformation is to swap the tokens on adjacent vertices. We prove that every such puzzle is solvable in O(n(2)) token swaps, and thus focus on the problem of minimizing the number of token swaps to reach the target token placement. We give a polynomial-time 2-approximation algorithm for trees, and using this, obtain a polynomial-time 2 alpha-approximation algorithm for graphs whose tree a-spanners can be computed in polynomial time. Finally, we show that the problem can be solved exactly in polynomial time on complete bipartite graphs. (C) 2015 Elsevier B.V. All rights reserved.
暂无评论