Trade-offs between energy and performance are important for energy-aware scheduling. Recently, a novel model, called energy-aware profit maximizing scheduling problem (EAPM), which combines energy and makespan into th...
详细信息
Trade-offs between energy and performance are important for energy-aware scheduling. Recently, a novel model, called energy-aware profit maximizing scheduling problem (EAPM), which combines energy and makespan into the objective of maximizing the profit per unit of time has been proposed. The user pay a given price to have a bag-of-tasks processed and the objective is to maximize the profit per unit time. In this study, we design a polynomial-time algorithm for the EAPM problem. The execution time of our algorithm is polynomial in the number of task types which is an improvement over the previous algorithm, whose execution time is polynomial in the number of tasks. Moreover, we demonstrate that the approximation ratio of our algorithm is close to 2 for a special case, which may be the best result we can obtain. Experimental results show that our algorithm can produce a feasible solution with better objective value than the previous algorithm. (C) 2018 Published by Elsevier Inc.
Given a set of points on a line, a set of intervals along the line and an integer k, each point p is associated with a covering requirement cr(p), the goal of the minimum interval partial multi-cover (MinIPMC) problem...
详细信息
Given a set of points on a line, a set of intervals along the line and an integer k, each point p is associated with a covering requirement cr(p), the goal of the minimum interval partial multi-cover (MinIPMC) problem is to select the minimum number of intervals to fully cover at least k points, where a point p is fully covered if it belongs to at least cr(p) selected intervals. This paper presents a 2-approximation algorithm for the MinIPMC problem.
In Wireless Sensor Network (WSN), sensors are deployed to sense useful data from environment. To prolong the sensor network lifetime in large-scale network, mobile sinks are employed for collecting data from the senso...
详细信息
In Wireless Sensor Network (WSN), sensors are deployed to sense useful data from environment. To prolong the sensor network lifetime in large-scale network, mobile sinks are employed for collecting data from the sensors directly. The major drawback of the system is slow speed of the mobile sinks, which causes long data gathering delay from the sensors. Since, sensors have limited memory and hence it causes buffer overflow in the sensors. Therefore, to avoid buffer overflow the data must be gathered by the mobile sinks within a predefined time interval. Data gathering from mobile sensors using mobile sinks is more challenging problem than data gathering from static sensors. A set of mobile sensors are moving arbitrarily on a set of predefined paths. Our objective is to collect data periodically from all mobile sensors using minimum number of mobile sinks and subsequently the mobile sinks visit a base station (BS) for final data delivery. We show that the problem is NP-hard and two approximation algorithms are proposed. We extend the proposed algorithms, where mobile sensors can deliver their sensed data to mobile sink within their circular communication regions and present a recovery algorithm from mobile sink's failure. We analyze the performance and time complexity of the proposed algorithms. (C) 2018 Elsevier B.V. All rights reserved.
We consider a bistatic radar sensor network that consists of multiple separated radar transmitters and radar receivers, which are deployed to detect targets among a set of points of interest. Any transmitter-receiver ...
详细信息
We consider a bistatic radar sensor network that consists of multiple separated radar transmitters and radar receivers, which are deployed to detect targets among a set of points of interest. Any transmitter-receiver pair with the same frequency forms a bistatic radar. In contrast to the disk-based sensing model in a traditional sensor network, the detection probability of a bistatic radar depends on both locations of the transmitter and receiver. Given the radar transmitters' locations and illuminating frequencies, we study the problem of joint radar receiver placement and frequency selection to maximize the target detection probability. We first study the case where there is a set of candidate locations to place the radar receivers, and propose a simple algorithm with approximation ratio at least 0.63. We then consider the case where there is no constraint for radar receivers' locations, and develop an approximation algorithm which is provably close to optimal. Finally, the numerical results are presented to show the efficacy of our algorithms.
For a given graph G, the minimum weight connected-k-subgraph cover problem (MinWCkSC) is to find a minimum weight vertex subset C of G such that each connected subgraph of G on k vertices contains at least one vertex ...
详细信息
For a given graph G, the minimum weight connected-k-subgraph cover problem (MinWCkSC) is to find a minimum weight vertex subset C of G such that each connected subgraph of G on k vertices contains at least one vertex of C. Previously, Zhang et al. [37] presented a (k - 1)-approximation algorithm for MinWCkSC under the assumption that the girth of G, which is the length of a shortest cycle of G, is at least k. In this paper, we improve this result by showing that (k - 1)-approximation can be achieved when the girth requirement is relaxed from k to 2k/3. (C) 2020 Elsevier B.V. All rights reserved.
We study the problem Of MINIMIZING TOTAL LATENCY IN MACHINE SCHEDULING WITH DELIVERIES, which is defined as follows. There is a set of n jobs to be processed by a single machine at a plant, where job J(i) is associate...
详细信息
We study the problem Of MINIMIZING TOTAL LATENCY IN MACHINE SCHEDULING WITH DELIVERIES, which is defined as follows. There is a set of n jobs to be processed by a single machine at a plant, where job J(i) is associated with its processing time and a customer i located at location i to which the job is to be delivered. In addition, there is a single uncapacitated delivery vehicle available. All jobs (vehicle) are available for processing (delivery) at time 0. Our aim is to determine the sequence in which the jobs should be processed in the plant, the departure times of the vehicle from the plant, and the routing of the vehicle, so as to minimize the total latency (job delivery time). We present a 6e similar to 16.309691-approximation algorithm for the problem. (C) 2007 Elsevier B.V. All rights reserved.
The problem of efficiently monitoring the network flow is regarded as the problem to find out the minimum weighted weak vertex cover set for a given graphG=(V,E). In this paper, we give an approximation algorithm to s...
详细信息
The problem of efficiently monitoring the network flow is regarded as the problem to find out the minimum weighted weak vertex cover set for a given graphG=(V,E). In this paper, we give an approximation algorithm to solve it, which has the approximation ratio lnd+1, whered is the maximum degree of the vertex in graphG, and improve the previous work.
Keywords weak vertex cover - NP-hard - approximation algorithm
Note
This work is supported by the Ministry of Science and Technology of China (Grant No.2001CCA03000), the National Natural Science Foundation of China (Grant No.60273045), and the Shanghai Science and Technology Development Foundation (Grant No.025115032).
Steiner tree problem is a typical NP-hard problem, which has vast application background and has been an active research topic in recent years. Stochastic optimization problem is an important branch in the field of op...
详细信息
Steiner tree problem is a typical NP-hard problem, which has vast application background and has been an active research topic in recent years. Stochastic optimization problem is an important branch in the field of optimiza-tion. Compared with deterministic optimization problem, it is an optimization problem with random factors, and requires the use of tools such as probability and statistics, stochastic process and stochastic analysis. In this paper, we study a two-stage finite-scenario stochastic prize-collecting Steiner tree prob-lem, where the goal is to minimize the sum of the first stage cost, the expected second stage cost and the expected penalty cost. Our main contribution is to present a primal-dual 3-approximation algorithm for this problem.
Considering fairness has become increasingly important in recent research. This paper proposes the prize-collecting vertex cover problem with fairness constraints (FPCVC). In a prize-collecting vertex cover problem, t...
详细信息
Considering fairness has become increasingly important in recent research. This paper proposes the prize-collecting vertex cover problem with fairness constraints (FPCVC). In a prize-collecting vertex cover problem, those edges that are not covered incur penalties. By adding fairness concerns into the problem, the vertex set is divided into l groups, the goal is to find a vertex set to minimize the cost-plus-penalty value under the constraints that the profit of edges collected by each group exceeds a coverage requirement. In this paper, we propose a hybrid algorithm (combining deterministic rounding and randomized rounding) for the FPCVC problem which, with probability at least 1-1/l alpha\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$1-1/l<^>{\alpha }$$\end{document}, returns a feasible solution with an objective value at most 9(alpha+1)2lnl+3\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\left( \frac{9(\alpha +1)}{2}\ln l+3\right) $$\end{document} times that of an optimal solution, where alpha\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\alpha $$\end{document} is a constant. We also show a lower bound of Omega(lnl)\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\Omega (\ln l)$$\end{document} for the approximability of FPCVC. Thus, our approxima
In this article we study the group Steiner network problem, which is defined in the following way. Given a graph G = (V,E), a partition of its vertices into K groups and connectivity requirements between the different...
详细信息
In this article we study the group Steiner network problem, which is defined in the following way. Given a graph G = (V,E), a partition of its vertices into K groups and connectivity requirements between the different groups, the aim is to find simultaneously a set of representatives, one for each group, and a minimum cost connected subgraph that satisfies the connectivity requirements between the groups (representatives). This problem is a generalization of the Steiner network problem and the group Steiner tree problem, two known NP-complete problems. We present an approximation algorithm for a special case of the group Steiner network problem with an approximation ratio of min {2(1 + 2x),2I}, where I is the cardinality of the largest-group and x is a parameter that depends on the cost function. (c) 2006 Wiley Periodicals, Inc.
暂无评论