Associated primes and cofiniteness of local cohomology modules

Let be an ideal of Noetherian ring R and let s be a non-negative integer. Let M be an R-module such that is finite R-module. If s is the first integer such that the local cohomology module is non -cofinite, then we show that is finite. In particular, the set of associated primes of is finite. Let be a local Noetherian ring and let M be a finite R-module. We study the last integer n such that the local cohomology module is not -cofinite and show that n just depends on the support of M.The research of the first author was supported in part by a grant from IPM (No. 83130114).The second author was supported by a grant from University of Tehran (No. 6103023/1/01).     

The feasibility pump

In this paper we consider the NP-hard problem of finding a feasible solution (if any exists) for a generic MIP problem of the form min{c^Tx:Ax≥b,x_j integer ∀j ∈ }. Trivially, a feasible solution can be defined as a point x* ∈ P:={x:Ax≥b} that is equal to its rounding , where the rounded point is defined by := x*_j if j ∈ and := x*_j otherwise, and [·] represents scalar rounding to the nearest integer. Replacing “equal” with “as close as possible” relative to a suitable distance function Δ(x*, ), suggests the following Feasibility Pump (FP) heuristic for finding a feasible solution of a given MIP.We start from any x* ∈ P, and define its rounding . At each FP iteration we look for a point x* ∈ P that is as close as possible to the current by solving the problem min {Δ(x, ): x ∈ P}. Assuming Δ(x, ) is chosen appropriately, this is an easily solvable LP problem. If Δ(x*, )=0, then x* is a feasible MIP solution and we are done. Otherwise, we replace by the rounding of x*, and repeat.We report computational results on a set of 83 difficult 0-1 MIPs, using the commercial software ILOG-Cplex 8.1 as a benchmark. The outcome is that FP, in spite of its simple foundation, proves competitive with ILOG-Cplex both in terms of speed and quality of the first solution delivered. Interestingly, ILOG-Cplex could not find any feasible solution at the root node for 19 problems in our test-bed, whereas FP was unsuccessful in just 3 cases.     

Optimal 3-terminal cuts and linear programming

Given an undirected graph G=(V,E) and three specified terminal nodes t ₁,t ₂,t ₃, a 3-cut is a subset A of E such that no two terminals are in the same component of G\A. If a non-negative edge weight c _e is specified for each e∈E, the optimal 3-cut problem is to find a 3-cut of minimum total weight. This problem is -hard, and in fact, is max- -hard. An approximation algorithm having performance guarantee has recently been given by Călinescu, Karloff, and Rabani. It is based on a certain linear-programming relaxation, for which it is shown that the optimal 3-cut has weight at most times the optimal LP value. It is proved here that can be improved to , and that this is best possible. As a consequence, we obtain an approximation algorithm for the optimal 3-cut problem having performance guarantee . In addition, we show that is best possible for this algorithm. Research of this author was supported by NSERC PGSB. Research supported by a grant from NSERC of Canada.     

Greedy splitting algorithms for approximating multiway partition problems

Given a system (V,T,f,k), where V is a finite set, is a submodular function and k2 is an integer, the general multiway partition problem (MPP) asks to find a k-partition ={V₁,V₂,...,V_k} of V that satisfiesfor all i and minimizes f(V₁)+f(V₂)+···+f(V_k), where is a k-partition of hold. MPP formulation captures a generalization in submodular systems of many NP-hard problems such as k-way cut, multiterminal cut, target split and their generalizations in hypergraphs. This paper presents a simple and unified framework for developing and analyzing approximation algorithms for various MPPs.Mathematics Subject Classification (1991): 20E28, 20G40, 20C20Acknowledgement This research is partially supported by the Scientific Grant-in-Aid from Ministry of Education, Science, Sports and Culture of Japan. The authors would like to thank the anonymous referees for their valuable comments and suggestions.     

Fast convolution with radial kernels at nonequispaced knots

Summary. We develop a new algorithm for the fast evaluation of linear combinations of radial functions based on the recently developed fast Fourier transform at nonequispaced knots. For smooth kernels, e.g. the Gaussian, our algorithm requires arithmetic operations. In case of singular kernels an additional regularization procedure must be incorporated and the algorithm has the arithmetic complexity if either the points y_j or the points x_k are reasonably uniformly distributed. We prove error estimates to obtain clues about the choice of the involved parameters and present numerical examples for various singular and smooth kernels in two dimensions.Mathematics Subject Classification (2000): 65T40, 65T50, 65F30Revised version received December 3, 2003     

The volumetric barrier for convex quadratic constraints

Let where and _i is an n×n positive semidefinite matrix. We prove that the volumetric and combined volumetric-logarithmic barriers for are and self-concordant, respectively. Our analysis uses the semidefinite programming (SDP) representation for the convex quadratic constraints defining , and our earlier results on the volumetric barrier for SDP. The self-concordance results actually hold for a class of SDP problems more general than those corresponding to the SDP representation of .Mathematics Subject Classification (1991):90C25, 90C30     

A branch-and-cut algorithm for the stochastic uncapacitated lot-sizing problem

This paper addresses a multi-stage stochastic integer programming formulation of the uncapacitated lot-sizing problem under uncertainty. We show that the classical (ℓ,S) inequalities for the deterministic lot-sizing polytope are also valid for the stochastic lot-sizing polytope. We then extend the (ℓ,S) inequalities to a general class of valid inequalities, called the inequalities, and we establish necessary and sufficient conditions which guarantee that the inequalities are facet-defining. A separation heuristic for inequalities is developed and incorporated into a branch-and-cut algorithm. A computational study verifies the usefulness of the inequalities as cuts. This research has been supported in part by the National Science Foundation under Award number DMII-0121495.     

Topologically transitive extensions of bounded operators

Let X be any Banach space and T a bounded operator on X. An extension of the pair (X,T) consists of a Banach space in which X embeds isometrically through an isometry i and a bounded operator on such that When X is separable, it is additionally required that be separable. We say that is a topologically transitive extension of (X, T) when is topologically transitive on , i.e. for every pair of non-empty open subsets of there exists an integer n such that is non-empty. We show that any such pair (X,T) admits a topologically transitive extension , and that when H is a Hilbert space, (H,T) admits a topologically transitive extension where is also a Hilbert space. We show that these extensions are indeed chaotic.Mathematics Subject Classification (2000): 47 A 16     

Modified Ariki-Koike algebras and cyclotomic <Emphasis Type="Italic">q</Emphasis>-Schur algebras

The modified Ariki-Koike algebra is a variation of the original Ariki-Koike algebra over an integral domain R. When R is a rational function field over the independent parameters, But for general R, is not isomorphic to , and has a simpler structure than . In this paper, we construct a cellular basis of which has a similar property as the cellular basis of introduced by Dipper-James-Mathas. By comparing these two cellular bases, we obtain some estimate on the decomposition numbers of in terms of the decomposition numbers of . We also prove the integral form of the Schur-Weyl reciprocity between a certain quantum algebra U_q and on the tensor space      

Estimates for the -Neumann problem and nonexistence of C 2 Levi-flat hypersurfaces in

Let be a pseudoconvex domain with C² boundary in , n 2. We prove that the -Neumann operator N exists for square-integrable forms on . Furthermore, there exists a number ₀>0 such that the operators and the Bergman projection are regular in the Sobolev space W ( ) for <₀. The -Neumann operator is used to construct -closed extension on for forms on the boundary b. This gives solvability for the tangential Cauchy-Riemann operators on the boundary. Using these results, we show that there exist no non-zero L²-holomorphic (p, 0)-forms on any domain with C² pseudoconcave boundary in with p > 0 and n 2. As a consequence, we prove the nonexistence of C² Levi-flat hypersurfaces in .This paper is a revision of our preprint (May 2003) formerly titled Estimates for the -Neumann problem and nonexistence of Levi-flat hypersurfaces in where the nonexistence of C², Levi-flat hypersurfaces is proved for >0.All three authors are partially supported by NSF grants.An erratum to this article can be found at