The benefits of using a mobile base station to prolong sensor network lifetime have been well recognized. However, due to the complexity of the problem (time-dependent network topology and traffic routing), theoretica...
详细信息
The benefits of using a mobile base station to prolong sensor network lifetime have been well recognized. However, due to the complexity of the problem (time-dependent network topology and traffic routing), theoretical performance limits and provably optimal algorithms remain difficult to develop. This paper fills this important gap by contributing some theoretical results regarding the optimal movement of a mobile base station. Our main result hinges upon two key intermediate results. In the first result, we show that a time-dependent joint base station movement and flow routing problem can be transformed into a location-dependent problem. In the second result, we show that, for (1 - epsilon) optimality, the infinite possible locations for base station movement can be reduced to a finite set of locations via several constructive steps [i.e., discretization of energy cost through a geometric sequence, division of a disk into a finite number of subareas, and representation of each subarea with a fictitious cost point (FCP)]. Subsequently, for each FCP, we can obtain the optimal sojourn time for the base station (as well as the corresponding location-dependent flow routing) via a simple linear program. We prove that the proposed solution can guarantee the achieved network lifetime is at least (1 - epsilon) of the maximum (unknown) network lifetime, where epsilon can be made arbitrarily small depending on the required precision.
This paper addresses the problem of scheduling non-preemptive moldable tasks to minimize the stretch of the tasks in an online non-clairvoyant setting. To the best of the authors knowledge, this problem has never been...
详细信息
This paper addresses the problem of scheduling non-preemptive moldable tasks to minimize the stretch of the tasks in an online non-clairvoyant setting. To the best of the authors knowledge, this problem has never been studied before. To tackle this problem, first the sequential subproblem is studied through the lens of the approximation theory. An algorithm, called DASEDF, is proposed and, through simulations, it is shown to outperform the first-come, first-served scheme. Furthermore, it is observed that machine availability is the key to getting good stretch values. Then, the moldable task scheduling problem is considered, and, by leveraging the results from the sequential case, another algorithm, DBOS, is proposed to optimize the stretch while scheduling moldable tasks. This work is motivated by a task scheduling problem in the context of parallel short sequence mapping which has important applications in biology and genetics. The proposed DBOS algorithm is evaluated both on synthetic data sets that represent short sequence mapping requests and on data sets generated using log files of real production clusters. The results show that the DBOS algorithm significantly outperforms the two state-of-the-art task scheduling algorithms on stretch optimization. (C) 2012 Elsevier Inc. All rights reserved.
In this article we study graphs with inductive neighborhood properties. Let P be a graph property, a graph G = (V, E) with n vertices is said to have an inductive neighborhood property with respect to P if there is an...
详细信息
In this article we study graphs with inductive neighborhood properties. Let P be a graph property, a graph G = (V, E) with n vertices is said to have an inductive neighborhood property with respect to P if there is an ordering of vertices v(1), ... , v(n) such that the property P holds on the induced subgraph G[N(v(i)) boolean AND V-i], where N(v(i)) is the neighborhood of v(i) and V-i = {v(i), ... , v(n)}. It turns out that if we take P as a graph with maximum independent set size no greater than k, then this definition gives a natural generalization of both chordal graphs and (k + 1)-claw-free graphs. We refer to such graphs as inductive k-independent graphs. We study properties of such families of graphs, and we show that several natural classes of graphs are inductive k-independent for small k. In particular, any intersection graph of translates of a convex object in a two dimensional plane is an inductive 3-independent graph;furthermore, any planar graph is an inductive 3-independent graph. For any fixed constant k, we develop simple, polynomial time approximation algorithms for inductive k-independent graphs with respect to several well-studied NP-complete problems. Our generalized formulation unifies and extends several previously known results.
The minimum weighted dominating set (MWDS) problem is one of the classic NP-hard optimization problems in graph theory with applications in many fields such as wireless communication networks. MWDS in general graphs h...
详细信息
The minimum weighted dominating set (MWDS) problem is one of the classic NP-hard optimization problems in graph theory with applications in many fields such as wireless communication networks. MWDS in general graphs has been showed not to have polynomial-time constant-approximation if . Recently, several polynomial-time constant-approximation SCHEMES have been designed for MWDS in unit disk graphs. In this paper, using the local neighborhood-based scheme technique, we present a PTAS for MWDS in polynomial growth bounded graphs with bounded degree constraint.
We devise an approximate feasibility test for multiprocessor real-time scheduling in the sporadic task model. We give an algorithm that, given a task system and epsilon > 0, correctly decides either that the task s...
详细信息
We devise an approximate feasibility test for multiprocessor real-time scheduling in the sporadic task model. We give an algorithm that, given a task system and epsilon > 0, correctly decides either that the task system can be scheduled using the Earliest Deadline First algorithm on m speed-(2-1/m+epsilon) machines, or that the system is not schedulable by any algorithm on m unit speed machines. This speedup bound is known to be the best possible for EDF. The running time of the algorithm is polynomial in the size of the task system and 1/epsilon. We also provide a generalized tight bound that trades off speed with additional machines.
In wireless sensor network, a connected dominating set (CDS) can be used as a virtual backbone for efficient routing. Constructing a minimal CDS (MCDS) is good for packet routing and energy efficiency, but is an NP-ha...
详细信息
In wireless sensor network, a connected dominating set (CDS) can be used as a virtual backbone for efficient routing. Constructing a minimal CDS (MCDS) is good for packet routing and energy efficiency, but is an NP-hard problem. In this article, an efficient approximation MCDS construction algorithm E-MCDS (energy efficient MCDS construction algorithm) is proposed which explicitly takes energy consumption into account. E-MCDS contains two stages: the CDS construction stage and the pruning stage. The constructed CDS is approximately composed of two independent sets (IS). The performance ratio of E-MCDS is analysed in both unit disk graph and disk graphs with bidirectional links, being 9.33opt and 17.33n(k)opt, respectively. The message complexity of E-MCDS is O(n). The simulation results have shown that E-MCDS performs well both in terms of the size of CDS constructed and the energy efficiency.
This paper considers the scheduling problem of parallel batch processing machines with non-identical job sizes. The jobs are processed in batches and the machines have the same capacity. The models of minimizing makes...
详细信息
This paper considers the scheduling problem of parallel batch processing machines with non-identical job sizes. The jobs are processed in batches and the machines have the same capacity. The models of minimizing makespan and total completion time are given using mixed integer programming method and the computational complexity is analyzed. The bound on the number of feasible solutions is given and the properties of the optimal solutions are presented. Then a polynomial time algorithm is proposed and the worst case ratios for minimizing total completion time and makespan is proved to be 2 and (8/3-2/3 m) respectively. To test the proposed algorithm, we generate different levels of random instances. The computational results demonstrate the effectiveness of the algorithm for minimizing the two objectives. (C) 2011 Elsevier Inc. All rights reserved.
Consider the NP-hard problem of, given a simple graph G, to find a series-parallel subgraph of G with the maximum number of edges. The algorithm that, given a connected graph G, outputs a spanning tree of G, is a 1/2-...
详细信息
Consider the NP-hard problem of, given a simple graph G, to find a series-parallel subgraph of G with the maximum number of edges. The algorithm that, given a connected graph G, outputs a spanning tree of G, is a 1/2-approximation. Indeed, if n is the number of vertices in G, any spanning tree in G has n-1 edges and any series-parallel graph on n vertices has at most 2n-3 edges. We present a 7/12 -approximation for this problem and results showing the limits of our approach.
The sell or hold problem (SHP) is to sell k out of n indivisible assets over two stages, with known first-stage prices and random second-stage prices, to maximize the total expected revenue. We show that SHP is NP-har...
详细信息
The sell or hold problem (SHP) is to sell k out of n indivisible assets over two stages, with known first-stage prices and random second-stage prices, to maximize the total expected revenue. We show that SHP is NP-hard when the second-stage prices are realized as a finite set of scenarios. We show that SUP is polynomially solvable when the number of scenarios in the second stage is constant. A max{1/2, k /n} - approximation algorithm is presented for the scenario-based SHP. (C) 2011 Elsevier B.V. All rights reserved.
We study the problem of multicast routing and wavelength assignment (MC-RWA) in multi-hop optical WDM networks with respect to several target functions. Specially, we first study the MC-RWA problem under the target of...
详细信息
We study the problem of multicast routing and wavelength assignment (MC-RWA) in multi-hop optical WDM networks with respect to several target functions. Specially, we first study the MC-RWA problem under the target of minimize maximum hops, an efficient MC-RWA algorithm was proposed for that case. But for the objective of minimizing the total number of wavelength conversions, problem turns out to be NP-hard, we proposed a new approximation MC-RWA algorithm based on group Steiner tree. At last, combining the two objectives, a bi-factor approximation algorithm was introduced to minimize the both targets in the system simultaneously.
暂无评论