The Overlay of Minimization Diagrams in a Randomized Incremental Construction

In a randomized incremental construction of the minimization diagram of a collection of n hyperplanes in ℝ ^d , for d≥2, the hyperplanes are inserted one by one, in a random order, and the minimization diagram is updated after each insertion. We show that if we retain all the versions of the diagram, without removing any old feature that is now replaced by new features, the expected combinatorial complexity of the resulting overlay does not grow significantly. Specifically, this complexity is O(n ^⌊d/2⌋log n), for d odd, and O(n ^⌊d/2⌋), for d even. The bound is asymptotically tight in the worst case for d even, and we show that this is also the case for d=3. Several implications of this bound, mainly its relation to approximate halfspace range counting, are also discussed.     

Traversing a Set of Points with a Minimum Number of Turns

Given a finite set of points S in ℝ ^d , consider visiting the points in S with a polygonal path which makes a minimum number of turns, or equivalently, has the minimum number of segments (links). We call this minimization problem the minimum link spanning path problem. This natural problem has appeared several times in the literature under different variants. The simplest one is that in which the allowed paths are axis-aligned. Let L(S) be the minimum number of links of an axis-aligned path for S, and let G _n ^d be an n×…×n grid in ℤ ^d . Kranakis et al. (Ars Comb. 38:177–192, 1994) showed that L(G _n ²)=2n−1 and and conjectured that, for all d≥3, We prove the conjecture for d=3 by showing the lower bound for L(G _n ³). For d=4, we prove that For general d, we give new estimates on L(G _n ^d ) that are very close to the conjectured value. The new lower bound of improves previous result by Collins and Moret (Inf. Process. Lett. 68:317–319, 1998), while the new upper bound of differs from the conjectured value only in the lower order terms. For arbitrary point sets, we include an exact bound on the minimum number of links needed in an axis-aligned path traversing any planar n-point set. We obtain similar tight estimates (within 1) in any number of dimensions d. For the general problem of traversing an arbitrary set of points in ℝ ^d with an axis-aligned spanning path having a minimum number of links, we present a constant ratio (depending on the dimension d) approximation algorithm. Work by A. Dumitrescu was partially supported by NSF CAREER grant CCF-0444188. Work by F. Hurtado was partially supported by projects MECMTM2006-01267 and Gen. Cat. 2005SGR00692. Work by P. Valtr was partially supported by the project 1M0545 of the Ministry of Education of the Czech Republic.     

Outer Approximation Method Incorporating a Quadratic Approximation for a DC Programming Problem

In this paper, we propose an outer approximation method using two quadratic functions approximating the constraint functions of a DC programming problem. By analyzing the relation among the eigenvectors of the Hessian matrices of the constraint functions, the search direction for a feasible solution of the problem is determined. Moreover, to avoid line searches along similar directions, we incorporate a penalty function method in the algorithm.     

The Problem on Class Numbers of Quadratic Number Fields

It is a survey of the problem on class numbers of quadratic number fields.     

An Augmented Lagrangian Method for a Class of Inverse Quadratic Programming Problems

We consider an inverse quadratic programming (QP) problem in which the parameters in the objective function of a given QP problem are adjusted as little as possible so that a known feasible solution becomes the optimal one. We formulate this problem as a minimization problem with a positive semidefinite cone constraint and its dual is a linearly constrained semismoothly differentiable (SC¹) convex programming problem with fewer variables than the original one. We demonstrate the global convergence of the augmented Lagrangian method for the dual problem and prove that the convergence rate of primal iterates, generated by the augmented Lagrange method, is proportional to 1/r, and the rate of multiplier iterates is proportional to  $1/\sqrt{r}$ , where r is the penalty parameter in the augmented Lagrangian. As the objective function of the dual problem is a SC¹ function involving the projection operator onto the cone of symmetrically semi-definite matrices, the analysis requires extensive tools such as the singular value decomposition of matrices, an implicit function theorem for semismooth functions, and properties of the projection operator in the symmetric-matrix space. Furthermore, the semismooth Newton method with Armijo line search is applied to solve the subproblems in the augmented Lagrange approach, which is proven to have global convergence and local quadratic rate. Finally numerical results, implemented by the augmented Lagrangian method, are reported.     

Ergodic Type Bellman Equations of First Order with Quadratic Hamiltonian

We consider Bellman equations of ergodic type in first order. The Hamiltonian is quadratic on the first derivative of the solution. We study the structure of viscosity solutions and show that there exists a critical value among the solutions. It is proved that the critical value has the representation by the long time average of the kernel of the max-plus Schrödinger type semigroup. We also characterize the critical value in terms of an invariant density in max-plus sense, which can be understood as a counterpart of the characterization of the principal eigenvalue of the Schrödinger operator by an invariant measure.     

A Polynomial Number of Random Points Does Not Determine the Volume of a Convex Body

We show that there is no algorithm which, provided a polynomial number of random points uniformly distributed over a convex body in ℝ ⁿ , can approximate the volume of the body up to a constant factor with high probability.     

On the Number of Representations of Positive Integers by a Direct Sum of Binary Quadratic Forms with Discriminant −23

Explicit exact formulas are obtained for the number of representations of positive integers by some direct sums of quadratic forms and      

Magnetically-Induced Buckling of a Whirling Conducting Rod with Applications to Electrodynamic Space Tethers

We study the effect of a magnetic field on the behaviour of a slender conducting elastic structure, motivated by stability problems of electrodynamic space tethers. Both static (buckling) and dynamic (whirling) instability are considered and we also compute post-buckling configurations. The equations used are the geometrically exact Kirchhoff equations. Magnetic buckling of a welded rod is found to be described by a surprisingly degenerate bifurcation, which is unfolded when both transverse anisotropy of the rod and angular velocity are considered. By solving the linearised equations about the (quasi-) stationary solutions, we find various secondary instabilities. Our results are relevant for current designs of electrodynamic space tethers and potentially for future applications in nano- and molecular wires.     

The Binding Number of a Graph

The binding number of a graph is an important characteristic quantity of agraph.In1973 Woodall first introduced the concept of the binding number ofa graph and then gave the binding number of some special graphs in[1].In1981 Kane,Mohanty and Hales gave the binding number of some product graphsin[2].Wang Jianfang,Tian Songlin,Liu Ziuqiang(1983-1987)gave the bin-ding number of some multi-product graphs,and it is the limit character.Up to     

Note on the Pair-crossing Number and the Odd-crossing Number

The crossing number of a graph G is the minimum possible number of edge-crossings in a drawing of G, the pair-crossing number is the minimum possible number of crossing pairs of edges in a drawing of G, and the odd-crossing number is the minimum number of pairs of edges that cross an odd number of times. Clearly, . We construct graphs with . This improves the bound of Pelsmajer, Schaefer and Štefankovič. Our construction also answers an old question of Tutte. Slightly improving the bound of Valtr, we also show that if the pair-crossing number of G is k, then its crossing number is at most O(k ²/log ² k). G. Tóth’s research was supported by the Hungarian Research Fund grant OTKA-K-60427 and the Research Foundation of the City University of New York.     

The Norm of the Laplace Operator Restriction to a Homogeneous Polynomial Space

We investigate the restriction Δ _r,μ of the Laplace operator Δ onto the space of r-variate homogeneous polynomials F of degree μ. In the uniform norm on the unit ball of ℝ ^r , and with the corresponding operator norm, ‖Δ _r,μ F‖≤‖Δ _r,μ ‖⋅‖F‖ holds, where, for arbitrary F, the ‘constant’ ‖Δ _r,μ ‖ is the best possible. We describe ‖Δ _r,μ ‖ with the help of the family T _μ (σ x), , of scaled Chebyshev polynomials of degree μ. On the interval [−1,+1], they alternate at least (μ−1)-times, as the Zolotarev polynomials do, but they differ from them by their symmetry. We call them Zolotarev polynomials of the second kind, and calculate ‖Δ _r,μ ‖ with their help. We derive upper and lower bounds, as well as the asymptotics for μ→∞. For r≥5 and sufficiently large μ, we just get ‖Δ _r,μ ‖=(r−2)μ(μ−1). However, for 2≤r≤4 or lower values of μ, the result is more complicated. This gives the problem a particular flavor. Some Bessel functions and the φcot φ-expansion are involved.      

The effective application of a new approach to the generalized orienteering problem

The Orienteering Problem (OP) is an important problem in network optimization in which each city in a network is assigned a score and a maximum-score path from a designated start city to a designated end city is sought that is shorter than a pre-specified length limit. The Generalized Orienteering Problem (GOP) is a generalized version of the OP in which each city is assigned a number of scores for different attributes and the overall function to optimize is a function of these attribute scores. In this paper, the function used was a non-linear combination of attribute scores, making the problem difficult to solve. The GOP has a number of applications, largely in the field of routing. We designed a two-parameter iterative algorithm for the GOP, and computational experiments suggest that this algorithm performs as well as or better than other heuristics for the GOP in terms of solution quality while running faster. Further computational experiments suggest that our algorithm also outperforms the leading algorithm for solving the OP in terms of solution quality while maintaining a comparable solution speed.     

Exterior Differential Systems Prolongations and Application to a Study of Two Nonlinear Partial Differential Equations

A generalized Korteweg-de Vries equation is formulated as an exterior differential system, which is used to determine the prolongation structure of the equation. The prolongation structure is obtained for several cases of the variable powers, and nontrivial algebras are determined. The analysis is extended to a differential system which gives the Camassa-Holm equation as a particular case. The subject of conservation laws is briefly discussed for each of the equations. A Bäcklund transformation is determined using one of the prolongations.     

On the order of a non-abelian representation group of a slim dense near hexagon

In this paper we study the possible orders of a non-abelian representation group of a slim dense near hexagon. We prove that if the representation group R of a slim dense near hexagon S is non-abelian, then R is a 2-group of exponent 4 and |R|=2 ^β , 1+NPdim(S)≤β≤1+dimV(S), where NPdim(S) is the near polygon embedding dimension of S and dimV(S) is the dimension of the universal representation module V(S) of S. Further, if β=1+NPdim(S), then R is necessarily an extraspecial 2-group. In that case, we determine the type of the extraspecial 2-group in each case. We also deduce that the universal representation group of S is a central product of an extraspecial 2-group and an abelian 2-group of exponent at most 4. This work was partially done when B.K. Sahoo was a Research Fellow at the Indian Statistical Institute, Bangalore Center with NBHM fellowship, DAE Grant 39/3/2000-R&D-II, Govt. of India.     

An Important Property of the Weak Focus of a Quadratic Differential System

It was proved in [1] that the order of a weak focus of a quadratic differential system is at most3,i.e.,if v_1=v_3=v_5=v_7=0 in Bautin's symbol,then the critical point is a center.By using theDulac function method we prove in this paper that,if a quadratic differential system has two weakfoci,then each focus must be of order 1;and also a known result of L.A.Cherkas:under the aloveconditon no limit cycle can exist.     

Using dual techniques to derive componentwise and mixed condition numbers for a linear function of a linear least squares solution

We prove duality results for adjoint operators and product norms in the framework of Euclidean spaces. We show how these results can be used to derive condition numbers especially when perturbations on data are measured componentwise relatively to the original data. We apply this technique to obtain formulas for componentwise and mixed condition numbers for a linear function of a linear least squares solution. These expressions are closed when perturbations of the solution are measured using a componentwise norm or the infinity norm and we get an upper bound for the Euclidean norm.      

Generating uniform random vectors over a simplex with implications to the volume of a certain polytope and to multivariate extremes

A uniform random vector over a simplex is generated. An explicit expression for the first moment of its largest spacing is derived. The result is used in a proposed diagnostic tool which examines the validity of random number generators. It is then shown that the first moment of the largest uniform spacing is related to the dependence measure of random vectors following any extreme value distribution. The main result is proved by a geometric proof as well as by a probabilistic one.     

Estimates of Variation with Respect to a Set and Applications to Optimization Problems

A variational norm that plays a role in functional optimization and learning from data is investigated. For sets of functions obtained by varying some parameters in fixed-structure computational units (e.g., Gaussians with variable centers and widths), upper bounds on the variational norms associated with such units are derived. The results are applied to functional optimization problems arising in nonlinear approximation by variable-basis functions and in learning from data. They are also applied to the construction of minimizing sequences by an extension of the Ritz method.