On Some Polyhedra Covering Problems

Let P ⁰, P ¹ be two simple polyhedra and let P ² be a convex polyhedron in E ³. Polyhedron P ⁰ is said to be covered by polyhedra P ¹ and P ² if every point of P ⁰ is a point of P ¹ P ². The following polyhedron covering problem is studied: given the positions of P ⁰, P ¹, and P ² in the xy-coordinate system, determine whether or not P ⁰ can be covered by P ¹ P ² via translation and rotation of P ¹ and P ²; furthermore, find the exact covering positions of these polyhedra if such a cover exists. It is shown in this paper that if only translation is allowed, then the covering problem of P ⁰, P ¹ and P ² can be solved in O(m ² n ²(m + n)l)) polynomial time, where m, n, and l are the sizes of P ⁰, P ¹, and P ², respectively. The method can be easily extended to the problem in E ^d for any fixed d > 3.     

A parameterized perspective on packing paths of length two

We study (vertex-disjoint) packings of paths of length two (i.e., of P ₂’s) in graphs under a parameterized perspective. Starting from a maximal P ₂-packing ℘ of size j we use extremal combinatorial arguments for determining how many vertices of ℘ appear in some P ₂-packing of size (j+1) (if such a packing exists). We prove that one can ‘reuse’ 2.5j vertices. We also show that this bound is asymptotically sharp. Based on a WIN-WIN approach, we build an algorithm which decides, given a graph, if a P ₂-packing of size at least k exists in time O^*(2.448^3k)\mathcal{O}^{*}(2.448^{3k}) .     

On the equitable k *-laceability of hypercubes

Let G be a finite undirected bipartite graph. Let u, v be two vertices of G from different partite sets. A collection of k internal vertex disjoint paths joining u to v is referred as a k-container C _k (u,v). A k-container is a k ^*-container if it spans all vertices of G. We define G to be a k ^*-laceable graph if there is a k ^*-container joining any two vertices from different partite sets. A k ^*-container C _k ^*(u,v)={P ₁,…,P _k } is equitable if ||V(P _i )|−|V(P _j )||≤2 for all 1≤i,j≤k. A graph is equitably k ^*-laceable if there is an equitable k ^*-container joining any two vertices in different partite sets. Let Q _n be the n-dimensional hypercube. In this paper, we prove that the hypercube Q _n is equitably k ^*-laceable for all k≤n−4 and n≥5. Dedicated to Professor Frank K. Hwang on the occasion of his 65th birthday. The work of H.-M. Huang was supported in part by the National Science Council of the Republic of China under NSC94-2115-M008-013.     

Hardness of <Emphasis Type="Italic">k</Emphasis>-Vertex-Connected Subgraph Augmentation Problem

Given a k-connected graph G=(V,E) and V ^′⊂V, k-Vertex-Connected Subgraph Augmentation Problem (k-VCSAP) is to find S⊂V∖V ^′ with minimum cardinality such that the subgraph induced by V ^′∪S is k-connected. In this paper, we study the hardness of k-VCSAP in undirect graphs. We first prove k-VCSAP is APX-hard. Then, we improve the lower bound in two ways by relying on different assumptions. That is, we prove no algorithm for k-VCSAP has a PR better than O(log (log n)) unless P=NP and O(log n) unless NP⊆DTIME(n ^{O(log log n)}), where n is the size of an input graph.     

On cubic 2-independent Hamiltonian connected graphs

A graph G=(V,E) is Hamiltonian connected if there exists a Hamiltonian path between any two vertices in G. Let P ₁=(u ₁,u ₂,…,u _|V|) and P ₂=(v ₁,v ₂,…,v _|V|) be any two Hamiltonian paths of G. We say that P ₁ and P ₂ are independent if u ₁=v ₁,u _|V|=v _|V|, and u _i ≠v _i for 1<i<|V|. A cubic graph G is 2-independent Hamiltonian connected if there are two independent Hamiltonian paths between any two different vertices of G. A graph G is 1-Hamiltonian if G−F is Hamiltonian for any F⊆V∪E with |F|=1. A graph G is super 3^*-connected if there exist i internal disjoint paths spanning G for i=1,2,3. It is proved that every super 3^*-connected graph is 1-Hamiltonian. In this paper, we prove that every cubic 2-independent Hamiltonian connected graph is also 1-Hamiltonian. We present some cubic 2-independent Hamiltonian connected graphs that are super 3^*-connected, some cubic 2-independent Hamiltonian connected graphs that are not super 3^*-connected, some super 3^*-connected graphs that are not 2-independent Hamiltonian connected, and some cubic 1-Hamiltonian graphs that are Hamiltonian connected but neither 2-independent Hamiltonian connected nor super 3^*-connected. Dedicated to Professor Frank K. Hwang on the occasion of his 65th birthday. This work was supported in part by the National Science Council of the Republic of China under Contract NSC 94-2213-E-233-011.     

Probability of Exporting Infected Carcasses from Vaccinated Pigs Following a Foot‐and‐Mouth Disease Epidemic

Emergency vaccination is an effective control strategy for foot‐and‐mouth disease (FMD) epidemics in densely populated livestock areas, but results in a six‐month waiting period before exports can be resumed, incurring severe economic consequences for pig exporting countries. In the European Union, a one‐month waiting period has been discussed based on negative test results in a final screening. The objective of this study was to analyze the risk of exporting FMD‐infected pig carcasses from a vaccinated area: (1) directly after final screening and (2) after a six‐month waiting period. A risk model has been developed to estimate the probability that a processed carcass was derived from an FMD‐infected pig (P_carc). Key variables were herd prevalence (P_H), within‐herd prevalence (P_A), and the probability of detection at slaughter (P_SL). P_H and P_A were estimated using Bayesian inference under the assumption that, despite all negative test results, ≥1 infected pigs were present. Model calculations indicated that P_carc was on average 2.0 × 10^?5 directly after final screening, and 1.7 × 10^?5 after a six‐month waiting period. Therefore, the additional waiting time did not substantially reduce P_carc. The estimated values were worst‐case scenarios because only viraemic pigs pose a risk for disease transmission, while seropositive pigs do not. The risk of exporting FMD via pig carcasses from a vaccinated area can further be reduced by heat treatment of pork and/or by excluding high‐risk pork products from export.     

Minimizing the sum cost in linear extensions of a poset

A linear extension problem is defined as follows: Given a poset P=(E,≤), we want to find a linear order L such that x≤y in L whenever x≤yin P. In this paper, we assign each pair of elements x,y∈E with a cost, and to find a linear extension of P with the minimum sum cost. For the general case, it is NP-complete and we present a greedy approximation algorithm which can be finished in polynomial time. Also we consider a special case which can be solved in polynomial time.     

On the distance paired domination of generalized Petersen graphs <Emphasis Type="Italic">P</Emphasis>(<Emphasis Type="Italic">n</Emphasis>,1) and <Emphasis Type="Italic">P</Emphasis>(<Emphasis Type="Italic">n</Emphasis>,2)

Let G=(V,E) be a graph without an isolated vertex. A set D⊆V(G) is a k -distance paired dominating set of G if D is a k-distance dominating set of G and the induced subgraph 〈D〉 has a perfect matching. The minimum cardinality of a k-distance paired dominating set for graph G is the k -distance paired domination number, denoted by γ _p ^k (G). In this paper, we determine the exact k-distance paired domination number of generalized Petersen graphs P(n,1) and P(n,2) for all k≥1.     

The Polymatroid Steiner Problems

The Steiner tree problem asks for a minimum cost tree spanning a given set of terminals S⊂eqV in a weighted graph G = (V,E,c), c:E→ R⁺. In this paper we consider a generalization of the Steiner tree problem, so called Polymatroid Steiner Problem, in which a polymatroid P = P(V) is defined on V and the Steiner tree is required to span at least one base of P (in particular, there may be a single base S⊂eqV). This formulation is motivated by the following application in sensor networks – given a set of sensors S = {s₁,…,s_k}, each sensor s_i can choose to monitor only a single target from a subset of targets X_i, find minimum cost tree spanning a set of sensors capable of monitoring the set of all targets X = X₁ ∪ … ∪ X_k. The Polymatroid Steiner Problem generalizes many known Steiner tree problem formulations including the group and covering Steiner tree problems. We show that this problem can be solved with the polylogarithmic approximation ratio by a generalization of the combinatorial algorithm of Chekuri et al. (2002).We also define the Polymatroid directed Steiner problem which asks for a minimum cost arborescence connecting a given root to a base of a polymatroid P defined on the terminal set S. We show that this problem can be approximately solved by algorithms generalizing methods of Chekuri et al. (2002).A preliminary version of this paper appeared in ISAAC 2004     

RNA multiple structural alignment with longest common subsequences

In this paper, we present a new model for RNA multiple sequence structural alignment based on the longest common subsequence. We consider both the off-line and on-line cases. For the off-line case, i.e., when the longest common subsequence is given as a linear graph with n vertices, we first present a polynomial O(n ²) time algorithm to compute its maximum nested loop. We then consider a slightly different problem—the Maximum Loop Chain problem and present an algorithm which runs in O(n ⁵) time. For the on-line case, i.e., given m RNA sequences of lengths n, compute the longest common subsequence of them such that this subsequence either induces a maximum nested loop or the maximum number of matches, we present efficient algorithms using dynamic programming when m is small. This research is partially supported by EPSCOR Visiting Scholar's Program and MSU Short-term Professional Development Program.     

Edgeworth Expansions for Semiparametric Averaged Derivatives

A valid Edgeworth expansion is established for the limit distribution of density‐weighted semiparametric averaged derivative estimates of single index models. The leading term that corrects the normal limit varies in magnitude, depending on the choice of bandwidth and kernel order. In general this term has order larger than the n^−1/2 that prevails in standard parametric problems, but we find circumstances in which it is O(n^−1/2), thereby extending the achievement of an n^−1/2 Berry‐Esseen bound in Robinson (1995a). A valid empirical Edgeworth expansion is also established. We also provide theoretical and empirical Edgeworth expansions for a studentized statistic, where some correction terms are different from those for the unstudentized case. We report a Monte Carlo study of finite sample performance.     

The 2-Edge-Connected Subgraph Polyhedron

We study the polyhedron P(G) defined by the convex hull of 2-edge-connected subgraphs of G where multiple copies of edges may be chosen. We show that each vertex of P(G) is also a vertex of the LP relaxation. Given the close relationship with the Graphical Traveling Salesman problem (GTSP), we examine how polyhedral results for GTSP can be modified and applied to P(G). We characterize graphs for which P(G) is integral and study how this relates to a similar result for GTSP. In addition, we show how one can modify some classes of valid inequalities for GTSP and produce new valid inequalities and facets for P(G).     

Inference for the Identified Set in Partially Identified Econometric Models

This paper provides computationally intensive, yet feasible methods for inference in a very general class of partially identified econometric models. Let P denote the distribution of the observed data. The class of models we consider is defined by a population objective function Q(θ, P) for θ∈Θ. The point of departure from the classical extremum estimation framework is that it is not assumed that Q(θ, P) has a unique minimizer in the parameter space Θ. The goal may be either to draw inferences about some unknown point in the set of minimizers of the population objective function or to draw inferences about the set of minimizers itself. In this paper, the object of interest is Θ₀(P)=argmin_θ∈ΘQ(θ, P), and so we seek random sets that contain this set with at least some prespecified probability asymptotically. We also consider situations where the object of interest is the image of Θ₀(P) under a known function. Random sets that satisfy the desired coverage property are constructed under weak assumptions. Conditions are provided under which the confidence regions are asymptotically valid not only pointwise in P, but also uniformly in P. We illustrate the use of our methods with an empirical study of the impact of top‐coding outcomes on inferences about the parameters of a linear regression. Finally, a modest simulation study sheds some light on the finite‐sample behavior of our procedure.     

带机会约束的动态投资决策模型研究

本文在BlackScholes型市场中,建立了具有投资机会约束的CaR动态投资决策模型: ,其中x是初始财富,π(t)=(π₁(t),…,π_d(t))′∈R^d为可行的证券组合过程,X^π(T)为计划期末的财富水平,CaR(x,π,T)为投资期末的在险资本,R是投资者事先给定的某正的财富水平,0<β<1通过对该模型的讨论,得到了最优常数再调整策略的显式表达式,其金融学含义包括:对于机会约束下的动态投资组合,在风险中性市场中,最优的常数再调整投资策略是纯债券投资策略,最优的在险资本值为零;在风险非中性市场中,最优的常数再调整投资策略蕴涵了共同基金定理的成立。     

Computing the Distributions of Economic Models via Simulation

We study a Monte Carlo algorithm for computing marginal and stationary densities of stochastic models with the Markov property, establishing global asymptotic normality and O_P(n^–1/2) convergence. Asymptotic normality is used to derive error bounds in terms of the distribution of the norm deviation.     

Trivial Two-Stage Group Testing with High Error Rates

Given a population of cardinality q ^r that contains a positive subset P of cardinality p, we give a trivial two-stage method that has first stage pools each of which contains q ^{r – 2} objects. We assume that errors occur in the first stage. We give an algorithm that uses the results of first stage to generate a set CP of candidate positives with |CP| (r + 1)q. We give the expected value of |CPP|. At most (r + 1)q trivial second stage tests are needed to identify all the positives in CP. We assume that the second stage tests are error free.     

Optimal tree structure with loyal users and batch updates

We study the probabilistic model in the key tree management problem. Users have different behaviors. Normal users have probability p to issue join/leave request while the loyal users have probability zero. Given the numbers of such users, our objective is to construct a key tree with minimum expected updating cost. We observe that a single LUN (Loyal User Node) is enough to represent all loyal users. When 1−p≤0.57 we prove that the optimal tree that minimizes the cost is a star. When 1−p>0.57, we try to bound the size of the subtree rooted at every non-root node. Based on the size bound, we construct the optimal tree using dynamic programming algorithm in O(n⋅K+K ⁴) time where K=min {4(log (1−p)⁻¹)⁻¹,n} and n is the number of normal users.     

Pooling designs associated with unitary space and ratio efficiency comparison

Let \mathbbF^(2n+d)_q²\mathbb{F}^{(2\nu+\delta)}_{q^{2}} be a (2ν+δ)-dimensional unitary space of \mathbbF_q²\mathbb{F}_{q^{2}} , where δ=0 or 1. In this paper we construct a family of inclusion matrices associated with subspaces of \mathbbF^(2n+d)_q²\mathbb{F}^{(2\nu+\delta)}_{q^{2}} , and exhibit its disjunct property. Moreover, we compare the ratio efficiency of this construction with others, and find it smaller under some conditions.     

Large Sample Properties of Matching Estimators for Average Treatment Effects

Matching estimators for average treatment effects are widely used in evaluation research despite the fact that their large sample properties have not been established in many cases. The absence of formal results in this area may be partly due to the fact that standard asymptotic expansions do not apply to matching estimators with a fixed number of matches because such estimators are highly nonsmooth functionals of the data. In this article we develop new methods for analyzing the large sample properties of matching estimators and establish a number of new results. We focus on matching with replacement with a fixed number of matches. First, we show that matching estimators are not N^1/2‐consistent in general and describe conditions under which matching estimators do attain N^1/2‐consistency. Second, we show that even in settings where matching estimators are N^1/2‐consistent, simple matching estimators with a fixed number of matches do not attain the semiparametric efficiency bound. Third, we provide a consistent estimator for the large sample variance that does not require consistent nonparametric estimation of unknown functions. Software for implementing these methods is available in Matlab, Stata, and R.     

On domination number of Cartesian product of directed paths

Let γ(G) denote the domination number of a digraph G and let P _m □P _n denote the Cartesian product of P _m and P _n , the directed paths of length m and n. In this paper, we give a lower and upper bound for γ(P _m □P _n ). Furthermore, we obtain a necessary and sufficient condition for P _m □P _n to have efficient dominating set, and determine the exact values: γ(P ₂□P _n )=n, g(P₃\square P_n)=n+é\fracn4ù\gamma(P_{3}\square P_{n})=n+\lceil\frac{n}{4}\rceil, g(P₄\square P_n)=n+é\frac2n3ù\gamma(P_{4}\square P_{n})=n+\lceil\frac{2n}{3}\rceil, γ(P ₅□P _n )=2n+1 and g(P₆\square P_n)=2n+é\fracn+23ù\gamma(P_{6}\square P_{n})=2n+\lceil\frac{n+2}{3}\rceil.