We study the problem of computing an energy-efficient data delivery scheme in wireless sensor networks that leverages the knowledge of a set of trajectories of mobile sinks in the network to route data from the sensor...
详细信息
ISBN:
(纸本)9781424493289
We study the problem of computing an energy-efficient data delivery scheme in wireless sensor networks that leverages the knowledge of a set of trajectories of mobile sinks in the network to route data from the sensors to the mobile sinks. Sensors collect data from the environment and instead of directly sending them to the mobile sinks (henceforth simply "sinks"), they route data to a number of selected nodes (we call them relay or stashing nodes) in the network. These stashing nodes lie on the trajectories of the sinks, and relay the received data directly to the sinks on behalf of the sensors. Assuming a set of p different applications being executed on each sensor node, we consider the following problem: Given a set of p trajectories T(1), T(2), ..., T(p) corresponding to p sinks, where sink i is dedicated to collect i-th application data, node u selects at least k stashing nodes from T(i) such that it can forward at least k copies of its i-application data to them. The goal of u is to minimize the total routing cost to send all its p application data to the corresponding stashing nodes of p trajectories. We use the expected number of transmissions on a link as the routing cost of the link and the routing cost for a path is the sum of all the link costs of that path. We wish to minimize the sum of the total routing costs of all the nodes. We call this the Minimum Cost Stashing problem and formulate this as a primal-dual problem. We present a 1/2(2f - k + 1)-approximationalgorithm using the primal-dual method for approximationalgorithms, where f is the maximum size of a trajectory.
In this paper, we consider the non-negative submodular function minimization problem with covering type linear constraints. Assume that there exist m linear constraints, and we denote by the number of non-zero coeffic...
详细信息
In this paper, we consider the non-negative submodular function minimization problem with covering type linear constraints. Assume that there exist m linear constraints, and we denote by the number of non-zero coefficients in the ith constraints. Furthermore, we assume that . For this problem, Koufogiannakis and Young proposed a polynomial-time -approximationalgorithm. In this paper, we propose a new polynomial-time primal-dual approximation algorithm based on the approximationalgorithm of Takazawa and Mizuno for the covering integer program with -variables and the approximationalgorithm of Iwata and Nagano for the submodular function minimization problem with set covering constraints. The approximation ratio of our algorithm is , where is the maximum size of a connected component of the input submodular function.
A matching in a graph is induced if no two of its edges are joined by an edge, and finding a large induced matching is a very hard problem. Lin et al. (2018) provide an approximationalgorithm with ratio Delta for the...
详细信息
A matching in a graph is induced if no two of its edges are joined by an edge, and finding a large induced matching is a very hard problem. Lin et al. (2018) provide an approximationalgorithm with ratio Delta for the weighted version of the induced matching problem on graphs of maximum degree Delta. Their approach is based on an integer linear programming formulation whose integrality gap is at least Delta - 1, that is, their approach offers only little room for improvement in the weighted case. For the unweighted case though, we conjecture that the integrality gap is at most 5/8 Delta + O(1), and that also the approximation ratio can be improved at least to this value. We provide primal-dual approximation algorithms with ratios (1 - epsilon)Delta + 1/2 for general Delta with epsilon approximate to 0.02005, and 7/3 for Delta = 3. Furthermore, we prove a best-possible bound on the fractional induced matching number in terms of the order and the maximum degree. (C) 2020 Elsevier B.V. All rights reserved.
暂无评论