Improved adaptive group testing algorithms with applications to multiple access channels and dead sensor diagnosis

We study group-testing algorithms for resolving broadcast conflicts on a multiple access channel (MAC) and for identifying the dead sensors in a mobile ad hoc wireless network. In group-testing algorithms, we are asked to identify all the defective items in a set of items when we can test arbitrary subsets of items. In the standard group-testing problem, the result of a test is binary—the tested subset either contains defective items or not. In the more generalized versions we study in this paper, the result of each test is non-binary. For example, it may indicate whether the number of defective items contained in the tested subset is zero, one, or at least two. We give adaptive algorithms that are provably more efficient than previous group testing algorithms. We also show how our algorithms can be applied to solve conflict resolution on a MAC and dead sensor diagnosis. Dead sensor diagnosis poses an interesting challenge compared to MAC resolution, because dead sensors are not locally detectable, nor are they themselves active participants. A preliminary version of this paper was presented at SPAA 2006.     

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\).     

Constraining the number of positive responses in adaptive,non-adaptive,and two-stage group testing

Group testing is a well known search problem that consists in detecting the defective members of a set of objects O by performing tests on properly chosen subsets (pools) of the given set O. In classical group testing the goal is to find all defectives by using as few tests as possible. We consider a variant of classical group testing in which one is concerned not only with minimizing the total number of tests but aims also at reducing the number of tests involving defective elements. The rationale behind this search model is that in many practical applications the devices used for the tests are subject to deterioration due to exposure to or interaction with the defective elements. In this paper we consider adaptive, non-adaptive and two-stage group testing. For all three considered scenarios, we derive upper and lower bounds on the number of “yes” responses that must be admitted by any strategy performing at most a certain number t of tests. In particular, for the adaptive case we provide an algorithm that uses a number of “yes” responses that exceeds the given lower bound by a small constant. Interestingly, this bound can be asymptotically attained also by our two-stage algorithm, which is a phenomenon analogous to the one occurring in classical group testing. For the non-adaptive scenario we give almost matching upper and lower bounds on the number of “yes” responses. In particular, we give two constructions both achieving the same asymptotic bound. An interesting feature of one of these constructions is that it is an explicit construction. The bounds for the non-adaptive and the two-stage cases follow from the bounds on the optimal sizes of new variants of d-cover free families and (p, d)-cover free families introduced in this paper, which we believe may be of interest also in other contexts.     

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.     

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.     

证券组合有效子集的统计检验及实证研究

本文研究了投资组合管理中的证券子集选择问题,通过分析证券组合有效子集与均值-方差张成的关系,给出了一种新的基于统计推断的证券子集有效性检验方法,同时也拓展了Huberman和Kandel的均值-方差张成条件。实证结果表明,本文的方法相对于现有的基于矩阵秩的判别方法更稳健。     

New combinatorial structures with applications to efficient group testing with inhibitors

Group testing with inhibitors (GTI) is a variant of classical group testing where in addition to positive items and negative items, there is a third class of items called inhibitors. In this model the response to a test is YES if and only if the tested group of items contains at least one positive item and no inhibitor. This model of group testing has been introduced by Farach et al. (Proceedings of compression and complexity of sequences, pp 357–367, 1997) for applications in the field of molecular biology. In this paper we investigate the GTI problem both in the case when the exact number of positive items is given, and in the case when the number of positives is not given but we are provided with an upper bound on it. For the latter case, we present a lower bound on the number of tests required to determine the positive items in a completely nonadaptive fashion. Also under the same hypothesis, we derive an improved lower bound on the number of tests required by any algorithm (using any number of stages) for the GTI problem. As far as it concerns the case when the exact number of positives is known, we give an efficient trivial two-stage algorithm. Instrumental to our results are new combinatorial structures introduced in this paper. In particular we introduce generalized versions of the well known superimposed codes (Du, D.Z., Hwang, F.K. in Pooling designs and nonadaptive group testing, 2006; Dyachkov, A.G., Rykov, V.V. in Probl. Control Inf. Theory 12:7–13, 1983; Dyachkov, A.G., et al. in J. Comb. Theory Ser. A 99:195–218, 2002; Kautz, W.H., Singleton, R.R. in IEEE Trans. Inf. Theory 10:363–377, 1964) and selectors (Clementi, A.E.F, et al. in Proceedings of symposium on discrete algorithms, pp. 709–718, 2001; De Bonis, A., et al. in SIAM J Comput. 34(5):1253–1270, 2005; Indyk, P. in Proceedings of symposium on discrete algorithms, pp. 697–704, 2002) that we believe to be of independent interest.     

A new EPQ model: integrating lower pricing,rework and reject situations

The economic production quantity (EPQ) is a well-known and commonly used inventory control technique. It has been used for well over 50 years to optimize lot sizes in transportation/production. The standard results are easy to apply but are based on a number of assumptions. A common assumption in the EPQ model is that all units produced are of perfect quality, this will underestimate the actual required quantity. Many researchers have studied the effects after relaxing this assumption on the EPQ model. The previous studies had considered that imperfect quality and defective items are either to be reworked instantaneously and kept in stock or rejected at a cost. The objective of this paper is to provide a framework to integrate lower pricing, rework and reject situations into a single EPQ model. A 100% inspection is performed in order to identify the amount of good quality items, imperfect quality items and defective items in each lot. This model assumes that items of imperfect quality, not necessarily defective, could be used in another production situation or sold to a particular purchaser at a lower price. The electronic and clothing industries give good examples for such situations. A mathematical model is developed and a numerical example is presented to illustrate the solution procedures. It is found that the time factor of when to sell the imperfect items is critical, as this decision will affect the inventory cost and the batch quantities.     

Lower bounds on the adaptivity gaps in variants of the stochastic knapsack problem

We consider stochastic variants of the NP-hard 0/1 knapsack problem in which item values are deterministic and item sizes are independent random variables with known, arbitrary distributions. Items are placed in the knapsack sequentially, and the act of placing an item in the knapsack instantiates its size. The goal is to compute a policy for insertion of the items, that maximizes the expected value of the set of items placed in the knapsack. These variants that we study differ only in the formula for computing the value of the final solution obtained by the policy. We consider both nonadaptive policies (that designate a priori a fixed subset or permutation of items to insert) and adaptive policies (that can make dynamic decisions based on the instantiated sizes of the items placed in the knapsack thus far). Our work characterizes the benefit of adaptivity. For this purpose we use a measure called the adaptivity gap: the supremum over instances of the ratio between the expected value obtained by an optimal adaptive policy and the expected value obtained by an optimal non-adaptive policy. We show that while for the variants considered in the literature this quantity is bounded by a constant there are other variants where it is unbounded.     

The second largest number of maximal independent sets in connected graphs with at most one cycle

A maximal independent set is an independent set that is not a proper subset of any other independent set. In this paper, we determine the second largest number of maximal independent sets among all graphs (respectively, connected graphs) of order n??4 with at most one cycle. We also characterize those extremal graphs achieving these values.     

Statistical Modeling of Fire Occurrence Using Data from the Tōhoku,Japan Earthquake and Tsunami

In this article, we develop statistical models to predict the number and geographic distribution of fires caused by earthquake ground motion and tsunami inundation in Japan. Using new, uniquely large, and consistent data sets from the 2011 Tōhoku earthquake and tsunami, we fitted three types of models—generalized linear models (GLMs), generalized additive models (GAMs), and boosted regression trees (BRTs). This is the first time the latter two have been used in this application. A simple conceptual framework guided identification of candidate covariates. Models were then compared based on their out‐of‐sample predictive power, goodness of fit to the data, ease of implementation, and relative importance of the framework concepts. For the ground motion data set, we recommend a Poisson GAM; for the tsunami data set, a negative binomial (NB) GLM or NB GAM. The best models generate out‐of‐sample predictions of the total number of ignitions in the region within one or two. Prefecture‐level prediction errors average approximately three. All models demonstrate predictive power far superior to four from the literature that were also tested. A nonlinear relationship is apparent between ignitions and ground motion, so for GLMs, which assume a linear response‐covariate relationship, instrumental intensity was the preferred ground motion covariate because it captures part of that nonlinearity. Measures of commercial exposure were preferred over measures of residential exposure for both ground motion and tsunami ignition models. This may vary in other regions, but nevertheless highlights the value of testing alternative measures for each concept. Models with the best predictive power included two or three covariates.     

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.     

A Model for Resource Constrained Production and Inventory Management

We present a general model for multi-item production and inventory management problems that include a resource restriction. The decision variables in the model can take on a variety of interpretations, but will typically represent cycle times, production batch sizes, number of production runs, or order quantities for each item. We consider environments where item demand rates are approximately constant and performing an activity such as producing a batch of a product or placing an order results in the consumption of a scarceresource that is shared among the items. Some examples of shared resources include limited machine capacity, a restriction on the amount of money that can be tied up in stock, orlimited storage capacity. We focus on the case where the decision variables must be integer valued or selected from a discrete set of choices, such as when an integer number of production runs is desired for each item, or in order quantity problems where the items come in pack sizes containing more than one unit and, therefore, the order quantities must be an integer multiple of the pack sizes. We develop a heuristic and a branch and bound algorithm for solving the problem. The branch and bound algorithm includes reoptimization procedures and the heuristic to improve its performance. Computational testing indicates that the algorithms are effective for solving the general model.     

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

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

A PTAS for the minimum weighted dominating set problem with smooth weights on unit disk graphs

In the minimum weighted dominating set problem (MWDS), we are given a unit disk graph with non-negative weight on each vertex. The MWDS seeks a subset of the vertices of the graph with minimum total weight such that each vertex of the graph is either in the subset or adjacent to some nodes in the subset. A?weight function is called smooth, if the ratio of the weights of any two adjacent nodes is upper bounded by a constant. MWDS is known to be NP-hard. In this paper, we give the first polynomial time approximation scheme (PTAS) for MWDS with smooth weights on unit disk graphs, which achieves a (1+ε)-approximation for MWDS, for any ε>0.     

Facility Location: A Robust Optimization Approach

In this research, we apply robust optimization (RO) to the problem of locating facilities in a network facing uncertain demand over multiple periods. We consider a multi‐period fixed‐charge network location problem for which we find (1) the number of facilities, their location and capacities, (2) the production in each period, and (3) allocation of demand to facilities. Using the RO approach we formulate the problem to include alternate levels of uncertainty over the periods. We consider two models of demand uncertainty: demand within a bounded and symmetric multi‐dimensional box, and demand within a multi‐dimensional ellipsoid. We evaluate the potential benefits of applying the RO approach in our setting using an extensive numerical study. We show that the alternate models of uncertainty lead to very different solution network topologies, with the model with box uncertainty set opening fewer, larger facilities. Through sample path testing, we show that both the box and ellipsoidal uncertainty cases can provide small but significant improvements over the solution to the problem when demand is deterministic and set at its nominal value. For changes in several environmental parameters, we explore the effects on the solution performance.     

基于动态博弈的闭环供应链回收质量控制研究

本文采用三阶段的动态博弈模型,研究了在单个制造商和单个销售商构成的分散式闭环供应链中,占主导地位的制造商如何制定质量处罚比例和质量抽检比例,从而对销售商回收的废旧产品数量和质量实施引导和控制。本文建立了相应的模型并给出了最优解,并通过算例讨论了不同的废旧产品缺陷率和监督成本对双方决策的影响。     

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.     

A better constant-factor approximation for weighted dominating set in unit disk graph

This paper presents a (10+ε)-approximation algorithm to compute minimum-weight connected dominating set (MWCDS) in unit disk graph. MWCDS is to select a vertex subset with minimum weight for a given unit disk graph, such that each vertex of the graph is contained in this subset or has a neighbor in this subset. Besides, the subgraph induced by this vertex subset is connected. Our algorithm is composed of two phases: the first phase computes a dominating set, which has approximation ratio 6+ε (ε is an arbitrary positive number), while the second phase connects the dominating sets computed in the first phase, which has approximation ratio 4. This work is supported in part by National Science Foundation under grant CCF-9208913 and CCF-0728851; and also supported by NSFC (60603003) and XJEDU.