共查询到20条相似文献,搜索用时 31 毫秒
1.
The paper is devoted to studying the Hoffman global error bound for convex quadratic/affine inequality/equality systems in the context of Banach spaces. We prove that the global error bound holds if the Hoffman local error bound is satisfied for each subsystem at some point of the solution set of the system under consideration. This result is applied to establishing the equivalence between the Hoffman error bound and the Abadie qualification condition, as well as a general version of Wang &; Pang's result [30], on error bound of Hölderian type. The results in the present paper generalize and unify recent works by Luo &; Luo in [17], Li in [16] and Wang &; Pang in [30]. 相似文献
2.
Etienne de Klerk Dmitrii Pasechnik Renata Sotirov Cristian Dobre 《Mathematical Programming》2012,136(2):253-278
We derive a new semidefinite programming bound for the maximum $k$ -section problem. For $k=2$ (i.e. for maximum bisection), the new bound is at least as strong as a well-known bound by Poljak and Rendl (SIAM J Optim 5(3):467?C487, 1995). For $k \ge 3$ the new bound dominates a bound of Karisch and Rendl (Topics in semidefinite and interior-point methods, 1998). The new bound is derived from a recent semidefinite programming bound by De Klerk and Sotirov for the more general quadratic assignment problem, but only requires the solution of a much smaller semidefinite program. 相似文献
3.
《Optimization》2012,61(5):691-704
In 1972 Christofides introduced a lower bound for the Traveling Salesman Problem (TSP). The bound is based on solving repeatedly a Linear Assignment Problem. We relate the bound to the Complete Cycle Problem; as a consequence the correctness of the bound is easier to prove. Further we give improvements for the bound in the symmetric case and we deal with the influence of the triangle equation together with the identification of non-optimal edges for the TSP. The improvements are illustrated by examples and computational results for large problems. 相似文献
4.
Juan Migliore Uwe Nagel Tim Rö mer 《Transactions of the American Mathematical Society》2008,360(6):2965-2985
The Multiplicity conjecture of Herzog, Huneke, and Srinivasan states an upper bound for the multiplicity of any graded -algebra as well as a lower bound for Cohen-Macaulay algebras. In this note we extend this conjecture in several directions. We discuss when these bounds are sharp, find a sharp lower bound in the case of not necessarily arithmetically Cohen-Macaulay one-dimensional schemes of 3-space, and propose an upper bound for finitely generated graded torsion modules. We establish this bound for torsion modules whose codimension is at most two.
5.
Several lower bounds have been proposed for the smallest singular value of a square matrix, such as Johnson’s bound, Brauer-type bound, Li’s bound and Ostrowski-type bound. In this paper, we focus on a bidiagonal matrix and investigate the equality conditions for these bounds. We show that the former three bounds give strict lower bounds if all the bidiagonal elements are non-zero. For the Ostrowski-type bound, we present an easily verifiable necessary and sufficient condition for the equality to hold. 相似文献
6.
Fatabbi G. 《Journal of Algebra》1994,170(3)
In this paper we determine a new upper bound for the regularity index of fat points of P2, without requiring any geometric condition on the points. This bound is intermediate between Segre′s bound, that holds for points in the general position, and the more general bound, that is attained when the points are collinear: in fact, both of these bounds can be recovered as particular cases. Furthermore, our bound cannot, in general, be sharpened: in fact, it is attained if there are either many collinear points or collinear points with high multiplicities. 相似文献
7.
We give an upper bound for the Stanley depth of the edge ideal of a complete k-partite hypergraph and as an application we give an upper bound for the Stanley depth of a monomial ideal in a polynomial ring S. We also give a lower and an upper bound for the cyclic module S/I associated to the complete k-partite hypergraph. 相似文献
8.
《偏微分方程通讯》2013,38(5-6):881-917
ABSTRACT We prove the appearance of an explicit lower bound on the solution to the full Boltzmann equation in the torus for a broad family of collision kernels including in particular long-range interaction models, under the assumption of some uniform bounds on some hydrodynamic quantities. This lower bound is independent of time and space. When the collision kernel satisfies Grad's cutoff assumption, the lower bound is a global Maxwellian and its asymptotic behavior in velocity is optimal, whereas for noncutoff collision kernels the lower bound we obtain decreases exponentially but faster than the Maxwellian. Our results cover solutions constructed in a spatially homogeneous setting, as well as small-time or close-to-equilibrium solutions to the full Boltzmann equation in the torus. The constants are explicit and depend on the a priori bounds on the solution. 相似文献
9.
We investigate a global complexity bound of the Levenberg–Marquardt Method (LMM) for nonsmooth equations. The global complexity
bound is an upper bound to the number of iterations required to get an approximate solution that satisfies a certain condition.
We give sufficient conditions under which the bound of the LMM for nonsmooth equations is the same as smooth cases. We also
show that it can be reduced under some regularity assumption. Furthermore, by applying these results to nonsmooth equations
equivalent to the nonlinear complementarity problem (NCP), we get global complexity bounds for the NCP. In particular, we
give a reasonable bound when the mapping involved in the NCP is a uniformly P-function. 相似文献
10.
Given a node-weighted connected graph and a subset of terminals, the problem node-weighted Steiner tree (NWST) seeks a lightest
tree connecting a given set of terminals in a node-weighted graph. While NWST in general graphs are as hard as Set Cover,
NWST restricted to unit-disk graphs (UDGs) admits constant-approximations. Recently, Zou et al. (Lecture notes in computer
science, vol 5165, COCOA, 2008, pp 278–285) showed that any μ-approximation algorithm for the classical edge-weighted Steiner tree problem can be used to produce 2.5 μ-approximation algorithm for NWST restricted to UDGs. With the best known approximation bound 1.55 for the classical Steiner
tree problem, they obtained an approximation bound 3.875 for NWST restricted to UDGs. In this paper, we present three approximation
algorithms for NWST restricted to UDGs, the k-Restricted Relative Greedy Algorithm whose approximation bound converges to 1 + ln 5 ≈ 2.61 as k → ∞, the 3-Restricted Greedy Algorithm with approximation bound
4\frac13{4\frac{1}{3}} , and the k-Restricted Variable Metric Algorithm whose approximation bound converges to 3.9334 as k → ∞. 相似文献
11.
Various methods have been used to obtain improvements of the Goppa lower bound for the minimum distance of an algebraic geometric code. The main methods divide into two categories, and all but a few of the known bounds are special cases of either the Lundell-McCullough floor bound or the Beelen order bound. The exceptions are recent improvements of the floor bound by Güneri, Stichtenoth, and Taskin, and by Duursma and Park, and of the order bound by Duursma and Park, and by Duursma and Kirov. In this paper, we provide short proofs for all floor bounds and most order bounds in the setting of the van Lint and Wilson AB method. Moreover, we formulate unifying theorems for order bounds and formulate the DP and DK order bounds as natural but different generalizations of the Feng-Rao bound for one-point codes. 相似文献
12.
Kinkar Ch. Das 《Linear algebra and its applications》2009,431(8):1340-2600
An upper bound on the maximal entry in the principal eigenvector of a symmetric nonnegative matrix with zero diagonal entries is investigated in [S. Zhao, Y. Hong, On the bounds of maximal entries in the principal eigenvector of symmetric nonnegative matrix, Linear Algebra Appl. 340 (2002) 245-252]. We obtain a sharp upper bound on the maximal entry ymaxp in the principal eigenvector of symmetric nonnegative matrix in terms of order, the spectral radius, the largest and the smallest diagonal entries of that matrix. Our bound is applicable for any symmetric nonnegative matrix and the upper bound of Zhao and Hong (2002) for the maximal entry ymaxp follows as a special case. Moreover, we find an upper bound on maximal entry in the principal eigenvector for the signless Laplacian matrix of a graph. 相似文献
13.
Hiroshi Nozaki 《Combinatorica》2011,31(6):725-737
A finite set X in the Euclidean space is called an s-inner product set if the set of the usual inner products of any two distinct points in X has size s. First, we give a special upper bound for the cardinality of an s-inner product set on concentric spheres. The upper bound coincides with the known lower bound for the size of a Euclidean
2s-design. Secondly, we prove the non-existence of 2- or 3-inner product sets on two concentric spheres attaining the upper
bound for any d>1. The efficient property needed to prove the upper bound for an s-inner product set gives the new concept, inside s-inner product sets. We characterize the most known tight Euclidean designs as inside s-inner product sets attaining the upper bound. 相似文献
14.
We study the convergence of GMRES for linear algebraic systems with normal matrices. In particular, we explore the standard
bound based on a min-max approximation problem on the discrete set of the matrix eigenvalues. This bound is sharp, i.e. it
is attainable by the GMRES residual norm. The question is how to evaluate or estimate the standard bound, and if it is possible
to characterize the GMRES-related quantities for which this bound is attained (worst-case GMRES). In this paper we completely
characterize the worst-case GMRES-related quantities in the next-to-last iteration step and evaluate the standard bound in
terms of explicit polynomials involving the matrix eigenvalues. For a general iteration step, we develop a computable lower
and upper bound on the standard bound. Our bounds allow us to study the worst-case GMRES residual norm as a function of the
eigenvalue distribution. For hermitian matrices the lower bound is equal to the worst-case residual norm. In addition, numerical
experiments show that the lower bound is generally very tight, and support our conjecture that it is to within a factor of
4/π of the actual worst-case residual norm. Since the worst-case residual norm in each step is to within a factor of the square
root of the matrix size to what is considered an “average” residual norm, our results are of relevance beyond the worst case.
This revised version was published online in July 2006 with corrections to the Cover Date. 相似文献
15.
Manouchehr Zaker 《Journal of Graph Theory》2008,58(2):110-122
In this article we first give an upper bound for the chromatic number of a graph in terms of its degrees. This bound generalizes and modifies the bound given in 11 . Next, we obtain an upper bound of the order of magnitude for the coloring number of a graph with small K2,t (as subgraph), where n is the order of the graph. Finally, we give some bounds for chromatic number in terms of girth and book size. These bounds improve the best known bound, in terms of order and girth, for the chromatic number of a graph when its girth is an even integer. © 2008 Wiley Periodicals, Inc. J Graph Theory 58:110–122, 2008 相似文献
16.
We introduce a new upper bound for the maximum-entropy sampling problem. Our bound is described as the solution of a linear
integer program. The bound depends on a partition of the underlying set of random variables. For the case in which each block
of the partition has bounded cardinality, we describe an efficient dynamic-programming algorithm to calculate the bound. For
the very special case in which the blocks have no more than two elements, we describe an efficient algorithm for calculating
the bound based on maximum-weight matching. This latter formulation has particular value for local-search procedures that
seek to find a good partition. We relate our bound to recent bounds of Hoffman, Lee and Williams. Finally, we report on the
results of some computational experiments.
Received: September 27, 2000 / Accepted: July 26, 2001 Published online: September 5, 2002
Key words. experimental design – design of experiments – entropy – maximum-entropy sampling – matching – integer program – spectral
bound – Fischer's inequality – branch-and-bound – dynamic programming
Mathematics Subject Classification (2000): 52B12, 90C10
Send offprint requests to: Jon Lee
Correspondence to: Jon Lee 相似文献
17.
It is well known that the linear knapsack problem with general integer variables (LKP) is NP-hard. In this paper we first introduce a special case of this problem and develop an O(n) algorithm to solve it. We then show how this algorithm can be used efficiently to obtain a lower bound for a general instance of LKP and prove that it is at least as good as the linear programming lower bound. We also present the results of a computational study that show that for certain classes of problems the proposed bound on average is tighter than other bounds proposed in the literature. 相似文献
18.
We investigate universal bounds on spherical codes and spherical
designs that could be obtained using Delsartes
linear programming methods. We
give a lower estimate for the LP upper bound on codes, and an
upper estimate for the LP lower bound on designs.
Specifically, when the distance of the code is fixed and the
dimension goes to infinity, the LP upper bound on codes is at least as
large as the average of the best known upper and lower bounds.
When the dimension n of the design is fixed, and the strength k
goes to infinity, the LP bound on designs turns out,
in conjunction with known lower bounds, to be proportional to kn-1. 相似文献
19.
《Communications in Nonlinear Science & Numerical Simulation》2011,16(9):3475-3485
In this paper numerical approximation for the m-membrane problem is considered. We make a change of variables that leads to a different expression of the quadratic functional that allows after discretizing the problem to reformulate it as finite dimensional bound constrained quadratic problem. To our knowledge this is the first paper on numerical approximation of the m-membrane problem. We reformulate the m-membrane problem as a bound constraint quadratic minimization problem. The bound constraint quadratic form is solved with the gradient projection method. 相似文献
20.
《Journal of Graph Theory》2018,88(1):146-153
For minimally k‐connected graphs on n vertices, Mader proved a tight lower bound for the number of vertices of degree k in dependence on n and k. Oxley observed 1981 that in many cases a considerably better bound can be given if is used as additional parameter, i.e. in dependence on m, n, and k. It was left open to determine whether Oxley's more general bound is best possible. We show that this is not the case, but give a closely related bound that deviates from a variant of Oxley's long‐standing one only for small values of m. We prove that this new bound is best possible. The bound contains Mader's bound as special case. 相似文献