共查询到10条相似文献,搜索用时 140 毫秒
1.
Steven Buechler 《Israel Journal of Mathematics》1985,52(1-2):65-81
In this paper we give a complete solution to the classification problem forω-categorical,ω-stable theories. More explicitly, supposeT isω-categorical,ω-stable with fewer than the maximum number of models in some uncountable power. We associate with each modelM ofT a “simple” invariantI(M), not unlike a vector of dimensions, such thatI(M)=I(N) if and only ifM≅N. The spectrum function,I(−,T), for a first-order theoryT is such that for all infinite cardinals λ,I(λ,T) is the number of nonisomorphic models ofT of cardinality λ. As an application of our “structure theorem” we determine the possible spectrum functions forω-categorical,ω-stable theories. 相似文献
2.
Consider a finite setE, a weight functionw:E→R, and two matroidsM
1 andM
2 defined onE. The weighted matroid intersection problem consists of finding a setI⊆E, independent in both matroids, that maximizes Σ{w(e):e inI}. We present an algorithm of complexity O(nr(r+c+logn)) for this problem, wheren=|E|,r=min(rank(M
1), rank (M
2)),c=max (c
1,c
2) and, fori=1,2,c
i
is the complexity of finding the circuit ofI∪{e} inM
i
(or show that none exists) wheree is inE andI⊆E is independent inM
1 andM
2. A related problem is to find a maximum weight set, independent in both matroids, and of given cardinalityk (if one exists). Our algorithm also solves this problem. In addition, we present a second algorithm that, given a feasible
solution of cardinalityk, finds an optimal one of the same cardinality. A sensitivity analysis on the weights is easy to perform using this approach.
Our two algorithms are related to existing algorithms. In fact, our framework provides new simple proofs of their validity.
Other contributions of this paper are the existence of nonnegative reduced weights (Theorem 6), allowing the improved complexity
bound, and the introduction of artificial elements, allowing an improved start and flexibility in the implementation of the
algorithms.
This research was supported in part by NSF grant ECS 8503192 to Carnegie-Mellon University. 相似文献
3.
Ganesh S. Kadu 《印度理论与应用数学杂志》2011,42(2):73-97
Let (A, m) be a Cohen-Macaulay local ring, M a Cohen-Macaulay A-module of dimension d ≥ 1 and I a proper ideal of analytic deviation one with respect to M. In this paper we study the Cohen-Macaulayness of associated graded module of a Cohen-Macaulay module. We show that if I is generically a complete intersection of analytic deviation one and reduction number at most one with respect to M then G
I
(M) is Cohen-Macaulay. When analytic spread of I with respect to M equals d we prove a similar result when reduction number of an ideal is atmost two. 相似文献
4.
In this article, we determine the integral transforms of several two-boundary functionals for a difference of a compound Poisson
process and a compound renewal process. Another part of the article is devoted to studying the above-mentioned process reflected
at its infimum. We use the results obtained to study a G
δ
|M
ϰ
|1|B system with batch arrivals and finite buffer in the case when δ∼ge(λ). We derive the distributions of the main characteristics of the queuing system, such as the busy period, the time of the
first loss of a customer, the number of customers in the system, the virtual waiting time in transient and stationary regimes.
The advantage is that these results are given in a closed form, namely, in terms of the resolvent sequences of the process. 相似文献
5.
K. Lounici 《Mathematical Methods of Statistics》2007,16(3):246-259
We study the problem of aggregation of estimators. Given a collection of M different estimators, we construct a new estimator, called aggregate, which is nearly as good as the best linear combination
over an l
1-ball of ℝM of the initial estimators. The aggregate is obtained by a particular version of the mirror averaging algorithm. We show that
our aggregation procedure statisfies sharp oracle inequalities under general assumptions. Then we apply these results to a
new aggregation problem: D-convex aggregation. Finally we implement our procedure in a Gaussian regression model with random design and we prove its
optimality in a minimax sense up to a logarithmic factor.
相似文献
6.
Gerhard Opfer 《Numerische Mathematik》1982,39(3):411-420
Summary We transform a complex approximation problem into an equivalent semiinfinite optimization problem whose constraints are described in terms of a quantity [0,2[=I. We study the effect of disturbing the problem by replacingI by a compact subsetMI which includes as special case the discrete case whereM consists only of finitely many points. We introduce a measure for the deviation ofM fromI and show that in any complex approximation problem the minimal distance of the disturbed problem converges quadratically with 0 to the minimal distance of the undisturbed problem which is a generalization of a result by Streit and Nuttall. We also show that in a linear finite dimensional approximation problem the convergence of the coefficients of the disturbed problem is in general at most linear. There are some graphical representations of best complex approximations computed with the described method. 相似文献
7.
Let R be an arbitrary ring with identity and M a right R-module with S = EndR(M). Let F be a fully invariant submodule of M and I?1(F) denotes the set {m∈M:Im?F} for any subset I of S. The module M is called F-Baer if I?1(F) is a direct summand of M for every left ideal I of S. This work is devoted to the investigation of properties of F-Baer modules. We use F-Baer modules to decompose a module into two parts consists of a Baer module and a module determined by fully invariant submodule F, namely, for a module M, we show that M is F-Baer if and only if M = F⊕N where N is a Baer module. By using F-Baer modules, we obtain some new results for Baer rings. 相似文献
8.
In this article we introduce the sequence spaces cI(M),c0I(M),mI(M) and m0I(M) using the Orlicz function M.We study some of the properties like solid,symmetric,sequence algebra,etc and prove some inclusion relations. 相似文献
9.
S. M. Guu 《Journal of Optimization Theory and Applications》1996,89(2):373-387
The concept of sign reversing is a useful tool to characterize certain matrix classes in linear complementarity problems. In this paper, we characterize the sign-reversal set of an arbitrary square matrixM in terms of the null spaces of the matricesI–⁁+⁁M, where ⁁ is a diagonal matrix such that 0⁁I. These matrices are used to characterize the membership ofM in the classes P0, P, and the class of column-sufficient matrices. A simple proof of the Gale and Nikaido characterization theorem for the membership in P is presented.We also study the class of diagonally semistable matrices. We prove that this class is contained properly in the class of sufficient matrices. We show that to characterize the diagonally semistable property is equivalent to solving a concave Lagrangian dual problem. For 2×2 matrices, there is no duality gap between a primal problem and its Lagrangian problem. Such a primal problem is motivated by the definition of column sufficiency.The author would like to thank Professor Richard W. Cottle for his helpful comments on earlier versions of this paper. The author would also like to thank an anonymous referee for numerous helpful comments on this paper. 相似文献
10.
Motivated by a certain situation in communication networks, we will investigate the M/M/1/∞ queuing system, where one can change the input stream. Performance criteria coincide with the long-run average throughput of the system and the queue length. We will present a rigorous mathematical study of the constrained version of the multicriteria optimization problem for jump Markov processes. Subsequently, it will be shown that the stationary control strategies of the threshold type form a sufficient class in the initial bicriteria problem considered. 相似文献