Properties of the solutions of the Ginzburg-Landau equation on the bifurcation branch

Generalizing previous results of M. Comte and P. Mironescu, it is shown that for degree d large enough (such that ), there is a bifurcation branch in the set of the solutions of the Ginzburg-Landau equation, emanating from the branch of radial solutions at the critical value _d of the parameter. Moreover, the solutions on the bifurcation branch admit exactly d zeroes, and the energy on the bifurcation branch is strictly smaller than the energy on the radial branch.     

Doubly-Exponential Growth of the Number of Vectors of Multipilicities for Solutions of Systems of Polynomial

Earlier, D. Yu. Grigoriev and N. N. Vorob'yov obtained an upper bound for the number of vectors of multiplicities for solutions of systems of the form (assuming that the system has a finite number of solutions). In the system above, are polynomials of degrees . In the present paper, we show that the order of growth of this bound is close to the exact one. In particular, in the case d=n, the construction provides a doubly-exponential (in n) number of vectors of multiplicities. Bibliography: 4 titles.     

The Löwenheim—Skolem—Mal'tsev Theorem for ℍ\mathbb{F}-Structures

We deal with the problem asking whether hereditarily finite superstructures have elementary extensions of the form . In so doing, we settle the question whether a theory for some hereditarily finite superstructure have models of arbitrarily large cardinality. A Hanf number is shown to exist, and we provide an exact bound for the countable case.     

Two exact algorithms for the capacitated p-median problem

The p-median problem has been widely studied in combinatorial optimisation, but its generalisation to the capacitated case has not. We propose a branch and price algorithm, comparing it with a standard MIP solver and a branch and bound algorithm based on Lagrangean relaxation. We present computational experience, using test instances drawn from the literature and new instances with higher ratio between the number of medians p and the number of nodes N. The branch and price algorithm shows very good performances and computational time robustness in solving problems for any ratio.Received: December 2002, Revised: August 2003AMS classification: 90C10, 90C27     

AnO(nL) infeasible-interior-point algorithm for LCP with quadratic convergence

The Mizuno-Todd-Ye predictor-corrector algorithm for linear programming is extended for solving monotone linear complementarity problems from infeasible starting points. The proposed algorithm requires two matrix factorizations and at most three backsolves per iteration. Its computational complexity depends on the quality of the starting point. If the starting points are large enough, then the algorithm hasO(nL) iteration complexity. If a certain measure of feasibility at the starting point is small enough, then the algorithm has iteration complexity. At each iteration, both feasibility and optimality are reduced exactly at the same rate. The algorithm is quadratically convergent for problems having a strictly complementary solution, and therefore its asymptotic efficiency index is . A variant of the algorithm can be used to detect whether solutions with norm less than a given constant exist.This work was supported in part by the National Science Foundation under grant DMS-9305760.     

On the Relation of Σ-Reducibility Between Admissible Sets

Reducibility on admissible sets is studied which is a stronger version of the usual -presentability of models. One of its informal prototypes is the interpretability of one computational device in the other. We obtain criteria of reducibility for recursively listed and pure sets, introduce the notion of jump, and prove exact boundaries for the ordinals of jumps. We also show that this reducibility is lifted to -superstructures. Several results are proven on the relations of this reducibility to some known reducibilities.     

A BB&R algorithm for minimizing total tardiness on a single machine with sequence dependent setup times

This paper presents a Branch, Bound, and Remember (BB&R) exact algorithm using the Cyclic Best First Search (CBFS) exploration strategy for solving the ${1|ST_{sd}|\sum T_{i}}$ scheduling problem, a single machine scheduling problem with sequence dependent setup times where the objective is to find a schedule with minimum total tardiness. The BB&R algorithm incorporates memory-based dominance rules to reduce the solution search space. The algorithm creates schedules in the reverse direction for problems where fewer than half the jobs are expected to be tardy. In addition, a branch and bound algorithm is used to efficiently compute tighter lower bounds for the problem. This paper also presents a counterexample for a previously reported exact algorithm in Luo and Chu (Appl Math Comput 183(1):575–588, 2006) and Luo et?al. (Int J Prod Res 44(17):3367–3378, 2006). Computational experiments demonstrate that the algorithm is two orders of magnitude faster than the fastest exact algorithm that has appeared in the literature. Computational experiments on two sets of benchmark problems demonstrate that the CBFS search exploration strategy can be used as an effective heuristic on problems that are too large to solve to optimality.     

A Shifted-Barrier Primal-Dual Algorithm Model for Linearly Constrained Optimization Problems

In this paper we describe a Newton-type algorithm model for solving smooth constrained optimization problems with nonlinear objective function, general linear constraints and bounded variables. The algorithm model is based on the definition of a continuously differentiable exact merit function that follows an exact penalty approach for the box constraints and an exact augmented Lagrangian approach for the general linear constraints. Under very mild assumptions and without requiring the strict complementarity assumption, the algorithm model produces a sequence of pairs converging quadratically to a pair where satisfies the first order necessary conditions and is a KKT multipliers vector associated to the linear constraints. As regards the behaviour of the sequence x ^k alone, it is guaranteed that it converges at least superlinearly. At each iteration, the algorithm requires only the solution of a linear system that can be performed by means of conjugate gradient methods. Numerical experiments and comparison are reported.     

Analysis of the Xedni Calculus Attack

The xedni calculus attack on the elliptic curve discrete logarithm problem (ECDLP) involves lifting points from the finite field to the rational numbers and then constructing an elliptic curve over that passes through them. If the lifted points are linearly dependent, then the ECDLP is solved. Our purpose is to analyze the practicality of this algorithm. We find that asymptotically the algorithm is virtually certain to fail, because of an absolute bound on the size of the coefficients of a relation satisfied by the lifted points. Moreover, even for smaller values of p experiments show that the odds against finding a suitable lifting are prohibitively high.     

On Exact Constant in the Generalized Poincare Inequality

Some problems concerning an exact constant in the generalized Poincare inequality with are discussed. In particular, the conjecture that the extremal of this problem is symmetric is confirmed. Bibliography: 7 titles.     

Splitting along Submanifolds and L-Spectra

The problem of splitting of homotopy equivalence along a submanifold is closely related to surgeries of submanifolds and exact sequences in surgery theory. We describe possibilities and methods of application of -spectra for the investigation of the problem of splitting of (simple) homotopy equivalence of manifolds along submanifolds. This approach naturally leads us to commutative diagrams of exact sequences, which play an important role in calculational problems of surgery theory.     

An improved branch and bound algorithm for minimum concave cost network flow problems

This paper formulates the minimum concave cost network flow (MCCNF) problem as a mixed integer program and solves this program using a new branch and bound algorithm. The algorithm combines Driebeek's up and down penalties with a new technique referred to as the simple bound improvement (SBI) procedure. An efficient numerical method for the SBI procedure is described and computational results are presented which show that the SBI procedure reduces both the in-core storage and the CPU time required to solve the MCCNF problem. In fact, for problems with over 200 binary decision variables, the SBI procedure reduced the in-core storage by more than one-third and the CPU time by more than 40 percent.     

Lower Bounds on the State Complexity of Geometric Goppa Codes

We reinterpret the state space dimension equations for geometric Goppa codes. An easy consequence is that if deg then the state complexity of is equal to the Wolf bound. For deg , we use Clifford's theorem to give a simple lower bound on the state complexity of . We then derive two further lower bounds on the state space dimensions of in terms of the gonality sequence of . (The gonality sequence is known for many of the function fields of interest for defining geometric Goppa codes.) One of the gonality bounds uses previous results on the generalised weight hierarchy of and one follows in a straightforward way from first principles; often they are equal. For Hermitian codes both gonality bounds are equal to the DLP lower bound on state space dimensions. We conclude by using these results to calculate the DLP lower bound on state complexity for Hermitian codes.     

On higher order Bessel potentials

The solutions of the equation in , where are investigated, Bessel potentials of higher order are defined, and recurrence relations between these solutions and these Bessel potentials are obtained. It is also proved that these solutions and the solutions of , under certain conditions, are identical. Received: 6 November 2002     

A hybrid tabu search/branch & bound approach to solving the generalized assignment problem

A new approach for solving the generalized assignment problem (GAP) is proposed that combines the exact branch & bound approach with the heuristic strategy of tabu search (TS) to produce a hybrid algorithm for solving GAP. The algorithm described uses commercial software to solve sub-problems generated by the TS guiding strategy. The TS approach makes use of the concept of referent domain optimisation and introduces novel add/drop strategies. In addition, the linear programming relaxation of GAP that forms part of the branch & bound approach is itself helpful in suggesting which variables might take binary values. Computational results on benchmark test instances are presented and compared with results obtained by the standard branch & bound approach and also several other heuristic approaches from the literature. The results show the new algorithm performs competitively against the alternatives and is able to find some new best solutions for several benchmark instances.     

Optimal Scheduling of a Two-stage Hybrid Flow Shop

We present an exact branch-and-bound algorithm for the two-stage hybrid flow shop problem with multiple identical machines in each stage. The objective is to schedule a set of jobs so as to minimize the makespan. This is the first exact procedure which has been specifically designed for this strongly -hard problem. Among other features, our algorithm is based on the exact solution of identical parallel machine scheduling problems with heads and tails. We report the results of extensive computational experiments on instances which show that the proposed algorithm solves large-scale instances in moderate CPU time.     

Least-Square Fitting with Spheres

Fitting circles and spheres to given data in is at least relevant in computational metrology (Ref. 1) and reflectrometry (Ref. 2). A new descent algorithm, developed for circles in Ref. 3, is generalized to spheres. Numerical examples are given.     

One-Dimensional Topologically Nontrivial Solutions in the Skyrme Model

We consider the Skyrme model using the explicit parameterization of the rotation group through elements of its algebra. Topologically nontrivial solutions already arise in the one-dimensional case because the fundamental group of is . We explicitly find and analyze one-dimensional static solutions. Among them, there are topologically nontrivial solutions with finite energy. We propose a new class of projective models whose target spaces are arbitrary real projective spaces .     

Minihypers and Linear Codes Meeting the Griesmer Bound: Improvements to Results of Hamada, Helleseth and Maekawa

This article improves results of Hamada, Helleseth and Maekawa on minihypers in projective spaces and linear codes meeting the Griesmer bound.In [10,12],it was shown that any -minihyper, with , where , is the disjoint union of points, lines,..., -dimensional subspaces. For q large, we improve on this result by increasing the upper bound on non-square, to non-square, square, , and (4) for square, p prime, p<3, to . In the case q non-square, the conclusion is the same as written above; the minihyper is the disjoint union of subspaces. When q is square however, the minihyper is either the disjoint union of subspaces, or the disjoint union of subspaces and one subgeometry . For the coding-theoretical problem, our results classify the corresponding codes meeting the Griesmer bound.     

Die Jacobifelder zu Minimalflächen im ℝ3

Assume that x is a minimal surface in ³ of the topological type of a 2-ball. Then x is a critical point of the Dirichlet functional on a certain Banach manifold. We can define the space of Jacobi fields of x as the nullspace of the Hessian of at x. Let n(x) denote the dimension of this space and let (x) denote the total number of branch points of x. We show, that always n(x)2(x)+3, and that for almost all minimal surfaces equality holds. We can conclude, that all solutions of the classical Plateau problem, which have branch points in the interior and no branch points on the boundary, are degenerate critical points of the functional .