Optimally Computing the Shortest Weakly Visible Subedge of a Simple Polygon

Given ann-vertex simple polygonP, the problem of computing the shortest weakly visible subedge ofPis that of finding a shortest line segmentson the boundary ofPsuch thatPis weakly visible froms(ifsexists). In this paper, we present new geometric observations that are useful for solving this problem. Based on these geometric observations, we obtain optimal sequential and parallel algorithms for solving this problem. Our sequential algorithm runs inO(n) time, and our parallel algorithm runs inO(log n) time usingO(n/log n) processors in the CREW PRAM computational model. Using the previously best known sequential algorithms to solve this problem would takeO(n²) time. We also give geometric observations that lead to extremely simple and optimal algorithms for solving, both sequentially and in parallel, the case of this problem where the polygons are rectilinear.     

The Linear-Array Conjecture in Communication Complexity Is False

linear array network consists of k+1 processors with links only between and (0≤i<k). It is required to compute some boolean function f(x,y) in this network, where initially x is stored at and y is stored at . Let be the (total) number of bits that must be exchanged to compute f in worst case. Clearly, , where D(f) is the standard two-party communication complexity of f. Tiwari proved that for almost all functions and conjectured that this is true for all functions. In this paper we disprove Tiwari's conjecture, by exhibiting an infinite family of functions for which is essentially at most . Our construction also leads to progress on another major problem in this area: It is easy to bound the two-party communication complexity of any function, given the least number of monochromatic rectangles in any partition of the input space. How tight are such bounds? We exhibit certain functions, for which the (two-party) communication complexity is twice as large as the best lower bound obtainable this way. Received: March 1, 1996     

Packing Steiner trees: polyhedral investigations

LetG=(V, E) be a graph andT⊆V be a node set. We call an edge setS a Steiner tree forT ifS connects all pairs of nodes inT. In this paper we address the following problem, which we call the weighted Steiner tree packing problem. Given a graphG=(V, E) with edge weightsw _e , edge capacitiesc _e ,e∈E, and node setT ₁,…,T _N , find edge setsS ₁,…,S _N such that eachS _k is a Steiner tree forT _k , at mostc _e of these edge sets use edgee for eache∈E, and the sum of the weights of the edge sets is minimal. Our motivation for studying this problem arises from a routing problem in VLSI-design, where given sets of points have to be connected by wires. We consider the Steiner tree packing problem from a polyhedral point of view and define an associated polyhedron, called the Steiner tree packing polyhedron. The goal of this paper is to (partially) describe this polyhedron by means of inequalities. It turns out that, under mild assumptions, each inequality that defines a facet for the (single) Steiner tree polyhedron can be lifted to a facet-defining inequality for the Steiner tree packing polyhedron. The main emphasis of this paper lies on the presentation of so-called joint inequalities that are valid and facet-defining for this polyhedron. Inequalities of this kind involve at least two Steiner trees. The classes of inequalities we have found form the basis of a branch & cut algorithm. This algorithm is described in our companion paper (in this issue).     

Randomized k-server algorithms for growth-rate bounded graphs

The k-server problem is a fundamental online problem where k mobile servers should be scheduled to answer a sequence of requests for points in a metric space as to minimize the total movement cost. While the deterministic competitive ratio is at least k, randomized k-server algorithms have the potential of reaching o(k)-competitive ratios. Prior to this work only few specific cases of this problem were solved. For arbitrary metric spaces, this goal may be approached by using probabilistic metric approximation techniques. This paper gives the first results in this direction, obtaining o(k)-competitive ratio for a natural class of metric spaces, including d-dimensional grids, and wide range of k.     

Corrigendum to “Discrepancy principle for the dynamical systems method” [Communications in Nonlinear Science and Numerical Simulation 10 (2005) 95–101]

Consider an operator equation B(u) − f = 0 in a real Hilbert space. Let us call this equation ill-posed if the operator B′(u) is not boundedly invertible, and well-posed otherwise. The dynamical systems method (DSM) for solving this equation consists of a construction of a Cauchy problem, which has the following properties: (1) it has a global solution for an arbitrary initial data, (2) this solution tends to a limit as time tends to infinity, (3) the limit is the minimal-norm solution to the equation B(u) = f. A global convergence theorem is proved for DSM for equation B(u) − f = 0 with monotone operators B.     

Exchange rings having ideal-stable range one

In this paper, we introduce the notion of the ideal-stable range one condition for exchange rings. Some characterizations for this condition are given. Moreover, we show that, for an exchange ringR, ifI is an ideal ofR andR hasI-stable range one, then every regular square matrix overI is the product of an idempotent matrix and an invertible matrix overR, and admits a diagonal reduction.     

On the Prime Spectrum of X-Injective Modules

Let R be a commutative ring and M an R-module. The purpose of this article is to introduce a new class of modules over R called X-injective R-modules, where X is the prime spectrum of M. This class contains the family of top modules and that of weak multiplication modules properly. In this article our concern is to extend the properties of multiplication, weak multiplication, and top modules to this new class of modules. Furthermore, for a top module M, we study some conditions under which the prime spectrum of M is a spectral space for its Zariski topology.     

Automorphisms for Skew PBW Extensions and Skew Quantum Polynomial Rings

In this work, I study the automorphisms of skew PBW extensions and skew quantum polynomials. I use Artamonov's works as reference for getting the principal results about automorphisms for generic skew PBW extensions and generic skew quantum polynomials. In general, if I have an endomorphism on a generic skew PBW extension and there are some x _i , x _j , x _u such that the endomorphism is not zero on these elements and the principal coefficients are invertible, then endomorphisms act over x _i as a _i x _i for some a _i in the ring of coefficients. Of course, this is valid for quantum polynomial rings, with r = 0, as such Artamonov shows in his work. We use this result for giving some more general results for skew PBW extensions, using filtred-graded techniques. Finally, I use localization to characterize some class the endomorphisms and automorphisms for skew PBW extensions and skew quantum polynomials over Ore domains.     

On abelian quantum invariants of links in 3-manifolds

From a finite abelian group G, a quadratic form onG and an element in , we define a topological invariant of a pair(M,L) where is a closed oriented 3-manifold and L an oriented, framedn-component link inM. The main result consists in an explicit formula for this invariant, based on a reciprocity formula for Gauss sums, which features a special linking pairing. This pairing depends on both the quadratic form q and the linking pairing of M. A necessary and sufficient condition for the invariant to vanish is described in terms of a characteristic class for this pairing. We also discuss torsion spin-structures and related structures which appear in this context. Received May 13, 1998 / Accepted November 11, 1999 / Published online February 5, 2001     

On Exit and Ergodicity of the Spectrally One-Sided Lévy Process Reflected at Its Infimum

Consider a spectrally one-sided Lévy process X and reflect it at its past infimum I. Call this process Y. For spectrally positive X, Avram et al.(2) found an explicit expression for the law of the first time that Y=X–I crosses a finite positive level a. Here we determine the Laplace transform of this crossing time for Y, if X is spectrally negative. Subsequently, we find an expression for the resolvent measure for Y killed upon leaving [0,a]. We determine the exponential decay parameter for the transition probabilities of Y killed upon leaving [0,a], prove that this killed process is -positive and specify the -invariant function and measure. Restricting ourselves to the case where X has absolutely continuous transition probabilities, we also find the quasi-stationary distribution of this killed process. We construct then the process Y confined in [0,a] and prove some properties of this process.     

On the Order of Convergence of a Determinantal Family of Root-Finding Methods

Recently, we have shown that for each natural number m greater than one, and each natural number k less than or equal to m, there exists a root-finding iteration function, defined as the ratio of two determinants that depend on the first m - k derivatives of the given function. For each k the corresponding matrices are upper Hessenberg matrices. Additionally, for k = 1 these matrices are Toeplitz matrices. The goal of this paper is to analyze the order of convergence of this fundamental family. Newton's method, Halley's method, and their multi-point versions are members of this family. In this paper we also derive these special cases. We prove that for fixed m, as k increases, the order of convergence decreases from m to the positive root of the characteristic polynomial of generalized Fibonacci numbers of order m. For fixed k, the order of convergence increases in m. The asymptotic error constant is also derived in terms of special determinants.     

On the existence of unitarily invariant norm under some conditions

Let r ₁, …, r _m be positive real numbers and A ₁, …, A _m be n × n matrices with complex entries. In this article, we present a necessary and sufficient condition for the existence of a unitarily invariant norm ‖·‖, such that ‖A _i ‖ = r _i , for i = 1, …, m. Then we identify the greatest unitarily invariant norm which satisfies this condition. Using this, we get an approximation of unitarily invariant norms. Although the minimum unitarily invariant norm which satisfies this condition does not exist in general, we find conditions over A _i s and r _i s which are sufficient for the existence of such a norm. Finally, we get a characterization of unitarily invariant norms.     

LIMIT OF ITERATES FOR BERNSTEIN POLYNOMIALS DEFINED ON A TRIANGLE

Let f∈C[0,1],and Bn(f,x) be the a-th Bernstein polynomial associated with function f.ln 1967,the limit of iterates for B.(f,x) was given by Kelisky and Rivlin.After this,Many mathematicians studied and generalized this result.But anyway,all these discussions are only for univariate case ,In this paper,the main contrlbution is that the limit of lterates for Bernstein polynomial defined on a triangle is given completely.     

Interior-Point Algorithms for Semidefinite Programming Based on a Nonlinear Formulation

Recently in Burer et al. (Mathematical Programming A, submitted), the authors of this paper introduced a nonlinear transformation to convert the positive definiteness constraint on an n × n matrix-valued function of a certain form into the positivity constraint on n scalar variables while keeping the number of variables unchanged. Based on this transformation, they proposed a first-order interior-point algorithm for solving a special class of linear semidefinite programs. In this paper, we extend this approach and apply the transformation to general linear semidefinite programs, producing nonlinear programs that have not only the n positivity constraints, but also n additional nonlinear inequality constraints. Despite this complication, the transformed problems still retain most of the desirable properties. We propose first-order and second-order interior-point algorithms for this type of nonlinear program and establish their global convergence. Computational results demonstrating the effectiveness of the first-order method are also presented.     

A PTAS for the sparsest 2-spanner of 4-connected planar triangulations

A t-spanner of an undirected, unweighted graph G is a spanning subgraph of G with the added property that for every pair of vertices in G, the distance between them in is at most t times the distance between them in G. We are interested in finding a sparsest t-spanner, i.e., a t-spanner with the minimum number of edges. In the general setting, this problem is known to be NP-hard for all t2. For t5, the problem remains NP-hard for planar graphs, whereas for t{2,3,4}, the complexity of this problem on planar graphs is still unknown. In this paper we present a polynomial time approximation scheme for the problem of finding a sparsest 2-spanner of a 4-connected planar triangulation.     

Edges of the Barvinok–Novik Orbitope

Here we study the kth symmetric trigonometric moment curve and its convex hull, the Barvinok–Novik orbitope. In 2008, Barvinok and Novik introduced these objects and showed that there is some threshold so that for two points on \mathbb S¹\mathbb {S}^{1} with arclength below this threshold the line segment between their lifts to the curve forms an edge on the Barvinok–Novik orbitope, and for points with arclength above this threshold their lifts do not form an edge. They also gave a lower bound for this threshold and conjectured that this bound is tight. Results of Smilansky prove tightness for k=2. Here we prove this conjecture for all k.     

C 1 surface interpolation with constraints

Givenn pairwise distinct and arbitrarily spaced pointsP _i in a domainD of thex–y plane andn real numbersf _i, consider the problem of computing a bivariate functionf(x, y) of classC ¹ inD whose values inP _i are exactlyf _i,i=1,,n, and whose first or second order partial derivatives satisfy appropriate equality and inequality constraints on a given set ofp pointsQ _l inD.In this paper we present a method for solving the above problem, which is designed for extremely large data sets. A step of this method requires the solution of a large scale quadratic programming (QP) problem.The main purpose of this work is to analyse an iterative method for determining the solution of this QP problem: such a method is very efficient and well suited for parallel implementation on a multiprocessor system.Work supported by MURST Project of Computational Mathematics, Italy.     

The Bass Conjecture and Group von Neumann Algebras

The precise relationship between the Bass conjecture for the Hattori–Stallings trace for projective ZG-modules and the map from reduced K-theory of ZG to reduced K-theory of the von Neumann algebra, NG, of G, of G is determined. As a consequence it is shown this map is zero for all groups G. It is also shown that the map induced on K-theory from the inclusion of NG to the ring of closed, densely defined operators affiliated to NG is an isomorphism. Together with the above result, this gives some positive evidence for the validity of the Division Ring Conjecture for torsion free groups.     

On the Auslander–Reiten conjecture for Cohen–Macaulay rings and path algebras

In this note, it is shown that the validity of the Auslander–Reiten conjecture for a given d-dimensional Cohen–Macaulay local ring R depends on its validity for all direct summands of d-th syzygy of R-modules of finite length, provided R is an isolated singularity. Based on this result, it is shown that under a mild assumption on the base ring R, satisfying the Auslander–Reiten conjecture behaves well under completion and reduction modulo regular elements. In addition, it will turn out that, if R is a commutative Noetherian ring and 𝒬 a finite acyclic quiver, then the Auslander–Reiten conjecture holds true for the path algebra R𝒬, whenever so does R. Using this result, examples of algebras satisfying the Auslander–Reiten conjecture are presented.     

The Euler Class Group of a Noetherian Ring

For a commutative Noetherian ring A of finite Krull dimension containing the field of rational numbers, an Abelian group called the Euler class group is defined. An element of this group is attached to a projective A-module of rank = dim A and it is shown that the vanishing of this element is necessary and sufficient for P to split off a free summand of rank 1. As one of the applications of this result, it is shown that for any n-dimensional real affine domain, a projective module of rank n (with trivial determinant), all of whose generic sections have n generated vanishing ideals, necessarily splits off a free direct summand of rank 1.