A quadratic programming approach to the determination of an upper bound on the weighted stability number

In a previous work, the authors have introduced an upper bound on the stability number of a graph and several of its properties were given. The determination of this upper bound was done by a quadratic programming approach whose implementation has given good computational results. We now extend this bound to the weighted case, i.e., an upper bound on the weighted stability of an arbitrary graph with node weights is presented. Similarly to the non-weighted case, the deduced bound allows us to give a necessary and sufficient condition to a weighted graph that attains the given bound. Also a heuristic for determining the maximum weight stable set is proposed which is based on an integrality property of a convex quadratic problem that produces the bound. Some comments about the proposed approach will conclude the paper.     

The number of edges in a bipartite graph of given radius

Vizing established an upper bound on the size of a graph of given order and radius. We find a sharp upper bound on the size of a bipartite graph of given order and radius.     

Computation of differential Chow forms for ordinary prime differential ideals

In this paper, we propose algorithms for computing differential Chow forms for ordinary prime differential ideals which are given by characteristic sets. The algorithms are based on an optimal bound for the order of a prime differential ideal in terms of a characteristic set under an arbitrary ranking, which shows the Jacobi bound conjecture holds in this case. Apart from the order bound, we also give a degree bound for the differential Chow form. In addition, for a prime differential ideal given by a characteristic set under an orderly ranking, a much simpler algorithm is given to compute its differential Chow form. The computational complexity of the algorithms is single exponential in terms of the Jacobi number, the maximal degree of the differential polynomials in a characteristic set, and the number of variables.     

Radial sums of ridge functions: A characterization

We extend and sharpen the characterization of radial sums of ridge functions of two variables given in an earlier paper. More precisely, a bound on the degree of certain polynomials is given which depends on the angles between the ridges; not only is this bound best possible but also a converse result holds. Furthermore, variants of this characterization which hold for higher dimensional analogues are also given. These results are then applied to certain parallel am models in computed tomography to obtain more precise and otherwise improved characterizations of algorithms which commute with rigid motions.     

Bounds for the Homological Dimensions of Pullbacks

A new upper bound on the global dimension of a pullback ring is given, and Scrivanti's upper bound on the weak dimension of a pullback ring is generalized to the noncommutative case. Bibliography: 8 titles.     

On field extensions given by periods of Drinfeld modules

In this short note, we answer a question raised by M. Papikian on a universal upper bound for the degree of the extension of $$K_\infty $$ given by adjoining the periods of a Drinfeld module of rank 2. We show that contrary to the rank 1 case such a universal upper bound does not exist, and the proof generalies to higher rank. Moreover, we give an upper and lower bound for the extension degree depending on the valuations of the defining coefficients of the Drinfeld module. In particular, the lower bound shows the non-existence of a universal upper bound.     

Error bounds for nondifferentiable convex inequalities under a strong Slater constraint qualification

A global error bound is given on the distance between an arbitrary point in then-dimensional real spaceR ⁿ and its projection on a nonempty convex set determined bym convex, possibly nondifferentiable, inequalities. The bound is in terms of a natural residual that measures the violations of the inequalities multiplied by a new simple condition constant that embodies a single strong Slater constraint qualification (CQ) which implies the ordinary Slater CQ. A very simple bound on the distance to the projection relative to the distance to a point satisfying the ordinary Slater CQ is given first and then used to derive the principal global error bound. This material is based on research supported by National Science Foundation Grant CCR-9322479 and Air Force Office of Scientific Research grant F49620-97-1-0326.     

循环图圈空间的最小基

For most of circular graph the length of the minimum cycle basis is given.For the others a bound of the length of the minimum cycle basis is given and the given bound is reached.     

A Note on the Kissing Numbers of Superballs

The lower bounds for the translative kissing numbers of superballs are studied in this note. We improve the bound given by Larman and Zong. Furthermore, we give a constructive bound based on algebraic-geometry codes that also improves the bound by Larman and Zong in almost all cases.     

Bounds on the number of numerical semigroups of a given genus

Lower and upper bounds are given for the number n_g of numerical semigroups of genus g. The lower bound is the first known lower bound while the upper bound significantly improves the only known bound given by the Catalan numbers. In a previous work the sequence n_g is conjectured to behave asymptotically as the Fibonacci numbers. The lower bound proved in this work is related to the Fibonacci numbers and so the result seems to be in the direction to prove the conjecture. The method used is based on an accurate analysis of the tree of numerical semigroups and of the number of descendants of the descendants of each node depending on the number of descendants of the node itself.     

Two geometric inequalities for the torus

Given an arbitrary Riemannian metric on the torus, a sharp lower bound for the area and a sharp upper bound for the first eigenvalue of the Laplacian is given in terms of the primitive length spectrum.     

The number of additional singular points in the Riemann-Hilbert problem on a Riemann surface

We present an upper bound for the number of additional singular points that are sufficient to construct a system of linear equations with given regular singular points and a given monodromy on a Riemann surface.     

A note on multivariate Gaussian estimates

An upper bound of multivariate Gaussian probability for a general convex domain D is given based on a geometric observation. The bound is sharper than known ones on multivariate Mills' ratio in many cases.     

具有学习效应的超前有奖延误受罚的排序问题(英文)

本文考虑具有学习效应和共同交货期的单机排序问题.目标函数是加权超前有奖延误受罚总和.我们的目标是寻找一个最优序使得目标函数的值最小.由于该问题是NP-hard的,我们给出一些特殊情况下多项式时间可解的特例.同时在快速估计下界的基础上给出了分支定界算法来求一般情况下的最有排序.     

具有学习效应的超前有奖延误受罚的排序问题(英)

本文考虑具有学习效应和共同交货期的单机排序问题.目标函数是加权超前有奖延误受罚总和.我们的目标是寻找一个最优序使得目标函数的值最小.由于该问题是NP-hard的,我们给出一些特殊情况下多项式时间可解的特例.同时在快速估计下界的基础上给出了分支定界算法来求一般情况下的最有排序.     

A Subclass of Binary Goppa Codes With Improved Estimation of the Code Dimension

A new bound for the dimension of binary Goppa codes belonging to a specific subclass is given. This bound improves the well-known lower bound for Goppa codes.     

A lower bound for weighted completion time variance

We consider a single machine scheduling problem to minimize the weighted completion time variance. This problem is known to be NP-hard. We propose a heuristic and a lower bound based on job splitting and the Viswanathkumar and Srinivasan procedure. The test on more than 2000 instances shows that this lower bound is very tight and the heuristic yields solutions very close to optimal ones since the gap between the solution given by the heuristic and the lower bound is very small.     

A new line-search step based on the Weierstrass \wp-function for minimizing a class of logarithmic barrier functions

Summary. We define the notion of self-concordance of order two for the restriction of a logarithmic barrier function to a given line. Based on this notion we prove an inner approximation of the domain of , as well as a lower bound of the distance from a point $t$ to the minimum of . These results provide the theoretical tools to develop a simple and efficient search step for finding the minimum of the barrier function along a given line. The new bound on the size of the line-search step is better than the optimal bound known for the case of a self-concordant function (of order one). We conclude with some numerical examples that illustrate the promise of the new line-search step. Received May 24, 1993 / Revised version received February 1994     

The Minimum Number of Basic Feasible Solutions to a Transport Problem

In this paper, combinatorial arguments are used to derive a lower bound to the number of basic feasible solutions of a transport problem. A separate argument is given for degenerate and non-degenerate systems, and an example which attains the lower bound is given for each type.     

两个逆网络选址问题的计算复杂性

本文考虑两个我们称之为逆网络选址的改进问题,它们是修改网络上各个边的长度,分别使得网络上某个给定的顶点到网络上所有点的最大距离以及该点到其它顶点的距离之和不大于预先给定的上界,并且所做的修改总量最小.我们将证明这两个逆网络选址问题都是强NP困难的.