Subscribe to the gold package and get unlimited access to Shamra Academy
Register a new userOn New Approaches of Maximum Weighted Target Coverage and Sensor Connectivity: Hardness and Approximation
61
0
0.0
(
0
)
Added by
Tu Nguyen
Publication date
2018
fields
Informatics Engineering
and research's language is
English
Ask ChatGPT about the research
No Arabic abstract
In mobile wireless sensor networks (MWSNs), each sensor has the ability not only to sense and transmit data but also to move to some specific location. Because the movement of sensors consumes much more power than that in sensing and communication, the problem of scheduling mobile sensors to cover all targets and maintain network connectivity such that the total movement distance of mobile sensors is minimized has received a great deal of attention. However, in reality, due to a limited budget or numerous targets, mobile sensors may be not enough to cover all targets or form a connected network. Therefore, targets must be weighted by their importance. The more important a target, the higher the weight of the target. A more general problem for target coverage and network connectivity, termed the Maximum Weighted Target Coverage and Sensor Connectivity with Limited Mobile Sensors (MWTCSCLMS) problem, is studied. In this paper, an approximation algorithm, termed the weighted-maximum-coverage-based algorithm (WMCBA), is proposed for the subproblem of the MWTCSCLMS problem. Based on the WMCBA, the Steiner-tree-based algorithm (STBA) is proposed for the MWTCSCLMS problem. Simulation results demonstrate that the STBA provides better performance than the other methods.
rate research
Read More
The minimum linear ordering problem (MLOP) seeks to minimize an aggregated cost $f(cdot)$ due to an ordering $sigma$ of the items (say $[n]$), i.e., $min_{sigma} sum_{iin [n]} f(E_{i,sigma})$, where $E_{i,sigma}$ is the set of items that are mapped by $sigma$ to indices at most $i$. This problem has been studied in the literature for various special cases of the cost function $f$, and in a general setting for a submodular or supermodular cost $f$ [ITT2012]. Though MLOP was known to be NP-hard for general submodular functions, it was unknown whether the special case of graphic matroid MLOP (with $f$ being the matroid rank function of a graph) was polynomial-time solvable. Following this motivation, we explore related classes of linear ordering problems, including symmetric submodular MLOP, minimum latency vertex cover, and minimum sum vertex cover. We show that the most special cases of our problem, graphic matroid MLOP and minimum latency vertex cover, are both NP-hard. We further expand the toolkit for approximating MLOP variants: using the theory of principal partitions, we show a $2-frac{1+ell_{f}}{1+|E|}$ approximation to monotone submodular MLOP, where $ell_{f}=frac{f(E)}{max_{xin E}f({x})}$ satisfies $1 leq ell_f leq |E|$. Thus our result improves upon the best known bound of $2-frac{2}{1+|E|}$ by Iwata, Tetali, and Tripathi [ITT2012]. This leads to a $2-frac{1+r(E)}{1+|E|}$ approximation for the matroid MLOP, corresponding to the case when $r$ is the rank function of a given matroid. Finally, we show that MLVC can be $4/3$ approximated, matching the integrality gap of its vanilla LP relaxation.
Bribery in election (or computational social choice in general) is an important problem that has received a considerable amount of attention. In the classic bribery problem, the briber (or attacker) bribes some voters in attempting to make the bribers designated candidate win an election. In this paper, we introduce a novel variant of the bribery problem, Election with Bribed Voter Uncertainty or BVU for short, accommodating the uncertainty that the vote of a bribed voter may or may not be counted. This uncertainty occurs either because a bribed voter may not cast its vote in fear of being caught, or because a bribed voter is indeed caught and therefore its vote is discarded. As a first step towards ultimately understanding and addressing this important problem, we show that it does not admit any multiplicative $O(1)$-approximation algorithm modulo standard complexity assumptions. We further show that there is an approximation algorithm that returns a solution with an additive-$epsilon$ error in FPT time for any fixed $epsilon$.
We study the online maximum coverage problem on a line, in which, given an online sequence of sub-intervals (which may intersect among each other) of a target large interval and an integer $k$, we aim to select at most $k$ of the sub-intervals such that the total covered length of the target interval is maximized. The decision to accept or reject each sub-interval is made immediately and irrevocably (no preemption) right at the release timestamp of the sub-interval. We comprehensively study different settings of this problem regarding both the length of a released sub-interval and the total number of released sub-intervals. We first present lower bounds on the competitive ratio for the settings concerned in this paper, respectively. For the offline problem where the sequence of all the released sub-intervals is known in advance to the decision-maker, we propose a dynamic-programming-based optimal approach as the benchmark. For the online problem, we first propose a single-threshold-based deterministic algorithm SOA by adding a sub-interval if the added length exceeds a certain threshold, achieving competitive ratios close to the lower bounds, respectively. Then, we extend to a double-thresholds-based algorithm DOA, by using the first threshold for exploration and the second threshold (larger than the first one) for exploitation. With the two thresholds solved by our proposed program, we show that DOA improves SOA in the worst-case performance. Moreover, we prove that a deterministic algorithm that accepts sub-intervals by multi non-increasing thresholds cannot outperform even SOA.
In this paper, we first remodel the line coverage as a 1D discrete problem with co-linear targets. Then, an order-based greedy algorithm, called OGA, is proposed to solve the problem optimally. It will be shown that the existing order in the 1D modeling, and especially the resulted Markov property of the selected sensors can help design greedy algorithms such as OGA. These algorithms demonstrate optimal/efficient performance and have lower complexity compared to the state-of-the-art. Furthermore, it is demonstrated that the conventional continuous line coverage problem can be converted to an equivalent discrete problem and solved optimally by OGA. Next, we formulate the well-known weak barrier coverage problem as an instance of the continuous line coverage problem (i.e. a 1D problem) as opposed to the conventional 2D graph-based models. We demonstrate that the equivalent discrete version of this problem can be solved optimally and faster than the state-of-the-art methods using an extended version of OGA, called K-OGA. Moreover, an efficient local algorithm, called LOGM, is proposed to mend barrier gaps due to sensor failure. In the case of m gaps, LOGM is proved to select at most 2m-1 sensors more than the optimal while being local and implementable in distributed fashion. We demonstrate the optimal/efficient performance of the proposed algorithms via extensive simulations.
The tree augmentation problem (TAP) is a fundamental network design problem, in which the input is a graph $G$ and a spanning tree $T$ for it, and the goal is to augment $T$ with a minimum set of edges $Aug$ from $G$, such that $T cup Aug$ is 2-edge-connected. TAP has been widely studied in the sequential setting. The best known approximation ratio of 2 for the weighted case dates back to the work of Frederickson and J{a}J{a}, SICOMP 1981. Recently, a 3/2-approximation was given for unweighted TAP by Kortsarz and Nutov, TALG 2016. Recent breakthroughs give an approximation of 1.458 for unweighted TAP [Grandoni et al., STOC 2018], and approximations better than 2 for bounded weights [Adjiashvili, SODA 2017; Fiorini et al., SODA 2018]. In this paper, we provide the first fast distributed approximations for TAP. We present a distributed $2$-approximation for weighted TAP which completes in $O(h)$ rounds, where $h$ is the height of $T$. When $h$ is large, we show a much faster 4-approximation algorithm for the unweighted case, completing in $O(D+sqrt{n}log^*{n})$ rounds, where $n$ is the number of vertices and $D$ is the diameter of $G$. Immediate consequences of our results are an $O(D)$-round 2-approximation algorithm for the minimum size 2-edge-connected spanning subgraph, which significantly improves upon the running time of previous approximation algorithms, and an $O(h_{MST}+sqrt{n}log^{*}{n})$-round 3-approximation algorithm for the weighted case, where $h_{MST}$ is the height of the MST of the graph. Additional applications are algorithms for verifying 2-edge-connectivity and for augmenting the connectivity of any connected spanning subgraph to 2. Finally, we complement our study with proving lower bounds for distributed approximations of TAP.
Log in to be able to interact and post comments
comments
Fetching comments
Sign in to be able to follow your search criteria
