An efficient FPRAS type group testing procedure to approximate the number of defectives

In many fault detection problems, we want to detect or identify defective items in a sample set by using the minimum number of tests. Group testing is for the scenario where each test is on a subset of items, and tells whether the subset contains at least one defective item or not. Another practically important problem is to estimate the number of defective items in a sample set. In this paper, we present an efficient FPRAS (fully polynomial-time randomized approximation scheme) type group testing procedure to approximate the number of defective items in a sample set.     

Distributed algorithms for barrier coverage via sensor rotation in wireless sensor networks

When deploying sensors to monitor boundaries of battlefields or country borders, sensors are usually dispersed from an aircraft following a predetermined path. In such scenarios sensing gaps are usually unavoidable. We consider a wireless sensor network consisting of directional sensors deployed using the line-based sensor deployment model. In this paper we propose distributed algorithms for weak and strong barrier coverage that allow sensors to determine their orientation such that the total number of gaps is minimized. We use simulations to analyze the performance of our algorithms and to compare them with related works.     

Quality strategies in supply chain alliances of disposable items

This paper studies a single-product distribution channel where a supplier manufactures items of a given type, some of which are defective, that are sold by a retailer who only detects a subset of the defective items, passing the rest along to customers. We conjecture the structure of the demand and cost functions, assuming customers to have a decreasing marginal aversion to bad quality while both the supplier and the retailer make marginally increasing efforts to avoid bad quality. This allows us to deduce several implicit parameters of a cost model based on observable data, such as the share of the channel margin. Once the parameters of the model are available, we analyze the result of vertical integration. Although we confirm the well-known fact that vertical integration improves the quality perceived by the customer, we characterize the supplier's decision of whether or not to provide a better quality in terms of the individual channel margins. As an alternative, we derive the conditions under which the supplier and the retailer may devise a mutually beneficial transfer contract that simultaneously increases their profit and improves quality.     

Efficient point coverage in wireless sensor networks

We study minimum-cost sensor placement on a bounded 3D sensing field, R, which comprises a number of discrete points that may or may not be grid points. Suppose we have ℓ types of sensors available with different sensing ranges and different costs. We want to find, given an integer σ ≥ 1, a selection of sensors and a subset of points to place these sensors such that every point in R is covered by at least σ sensors and the total cost of the sensors is minimum. This problem is known to be NP-hard. Let k_i denote the maximum number of points that can be covered by a sensor of the ith type. We present in this paper a polynomial-time approximation algorithm for this problem with a proven approximation ratio . In applications where the distance of any two points has a fixed positive lower bound, each k_i is a constant, and so we have a polynomial-time approximation algorithms with a constant guarantee. While γ may be large, we note that it is only a worst-case upper bound. In practice the actual approximation ratio is small, even on randomly generated points that do not have a fixed positive minimum distance between them. We provide a number of numerical results for comparing approximation solutions and optimal solutions, and show that the actual approximation ratios in these examples are all less than 3, even though γ is substantially larger. This research was supported in part by NSF under grant CCF-04080261 and by NSF of China under grant 60273062.     

Designing <Emphasis Type="Italic">k</Emphasis>-coverage schedules in wireless sensor networks

Some sensor network applications require k-coverage to ensure the quality of surveillance. Meanwhile, energy is another primary concern for sensor networks. In this paper, we investigate the Sensor Scheduling for k-Coverage (SSC) problem which requires to efficiently schedule the sensors, such that the monitored area can be k-covered throughout the whole network lifetime with the purpose of maximizing network lifetime. The SSC problem is NP-hard and we propose two heuristic algorithms under different scenarios. In addition, we develop a guideline for users to better design a sensor deployment plan to save energy by employing a density control scheme. Simulation results are presented to evaluate our proposed algorithms.     

A randomized competitive group testing procedure

In many fault detection problems, we want to identify all defective items from a set of n items using the minimum number of tests. Group testing is for the scenario where each test is on a subset of items, and tells whether the subset contains at least one defective item or not. In practice, the number d of defective items is often unknown in advance. In this paper, we propose a randomized group testing procedure RGT for the scenario where the number d of defectives is unknown in advance, and prove that RGT is competitive. By incorporating numerical results, we obtain improved upper bounds on the expected number of tests performed by RGT, for \(1\le d\le 10^6\). In particular, for \(1\le d\le 10^6\) and the special case where n is a power of 2, we obtain an upper bound of \(d\log \frac{n}{d}+Cd+O(\log d)\) with \(C\approx 2.67\) on the expected number of tests performed by RGT, which is better than the currently best upper bound in Cheng et al. (INFORMS J Comput 26(4):677–689, 2014). We conjecture that the above improved upper bounds based on numerical results from \(1\le d\le 10^6\) actually hold for all \(d\ge 1\).     

Maximizing target-temporal coverage of mission-driven camera sensor networks

In camera sensor networks (CSNs), the target coverage problem is of special importance since a sensor with different viewing directions captures distinct views for the same target. Furthermore, mission-driven monitoring applications in CSNs usually have special network lifetime requirements in which the limited battery lifetime of sensors probably can not sustain for full coverage. In this paper, based on effective-sensing model, we address three new coverage problems in mission-driven camera sensor networks, namely the target-temporal effective-sensing coverage with non-adjustable cameras (TEC-NC) problem, the target-temporal effective-sensing coverage with adjustable cameras (TEC-AC) problem, and the target-temporal effective-sensing coverage with fully-adjustable cameras (TEC-FAC) problem. Given a mission period, the common objective of the problems is to find a sleep-wakeup schedule such that the overall target-temporal coverage is maximized. For TEC-NC, we propose a 2-approximation algorithm and two new heuristics. We also design two greedy strategies, each of which can be combined with our solutions for TEC-NC to deal with TEC-AC and TEC-FAC, respectively. We finally conduct extensive experiments to evaluate the performance of the proposed algorithms, whose results indicate the proposed algorithms outperform the existing alternatives as well as are close to the theoretical optimum on average under certain conditions.     

A joint optimization of data ferry trajectories and communication powers of ground sensors for long-term environmental monitoring

Recently, various hybrid wireless sensor networks which consist of several robotic vehicles and a number of static ground sensors have been investigated. In this kind of system, the main role of the mobile nodes is to deliver the messages produced by the sensor nodes, and naturally their trajectory control becomes a significant issue closely related to the performance of the entire system. Previously, several communication power control strategies such as topology control are investigated to improve energy-efficiency of wireless sensor networks. However, to the best of our knowledge, no communication power control strategy has been investigated in the context of the hybrid wireless sensor networks. This paper introduces a new strategy to utilize the communication power control in multiple data ferry assisted wireless sensor network for long-term environmental monitoring such that the lifetime of the sensor network is maximized. We formally define the problem of our interest and show it is NP-hard. We further prove there exists no approximation algorithm for the problem which can produce a feasible solution for every possible problem instance even though there is a feasible solution. Then, we propose heuristic algorithms along with rigorous theoretical performance analysis for both the single data ferry case and the multiple data ferry case under certain condition.     

On optimal placement of relay nodes for reliable connectivity in wireless sensor networks

The paper addresses the relay node placement problem in two-tiered wireless sensor networks. Given a set of sensor nodes in Euclidean plane, our objective is to place minimum number of relay nodes to forward data packets from sensor nodes to the sink, such that: 1) the network is connected, 2) the network is 2-connected. For case one, we propose a (6+ε)-approximation algorithm for any ε > 0 with polynomial running time when ε is fixed. For case two, we propose two approximation algorithms with (24+ε) and (6/T+12+ε), respectively, where T is the ratio of the number of relay nodes placed in case one to the number of sensors. We further extend the results to the cases where communication radiuses of sensor nodes and relay nodes are different from each other.     

Optimal Acquisition Quantities in Remanufacturing with Condition Uncertainty

The condition of the used products acquired by remanufacturing firms often varies widely. A firm can manage this variation by acquiring a quantity of used items that exceeds demand, enabling it to remanufacture a subset of the acquired items in the best condition. As more excess items are acquired, the firm can increase its selectivity and lower its remanufacturing costs. In this paper, we examine the tradeoff of acquisition and scrapping costs vs. remanufacturing costs when used product condition is widely varying and uncertain. We derive acquisition quantities that minimize total expected costs for several representations of condition variability and remanufacturing cost structures. We find that, when costs are linear, the optimal acquisition quantity has a closed form and increases with the square root of the degree of condition variability. Our models are based on experience with remanufacturers of cell phones and imaging supplies, and application of our results is illustrated using example data from industry.     

我国上市公司CFO薪酬与盈余质量的相关性研究

本文研究了我国上市公司CFO薪酬与盈余质量的相关性.研究发现,随着我国上市公司治理机制的不断完善,上市公司逐步建立起了以盈余为业绩指标的CFO薪酬激励机制.通过文章逐层递进的研究,我们发现我国上市公司CFO薪酬激励契约显著地区别反映了盈余中的非经常性损益和经常性损益,但是却未能有效地区别反映经常性损益中的应计项目和经营性现金流,存在类似"功能锁定"的现象.进一步细分研究样本后,我们发现由于盈余管理上市公司CFO薪酬激励契约对非经常性损益和经常性损益的不合理权重赋值,扭亏上市公司的CFO薪酬激励契约反而刺激了CFO进行盈余管理.根据研究我们认为,解决CFO薪酬激励契约对应计项目和经营性现金流的"功能锁定"现象,改进盈余管理上市公司CFO薪酬激励契约成为目前我国上市公司完善CFO薪酬激励机制的两个重要任务.     

Lot sizing in case of defective items with investments to increase the speed of quality control

In many cases the quality of each item in a lot is checked. Speeding up the quality checking process increases the responsiveness of the system and saves cost. The percentage of defective items is a random variable and two models are proposed. In one of the models the system remains always at the same state, while in the other one after each order cycle, the state of the system may change, thus the percentage of defective items may be different in consecutive periods. In both cases the speed of the quality checking is a variable, and procedures are provided to find the optimal lot sizes and screening speed for general and specific investment cost functions. The characteristics of the two model settings will largely be different when the percentage of defective items is high. Among the important managerial insights gained is that a high unit backlogging cost, especially spurs the system to invest more intensively into improving the quality checking process.     

Approximability of the subset sum reconfiguration problem

The subset sum problem is a well-known NP-complete problem in which we wish to find a packing (subset) of items (integers) into a knapsack with capacity so that the sum of the integers in the packing is at most the capacity of the knapsack and at least a given integer threshold. In this paper, we study the problem of reconfiguring one packing into another packing by moving only one item at a time, while at all times maintaining the feasibility of packings. First we show that this decision problem is strongly NP-hard, and is PSPACE-complete if we are given a conflict graph for the set of items in which each vertex corresponds to an item and each edge represents a pair of items that are not allowed to be packed together into the knapsack. We then study an optimization version of the problem: we wish to maximize the minimum sum among all packings in a reconfiguration. We show that this maximization problem admits a polynomial-time approximation scheme, while the problem is APX-hard if we are given a conflict graph.     

Bin packing under linear constraints

In this paper, we study a bin packing problem in which the sizes of items are determined by k linear constraints, and the goal is to decide the sizes of items and pack them into a minimal number of unit sized bins. We first provide two scenarios that motivate this research. We show that this problem is NP-hard in general, and propose several algorithms in terms of the number of constraints. If the number of constraints is arbitrary, we propose a 2-approximation algorithm, which is based on the analysis of the Next Fit algorithm for the bin packing problem. If the number of linear constraints is a fixed constant, then we obtain a PTAS by combining linear programming and enumeration techniques, and show that it is an optimal algorithm in polynomial time when the number of constraints is one or two. It is well known that the bin packing problem is strongly NP-hard and cannot be approximated within a factor 3 / 2 unless P = NP. This result implies that the bin packing problem with a fixed number of constraints may be simper than the original bin packing problem. Finally, we discuss the case when the sizes of items are bounded.     

Approximation Algorithms for the Multiple Knapsack Problem with Assignment Restrictions

Motivated by a real world application, we study the multiple knapsack problem with assignment restrictions (MKAR). We are given a set of items, each with a positive real weight, and a set of knapsacks, each with a positive real capacity. In addition, for each item a set of knapsacks that can hold that item is specified. In a feasible assignment of items to knapsacks, each item is assigned to at most one knapsack, assignment restrictions are satisfied, and knapsack capacities are not exceeded. We consider the objectives of maximizing assigned weight and minimizing utilized capacity.We focus on obtaining approximate solutions in polynomial computational time. We show that simple greedy approaches yield 1/3-approximation algorithms for the objective of maximizing assigned weight. We give two different 1/2-approximation algorithms: the first one solves single knapsack problems successively and the second one is based on rounding the LP relaxation solution. For the bicriteria problem of minimizing utilized capacity subject to a minimum requirement on assigned weight, we give an (1/3,2)-approximation algorithm.     

Average-Case Performance Analysis of a 2D Strip Packing Algorithm—NFDH

The two-dimensional strip packing problem is a generalization of the classic one-dimensional bin packing problem. It has many important applications such as costume clipping, material cutting, real-world planning, packing, scheduling etc. Average-case performance analysis of approximation algorithms attracts a lot of attention because it plays a crucial role in selecting an appropriate algorithm for a given application. While approximation algorithms for two-dimensional packing are frequently presented, the results of their average-case performance analyses have seldom been reported due to intractability. In this paper, we analyze the average-case performance of Next Fit Decreasing Height (NFDH) algorithm, one of the first strip packing algorithms proposed by Coffman, Jr. in 1980. We prove that the expected height of packing with NFDH algorithm, when the heights and widths of the rectangle items are independent and both obey (0, 1] uniform distribution, is about n/3, where n is the number of rectangle items. We also validate the theoretical result with experiments.This work is supported by National 973 Fundamental Research Project of China on NP Complete Problems and High Performance Software (No. G1998030403).     

Exact algorithms for scheduling programs with shared tasks

We study a scheduling problem where the jobs we have to perform are composed of one or more tasks. If two jobs sharing a non-empty subset of tasks are scheduled on the same machine, then these shared tasks have to be performed only once. This kind of problem is known in the literature under the names of VM-PACKING or PAGINATION. Our objective is to schedule a set of these objects on two parallel identical machines, with the aim of minimizing the makespan. This problem is NP-complete as an extension of the PARTITION problem. In this paper we present three exact algorithms with worst-case time-complexity guarantees, by exploring different branching techniques. Our first algorithm focuses on the relation between jobs sharing one or more symbols in common, whereas the two other algorithms branches on the shared symbols.

     

企业文化内部传播渠道个人感知量表的建构

通过对企业文化内部传播渠道的文献调研和企业访谈获得了量表的初始条目,在预测试和正式测试两个阶段,采用探索性因子分析、相关分析等技术对量表进行了检验和修改,得出了沟通、CEO榜样作用、直接上级榜样作用、同事榜样作用、英雄人物与故事、奖惩、活动七个因子,数据分析结果表明,量表具有良好的同质信度、折半信度、结构效度和预测效度.     

Inner and outer approximations of technology: A shadow profit approach

In this paper we extend the taxonomy on inner and outer approximations to a technology by assuming that price data are not available. Mimicking Varian [Varian H., Econometrica 1984;52(3):579], we introduce a Weak Axiom of Shadow Profit Maximization (WASPM) to test if observed production plans are compatible with technically efficient behavior. If the test fails for an observed sample, we then characterize the maximal subset of observed production plans that meets WASPM and we derive lower and upper bounds on technical efficiency for production plans that are observed but not in this subset. We also derive linear programs to implement these bounds.     

Optimal Stopping Analysis of a Radiation Detection System to Protect Cities from a Nuclear Terrorist Attack

We formulate and analyze an optimal stopping problem concerning a terrorist who is attempting to drive a nuclear or radiological weapon toward a target in a city center. In our model, the terrorist needs to travel through a two-dimensional lattice containing imperfect radiation sensors at some of the nodes, and decides at each node whether to detonate the bomb or proceed. We consider five different scenarios containing various informational structures and two different sensor array topologies: the sensors are placed randomly or they form an outer wall around the periphery of the city. We find that sensors can act as a deterrent in some cases, and that the government prefers the outer wall topology unless the sensors have a very low detection probability and the budget is tight (so that they are sparsely deployed).