A greedy algorithm for multicut and integral multiflow in rooted trees

We present an O(min(Kn,n²)) algorithm to solve the maximum integral multiflow and minimum multicut problems in rooted trees, where K is the number of commodities and n is the number of vertices. These problems are NP-hard in undirected trees but polynomial in directed trees. In the algorithm we propose, we first use a greedy procedure to build the multiflow then we use duality properties to obtain the multicut and prove the optimality.     

Rank, term rank, and chromatic number

Let G be a graph with a nonempty edge set, and with rank rk(G), term rank Rk(G), and chromatic number χ(G). We characterize Rk(G) as being the maximum number of colors in certain proper colorings of G. In particular, we observe that χ(G)Rk(G), with equality holding if and only if (besides isolated vertices) G is either complete or a star. For a twin-free graph G, we observe the bound and we show that this bound is sharp.     

Necessary conditions and non-existence results for autonomous nonconvex variational problems

Classical one-dimensional, autonomous Lagrange problems are considered. In absence of any smoothness, convexity or coercivity condition on the energy density, we prove a DuBois-Reymond type necessary condition, expressed as a differential inclusion involving the subdifferential of convex analysis. As a consequence, a non-existence result is obtained.     

Parametric and Non Homogeneous Semi-Markov Process for HIV Control

In AIDS control, physicians have a growing need to use pragmatically useful and interpretable tools in their daily medical taking care of patients. Semi-Markov process seems to be well adapted to model the evolution of HIV-1 infected patients. In this study, we introduce and define a non homogeneous semi-Markov (NHSM) model in continuous time. Then the problem of finding the equations that describe the biological evolution of patient is studied and the interval transition probabilities are computed. A parametric approach is used and the maximum likelihood estimators of the process are given. A Monte Carlo algorithm is presented for realizing non homogeneous semi-Markov trajectories. As results, interval transition probabilities are computed for distinct times and follow-up has an impact on the evolution of patients.      

An improved max-flow-based lower bound for minimizing maximum lateness on identical parallel machines

In this paper, we introduce a new concept of semi-preemptive scheduling and we show how it can be used to derive a maximum-flow-based lower bound for the P|r_j|L_max which dominates the well-known preemptive lower bound. We show that, in some cases, the proposed bound strictly dominates the preemptive one while having the same complexity.     

On the maximum principle for complete second-order elliptic operators in general domains

This paper is concerned with the maximum principle for second-order linear elliptic equations in a wide generality. By means of a geometric condition previously stressed by Berestycki-Nirenberg-Varadhan, Cabré was very able to improve the classical ABP estimate obtaining the maximum principle also in unbounded domains, such as infinite strips and open connected cones with closure different from the whole space. Now we introduce a new geometric condition that extends the result to a more general class of domains including the complements of hypersurfaces, as for instance the cut plane. The methods developed here allow us to deal with complete second-order equations, where the admissible first-order term, forced to be zero in a preceding result with Cafagna, depends on the geometry of the domain.     

An example of a two-sided Wilcoxon signed rank test which is not unbiased

Although the theory of rank tests is rather complete in the one-sided case, it was not even known in 1959, whether the Wilcoxon two-sample test and other similar tests are unbiased against the two-sided alternatives (Lehmann (1959,Testing Statistical Hypotheses, p. 240, Wiley, New York)). A partial answer to this question was given by Sugiura in 1965, who found, that the test named above may be biased (Sugiura (1965,Ann. Inst. Statist. Math.,17, 261–263)). According to Lehmann (1986,Testing Statistical Hypotheses, 2nd ed., pp. 322–324, Wiley, New York) it seems to be still open, whether the same is true for the WILCOXON one-sample test, which is also known as WILCOXON signed rank test. This will be shown in the present paper.     

BAHADUR ASYMPTOTIC EFFICIENCY IN A SEMIPARAMETRIC REGRESSION MODEL

ＢＡＨＡＤＵＲＡＳＹＭＰＴＯＴＩＣＥＦＦＩＣＩＥＮＣＹＩＮＡＳＥＭＩＰＡＲＡＭＥＴＲＩＣＲＥＧＲＥＳＳＩＯＮＭＯＤＥＬ￥ＬＩＡＮＧＨＵＡ；ＣＨＥＮＧＰＩＮＧＡｂｓｔｒａｃｔ：ＴｈｅａｕｔｈｏｒＳｇｉｖｅＭＬＥθ１ＭＬｏｆθ１ｉｎｔｈｅｍｏｄｅｌＹ＝θ...     

A graph theory approach to subcontracting, machine duplication and intercell moves in cellular manufacturing

We address in this paper the problem of finding an optimal strategy for dealing with bottleneck machines and bottleneck parts in the cell formation process in group technology. Three types of economic decisions are considered: subcontracting, machine duplication and intercell moves. The problem is formulated as a minimum weighted node covering problem in a hypergraph, and we show that it can be solved in polynomial time by finding a maximum weighted stable set in a bipartite graph. We extend this result to cellular manufacturing systems in which the sequence of operations of each part is known in advance.     

On the exact distribution of linear combinations of order statistics from dependent random variables

We study the exact distribution of linear combinations of order statistics of arbitrary (absolutely continuous) dependent random variables. In particular, we examine the case where the random variables have a joint elliptically contoured distribution and the case where the random variables are exchangeable. We investigate also the particular L-statistics that simply yield a set of order statistics, and study their joint distribution. We present the application of our results to genetic selection problems, design of cellular phone receivers, and visual acuity. We give illustrative examples based on the multivariate normal and multivariate Student t distributions.