Considerable attention has been paid to sweep coverage in Wireless Sensor Networks (WSNs) for the past few years. In sweep coverage, mobile sensor nodes are scheduled to visit Points of Interests (POIs) periodically. ...
详细信息
Considerable attention has been paid to sweep coverage in Wireless Sensor Networks (WSNs) for the past few years. In sweep coverage, mobile sensor nodes are scheduled to visit Points of Interests (POIs) periodically. Due to the limited energy of mobile sensors, energy consumption poses an important challenge in sweep coverage. In this paper, we extend the Energy Restricted Sweep Coverage to the General Energy Restricted Sweep Coverage (GERSC) by assuming the unit energy consumption of mobile sensors varies in different road sections. The goal of GERSC is also to minimize the required number of mobile sensors in sweep coverage under the energy constraint. In GERSC, the approximation ratio of the state-of-the-art algorithm named ERSweepCoverage is no longer guaranteed. Therefore, we devise a constant-factor approximation algorithm named IERSC for GERSC. The approximation ratio of IERSC is beta[3 alpha/min(theta,1-theta) + 1]. theta is the predefined parameter of IERSC ranging from 0 to 1. With theta being 12, IERSC has the best approximation ratio of (6 alpha + 1)beta. Finally, the promising experimental results demonstrate the effectiveness and efficiency of the proposed algorithm. (C) 2021 Elsevier B.V. All rights reserved.
The hitting set problem is a generalization of the vertex cover problem to hypergraphs. Xu et al. (Theor Comput Sci 630:117-125, 2016) presented a primal-dual algorithm for the submodular vertex cover problem with lin...
详细信息
The hitting set problem is a generalization of the vertex cover problem to hypergraphs. Xu et al. (Theor Comput Sci 630:117-125, 2016) presented a primal-dual algorithm for the submodular vertex cover problem with linear/submodular penalties. Motivated by their work, we study the submodular hitting set problem with linear penalties (SHSLP). The goal of the SHSLP is to select a vertex subset in the hypergraph to cover some hyperedges and penalize the uncovered ones such that the total cost of covering and penalty is minimized. Based on the primal-dual scheme, we obtain ak-approximation algorithm for the SHSLP, wherekis the maximum number of vertices in all hyperedges.
One ultimate goal of wireless sensor networks is to collect the sensed data from a set of sensors and transmit them to some sink node via a data gathering tree. In this work, we are interested in data aggregation, whe...
详细信息
One ultimate goal of wireless sensor networks is to collect the sensed data from a set of sensors and transmit them to some sink node via a data gathering tree. In this work, we are interested in data aggregation, where the sink node wants to know the value for a certain function of all sensed data, such as minimum, maximum, average, and summation. Given a data aggregation tree, sensors receive messages from children periodically, merge them with its own packet, and send the new packet to its parent. The problem of finding an aggregation tree with the maximum lifetime has been proved to be NP-hard and can be generalized to finding a spanning tree with the minimum maximum vertex load, where the load of a vertex is a nondecreasing function of its degree in the tree. Although there is a rich body of research in those problems, they either fail to meet a theoretical bound or need high running time. In this paper, we develop a novel algorithm with provable performance bounds for the generalized problem. We show that the running time of our algorithm is in the order of O(mn alpha)(m, n)), where m is the number of edges, n is the number of sensors, and alpha is the inverse Ackerman function. Though our work is motivated by applications in sensor networks, the proposed algorithm is general enough to handle a wide range of degree-oriented spanning tree problems, including bounded degree spanning tree problem and minimum degree spanning tree problem. When applied to these problems, it incurs a lower computational cost in comparison to existing methods. Simulation results validate our theoretical analysis.
A space-efficient approximation algorithm for the grammar-based compression problem, which requests for a given string to find a smallest context-free grammar deriving the string, is presented. For the input length it...
详细信息
A space-efficient approximation algorithm for the grammar-based compression problem, which requests for a given string to find a smallest context-free grammar deriving the string, is presented. For the input length it and an optimum CFG size g, the algorithm consumes only O(g log g) space and O(n log*n) time to achieve O((log*n) log n) approximation ratio to the optimum compression, where log*n is the maximum number of logarithms satisfying log log...log n > 1. This ratio is thus regarded to almost O(log n), which is the currently best approximation ratio. While g depends on the string, it is known that g = Omega(log n) and g = O(n/log(k)n) for strings from k-letter alphabet [12].
In this paper, we give an algorithm that finds an e-approximate solution to a mixed integer quadratic programming (MIQP) problem. The algorithm runs in polynomial time if the rank of the quadratic function and the num...
详细信息
In this paper, we give an algorithm that finds an e-approximate solution to a mixed integer quadratic programming (MIQP) problem. The algorithm runs in polynomial time if the rank of the quadratic function and the number of integer variables are fixed. The running time of the algorithm is expected unless P=NP. In order to design this algorithm we introduce the novel concepts of spherical form MIQP and of aligned vectors, and we provide a number of results of independent interest. In particular, we give a strongly polynomial algorithm to find a symmetric decomposition of a matrix, and show a related result on simultaneous diagonalization of matrices.
In packing steel products of coils into cassettes, we need to consider both the width and weight capacity of cassettes. Each coil has weight in (0, 1/3] and width in (1/6, 1/3] when scaling both the weight and width c...
详细信息
In packing steel products of coils into cassettes, we need to consider both the width and weight capacity of cassettes. Each coil has weight in (0, 1/3] and width in (1/6, 1/3] when scaling both the weight and width capacities to 1. With the objective of minimizing the number of cassettes to pack the coils, the problem is modeled by two-dimensional vector packing. To efficiently pack the coils having sizes specified by the ranges, we develop a 4/3-approximation algorithm.
We consider the scheduling problem of n independent jobs on m identical parallel processors in order to minimize makespan, the completion time of the last job. We propose a new approximation algorithm that iteratively...
详细信息
We consider the scheduling problem of n independent jobs on m identical parallel processors in order to minimize makespan, the completion time of the last job. We propose a new approximation algorithm that iteratively combines partial solutions to the problem. The worst-case performance ratio of the algorithm is (z+ 1)/(z) - (1)/(mz), where z is the number of initial partial solutions that are obtained by partitioning the set of jobs into z families of subsets which satisfy suitable properties. The computational behavior of our worst-case performance ratio provided encouraging results on three families of instances taken from the literature.
The S-connectivity lambda(S)(G)(u,nu) of (u,nu)in a graph G is the maximum number of uv-paths that no two of them have an edge or a node in S - {u, nu} in common. The corresponding Connectivity Augmentation (CA) probl...
详细信息
The S-connectivity lambda(S)(G)(u,nu) of (u,nu)in a graph G is the maximum number of uv-paths that no two of them have an edge or a node in S - {u, nu} in common. The corresponding Connectivity Augmentation (CA) problem is: given a graph G(0) = (V, E-0), S subset of V, and requirements r(u, nu) on V x V, find a minimum size set F of new edges (any edge is allowed) so that lambda(S)(G0+F)(u, nu) >= r(u, nu) for all u,nu is an element of V. Extensively studied particular choices of S are the edge-CA (when S = phi) and the node-CA (when S = V). A. Frank gave a polynomial algorithm for undirected edge-CA and observed that the directed case even with rooted {0, 1}-requirements is at least as hard as the Set-Cover problem (in rooted requirements there is s is an element of V - S so that if r(u, v) > 0 then: u = s for directed graphs, and u = s or nu = s for undirected graphs). Both directed and undirected node-CA have approximation threshold Omega(2log(1-epsilon) n). The only polylogarithmic approximation ratio known for CA was for rooted requirements-O(logn . logr(max)) = O(log(2)n), where r(max) = max(u,nu is an element of V) r(u, nu). No nontrivial approximation algorithms were known fordirected CA even forr(u, nu) is an element of {0, 1}, nor for undirected CA with S arbitrary. We give an approximation algorithm for the general case that matches the known approximation thresholds. For both directed and undirected CA with arbitrary requirements our approximation ratio is: O(logn) for S not equal V arbitrary, and O(r(max) . log n) for S = V. (c) 2007 Published by Elsevier Inc.
We present the first approximation algorithm for a two depot, heterogeneous traveling salesman problem with an approximation ratio of 3 when the costs are symmetric and satisfy the triangle inequality.
We present the first approximation algorithm for a two depot, heterogeneous traveling salesman problem with an approximation ratio of 3 when the costs are symmetric and satisfy the triangle inequality.
作者：
Yang, HYe, YYZhang, JWStanford Univ
Sch Engn Dept Management Sci & Engn Stanford CA 94305 USA Tsinghua Univ
Dept Automat State Key Lab Intelligent Technol & Syst Beijing 100084 Peoples R China Stanford Univ
Sch Engn Dept Management Sci & Engn Stanford CA 94305 USA
We consider the problem of scheduling n independent jobs on two identical parallel machines, with a limit on the number of jobs that can be assigned to each single machine, so as to minimize the total weighted complet...
详细信息
We consider the problem of scheduling n independent jobs on two identical parallel machines, with a limit on the number of jobs that can be assigned to each single machine, so as to minimize the total weighted completion time of the jobs. We study a semidefinite programming-based approximation algorithm for solving this problem and prove that the algorithm has a worst case ratio at most 1.1626. (C) 2002 Elsevier B.V. All rights reserved.
暂无评论