ALBERT

All Library Books, journals and Electronic Records Telegrafenberg

X
feed icon rss

Your email was sent successfully. Check your inbox.

An error occurred while sending the email. Please try again.

Proceed reservation?

Export
Filter
  • Articles  (16,387)
  • Springer  (16,387)
  • Nature Publishing Group
  • 1995-1999  (15,041)
  • 1965-1969  (1,346)
  • Computer Science  (16,387)
Collection
  • Articles  (16,387)
Source
Keywords
Publisher
Years
Year
Journal
Topic
  • 1
    Electronic Resource
    Electronic Resource
    A numerical approach to optimization problems with variational inequality constraints (1995)
    Springer
    Mathematical programming 68 (1995), S. 105-130 
    Details
    ISSN: 1436-4646
    Keywords: primary 49B34 ; secondary 90C31 ; 93C30 ; Variational inequalities ; Sensitivity analysis ; Generalized Jacobian
    Source: Springer Online Journal Archives 1860-2000
    Topics: Computer Science , Mathematics
    Notes: Abstract Optimization problems with variational inequality constraints are converted to constrained minimization of a local Lipschitz function. To this minimization a non-differentiable optimization method is used; the required subgradients of the objective are computed by means of a special adjoint equation. Besides tests with some academic examples, the approach is applied to the computation of the Stackelberg—Cournot—Nash equilibria and to the numerical solution of a class of quasi-variational inequalities.
    Type of Medium: Electronic Resource
    URL: http://dx.doi.org/10.1007/BF01585759
    Location Call Number Expected Availability
    BibTip Others were also interested in ...
    Paper (German National Licenses)
    Fulltext
  • 2
    Electronic Resource
    Electronic Resource
    A cutting plane algorithm for convex programming that uses analytic centers (1995)
    Springer
    Mathematical programming 69 (1995), S. 1-43 
    Details
    ISSN: 1436-4646
    Keywords: Mathematical programming ; Cutting planes ; Analytic center
    Source: Springer Online Journal Archives 1860-2000
    Topics: Computer Science , Mathematics
    Notes: Abstract Anoracle for a convex setS ⊂ ℝ n accepts as input any pointz in ℝ n , and ifz ∈S, then it returns ‘yes’, while ifz ∉S, then it returns ‘no’ along with a separating hyperplane. We give a new algorithm that finds a feasible point inS in cases where an oracle is available. Our algorithm uses the analytic center of a polytope as test point, and successively modifies the polytope with the separating hyperplanes returned by the oracle. The key to establishing convergence is that hyperplanes judged to be ‘unimportant’ are pruned from the polytope. If a ball of radius 2−L is contained inS, andS is contained in a cube of side 2 L+1, then we can show our algorithm converges after O(nL 2) iterations and performs a total of O(n 4 L 3+TnL 2) arithmetic operations, whereT is the number of arithmetic operations required for a call to the oracle. The bound is independent of the number of hyperplanes generated in the algorithm. An important application in which an oracle is available is minimizing a convex function overS.
    Type of Medium: Electronic Resource
    URL: http://dx.doi.org/10.1007/BF01585551
    Location Call Number Expected Availability
    BibTip Others were also interested in ...
    Paper (German National Licenses)
    Fulltext
  • 3
    Electronic Resource
    Electronic Resource
    A cutting plane method from analytic centers for stochastic programming (1995)
    Springer
    Mathematical programming 69 (1995), S. 45-73 
    Details
    ISSN: 1436-4646
    Keywords: Cutting plane ; Stochastic programming ; Analytic center ; Interior-point method
    Source: Springer Online Journal Archives 1860-2000
    Topics: Computer Science , Mathematics
    Notes: Abstract The stochastic linear programming problem with recourse has a dual block-angular structure. It can thus be handled by Benders' decomposition or by Kelley's method of cutting planes; equivalently the dual problem has a primal block-angular structure and can be handled by Dantzig-Wolfe decomposition—the two approaches are in fact identical by duality. Here we shall investigate the use of the method of cutting planes from analytic centers applied to similar formulations. The only significant difference form the aforementioned methods is that new cutting planes (or columns, by duality) will be generated not from the optimum of the linear programming relaxation, but from the analytic center of the set of localization.
    Type of Medium: Electronic Resource
    URL: http://dx.doi.org/10.1007/BF01585552
    Location Call Number Expected Availability
    BibTip Others were also interested in ...
    Paper (German National Licenses)
    Fulltext
  • 4
    Electronic Resource
    Electronic Resource
    A continuation method for monotone variational inequalities (1995)
    Springer
    Mathematical programming 69 (1995), S. 237-253 
    Details
    ISSN: 1436-4646
    Keywords: Variational inequality ; Nonlinear complementarity ; Nonlinear programming ; Continuation method
    Source: Springer Online Journal Archives 1860-2000
    Topics: Computer Science , Mathematics
    Notes: Abstract This paper presents a continuation method for monotone variational inequality problems based on a new smooth equation formulation. The existence, uniqueness and limiting behavior of the path generated by the method are analyzed.
    Type of Medium: Electronic Resource
    URL: http://dx.doi.org/10.1007/BF01585559
    Location Call Number Expected Availability
    BibTip Others were also interested in ...
    Paper (German National Licenses)
    Fulltext
  • 5
    Electronic Resource
    Electronic Resource
    About strongly polynomial time algorithms for quadratic optimization over submodular constraints (1995)
    Springer
    Mathematical programming 69 (1995), S. 269-309 
    Details
    ISSN: 1436-4646
    Keywords: Quadratic programming ; Submodular constraints ; Kuhn-Tucker conditions ; Lexicographically optimal flow ; Parametric maximum flow
    Source: Springer Online Journal Archives 1860-2000
    Topics: Computer Science , Mathematics
    Notes: Abstract We present new strongly polynomial algorithms for special cases of convex separable quadratic minimization over submodular constraints. The main results are: an O(NM log(N 2/M)) algorithm for the problemNetwork defined on a network onM arcs andN nodes; an O(n logn) algorithm for thetree problem onn variables; an O(n logn) algorithm for theNested problem, and a linear time algorithm for theGeneralized Upper Bound problem. These algorithms are the best known so far for these problems. The status of the general problem and open questions are presented as well.
    Type of Medium: Electronic Resource
    URL: http://dx.doi.org/10.1007/BF01585561
    Location Call Number Expected Availability
    BibTip Others were also interested in ...
    Paper (German National Licenses)
    Fulltext
  • 6
    Electronic Resource
    Electronic Resource
    Worst-case comparison of valid inequalities for the TSP (1995)
    Springer
    Mathematical programming 69 (1995), S. 335-349 
    Details
    ISSN: 1436-4646
    Keywords: Polyhedral combinatorics ; Valid inequalities ; Travelling salesman ; Worst-case analysis
    Source: Springer Online Journal Archives 1860-2000
    Topics: Computer Science , Mathematics
    Notes: Abstract We consider most of the known classes of valid inequalities for the graphical travelling salesman polyhedron and compute the worst-case improvement resulting from their addition to the subtour polyhedron. For example, we show that the comb inequalities cannot improve the subtour bound by a factor greater than 10/9. The corresponding factor for the class of clique tree inequalities is 8/7, while it is 4/3 for the path configuration inequalities.
    Type of Medium: Electronic Resource
    URL: http://dx.doi.org/10.1007/BF01585563
    Location Call Number Expected Availability
    BibTip Others were also interested in ...
    Paper (German National Licenses)
    Fulltext
  • 7
    Electronic Resource
    Electronic Resource
    Solution of and bounding in a linearly constrained optimization problem with convex, polyhedral objective function (1995)
    Springer
    Mathematical programming 70 (1995), S. 1-16 
    Details
    ISSN: 1436-4646
    Keywords: Stochastic programming ; Polyhedral functions ; Simplicial functions
    Source: Springer Online Journal Archives 1860-2000
    Topics: Computer Science , Mathematics
    Notes: Abstract A dual method is presented to solve a linearly constrained optimization problem with convex, polyhedral objective function, along with a fast bounding technique, for the optimum value. The method can be used to solve problems, obtained from LPs, where some of the constraints are not required to be exactly satisfied but are penalized by piecewise linear functions, which are added to the objective function of the original problem. The method generalizes an earlier solution technique developed by Prékopa (1990). Applications to stochastic programming are also presented.
    Type of Medium: Electronic Resource
    URL: http://dx.doi.org/10.1007/BF01585925
    Location Call Number Expected Availability
    BibTip Others were also interested in ...
    Paper (German National Licenses)
    Fulltext
  • 8
    Electronic Resource
    Electronic Resource
    The curvature integral and the complexity of linear complementarity problems (1995)
    Springer
    Mathematical programming 70 (1995), S. 107-122 
    Details
    ISSN: 1436-4646
    Keywords: Linear complementarity problem ; Predictor—corrector algorithm ; Complexity analysis ; Central trajectory ; Curvature integral ; Interior-point methods
    Source: Springer Online Journal Archives 1860-2000
    Topics: Computer Science , Mathematics
    Notes: Abstract In this paper, we propose a predictor—corrector-type algorithm for solving the linear complementarity problem (LCP), and prove that the actual number of iterations needed by the algorithm is bounded from above and from below by a curvature integral along the central trajectory of the problem. This curvature integral is not greater than, and possibly smaller than, the best upper bound obtained in the literature to date.
    Type of Medium: Electronic Resource
    URL: http://dx.doi.org/10.1007/BF01585931
    Location Call Number Expected Availability
    BibTip Others were also interested in ...
    Paper (German National Licenses)
    Fulltext
  • 9
    Electronic Resource
    Electronic Resource
    Directional derivatives of the solution of a parametric nonlinear program (1995)
    Springer
    Mathematical programming 70 (1995), S. 159-172 
    Details
    ISSN: 1436-4646
    Keywords: Parametric nonlinear programming ; Directional differentiability ; B-derivative ; Piecewise smooth function ; Nonunique multipliers ; Degeneracy
    Source: Springer Online Journal Archives 1860-2000
    Topics: Computer Science , Mathematics
    Notes: Abstract Consider a parametric nonlinear optimization problem subject to equality and inequality constraints. Conditions under which a locally optimal solution exists and depends in a continuous way on the parameter are well known. We show, under the additional assumption of constant rank of the active constraint gradients, that the optimal solution is actually piecewise smooth, hence B-differentiable. We show, for the first time to our knowledge, a practical application of quadratic programming to calculate the directional derivative in the case when the optimal multipliers are not unique.
    Type of Medium: Electronic Resource
    URL: http://dx.doi.org/10.1007/BF01585934
    Location Call Number Expected Availability
    BibTip Others were also interested in ...
    Paper (German National Licenses)
    Fulltext
  • 10
    Electronic Resource
    Electronic Resource
    On the equivalence of nonlinear complementarity problems and least-element problems (1995)
    Springer
    Mathematical programming 70 (1995), S. 191-200 
    Details
    ISSN: 1436-4646
    Keywords: Strictly pseudomonotone map ; Z-map ; Complementarity problem ; Least element problem
    Source: Springer Online Journal Archives 1860-2000
    Topics: Computer Science , Mathematics
    Notes: Abstract Strictly pseudomonotoneZ-maps operating on Banach lattices are considered. Equivalence of complementarity problems and least-element problems is established under certain regularity and growth conditions. This extends a recent result by Riddell (1981) for strictly monotoneZ-maps to the pseudomonotone case. Some other problems equivalent to the above are discussed as well.
    Type of Medium: Electronic Resource
    URL: http://dx.doi.org/10.1007/BF01585936
    Location Call Number Expected Availability
    BibTip Others were also interested in ...
    Paper (German National Licenses)
    Fulltext
  • 11
    Electronic Resource
    Electronic Resource
    Primal—dual methods for linear programming (1995)
    Springer
    Mathematical programming 70 (1995), S. 251-277 
    Details
    ISSN: 1436-4646
    Keywords: Linear programming ; Barrier methods ; Interior-point methods
    Source: Springer Online Journal Archives 1860-2000
    Topics: Computer Science , Mathematics
    Notes: Abstract Many interior-point methods for linear programming are based on the properties of the logarithmic barrier function. After a preliminary discussion of the convergence of the (primal) projected Newton barrier method, three types of barrier method are analyzed. These methods may be categorized as primal, dual and primal—dual, and may be derived from the application of Newton's method to different variants of the same system of nonlinear equations. A fourth variant of the same equations leads to a new primal—dual method. In each of the methods discussed, convergence is demonstrated without the need for a nondegeneracy assumption or a transformation that makes the provision of a feasible point trivial. In particular, convergence is established for a primal—dual algorithm that allows a different step in the primal and dual variables and does not require primal and dual feasibility. Finally, a new method for treating free variables is proposed.
    Type of Medium: Electronic Resource
    URL: http://dx.doi.org/10.1007/BF01585940
    Location Call Number Expected Availability
    BibTip Others were also interested in ...
    Paper (German National Licenses)
    Fulltext
  • 12
    Electronic Resource
    Electronic Resource
    The fleet assignment problem: Solving a large-scale integer program (1995)
    Springer
    Mathematical programming 70 (1995), S. 211-232 
    Details
    ISSN: 1436-4646
    Keywords: Linear programming ; Mixed-integer programming ; Large-scale optimization ; Airline fleet assignment
    Source: Springer Online Journal Archives 1860-2000
    Topics: Computer Science , Mathematics
    Notes: Abstract Given a flight schedule and set of aircraft, the fleet assignment problem is to determine which type of aircraft should fly each flight segment. This paper describes a basic daily, domestic fleet assignment problem and then presents chronologically the steps taken to solve it efficiently. Our model of the fleet assignment problem is a large multi-commodity flow problem with side constraints defined on a time-expanded network. These problems are often severely degenerate, which leads to poor performance of standard linear programming techniques. Also, the large number of integer variables can make finding optimal integer solutions difficult and time-consuming. The methods used to attack this problem include an interior-point algorithm, dual steepest edge simplex, cost perturbation, model aggregation, branching on set-partitioning constraints and prioritizing the order of branching. The computational results show that the algorithm finds solutions with a maximum optimality gap of 0.02% and is more than two orders of magnitude faster than using default options of a standard LP-based branch-and-bound code.
    Type of Medium: Electronic Resource
    URL: http://dx.doi.org/10.1007/BF01585938
    Location Call Number Expected Availability
    BibTip Others were also interested in ...
    Paper (German National Licenses)
    Fulltext
  • 13
    Electronic Resource
    Electronic Resource
    An interior-proximal method for convex linearly constrained problems and its extension to variational inequalities (1995)
    Springer
    Mathematical programming 71 (1995), S. 77-100 
    Details
    ISSN: 1436-4646
    Keywords: Convex linearly constrained problems ; Variational inequalities ; Interior methods ; Entropy-like proximal method ; Maximal monotone operator
    Source: Springer Online Journal Archives 1860-2000
    Topics: Computer Science , Mathematics
    Notes: Abstract In this paper, an entropy-like proximal method for the minimization of a convex function subject to positivity constraints is extended to an interior algorithm in two directions. First, to general linearly constrained convex minimization problems and second, to variational inequalities on polyhedra. For linear programming, numerical results are presented and quadratic convergence is established.
    Type of Medium: Electronic Resource
    URL: http://dx.doi.org/10.1007/BF01592246
    Location Call Number Expected Availability
    BibTip Others were also interested in ...
    Paper (German National Licenses)
    Fulltext
  • 14
    Electronic Resource
    Electronic Resource
    One-third-integrality in the max-cut problem (1995)
    Springer
    Mathematical programming 71 (1995), S. 29-50 
    Details
    ISSN: 1436-4646
    Keywords: Max-cut ; Cut polytope ; Metric polytope ; Linear relaxation ; One-third-integrality ; Box one-third-integrality ; Forbidden minor
    Source: Springer Online Journal Archives 1860-2000
    Topics: Computer Science , Mathematics
    Notes: Abstract Given a graphG = (V, E), the metric polytopeS (G) is defined by the inequalitiesx(F) − x(C∖F) ⩽ |F| − 1 for $$F \subseteq C$$ , |F| odd,C cycle ofG, and 0 ⩽x e ⩽ 1 fore ∈ E. Optimization overS (G) provides an approximation for the max-cut problem. The graphG is called 1/d-integral if all the vertices ofS(G) have their coordinates in{i/d ∣ 0 ⩽ i ⩽ d}. We prove that the class of 1/d-integral graphs is closed under minors, and we present several minimal forbidden minors for 1/3-integrality. In particular, we characterize the 1/3-integral graphs on seven nodes. We study several operations preserving 1/d-integrality, in particular, thek-sum operation for 0 ⩽k ⩽ 3. We prove that series parallel graphs are characterized by the following stronger property. All vertices of the polytopeS (G) ∩ {x ∣ ℓ ⩽ x ⩽ u} are 1/3-integral for every choice of 1/3-integral boundsℓ, u on the edges ofG.
    Type of Medium: Electronic Resource
    URL: http://dx.doi.org/10.1007/BF01592243
    Location Call Number Expected Availability
    BibTip Others were also interested in ...
    Paper (German National Licenses)
    Fulltext
  • 15
    Electronic Resource
    Electronic Resource
    On minquantile and maxcovering optimisation (1995)
    Springer
    Mathematical programming 71 (1995), S. 101-112 
    Details
    ISSN: 1436-4646
    Keywords: Minmax ; Maximal covering problems ; Multi criteria decision-making
    Source: Springer Online Journal Archives 1860-2000
    Topics: Computer Science , Mathematics
    Notes: Abstract In this paper we introduce the parametric minquantile problem, a weighted generalisation ofkth maximum minimisation. It is shown that, under suitable quasiconvexity assumptions, its resolution can be reduced to solving a polynomial number of minmax problems. It is also shown how this simultaneously solves (parametric) maximal covering problems. It follows that bicriteria problems, where the aim is to both maximize the covering and minimize the cover-level, are reducible to a discrete problem, on which any multiple criteria method may be applied.
    Type of Medium: Electronic Resource
    URL: http://dx.doi.org/10.1007/BF01592247
    Location Call Number Expected Availability
    BibTip Others were also interested in ...
    Paper (German National Licenses)
    Fulltext
  • 16
    Electronic Resource
    Electronic Resource
    The Fermat—Weber location problem revisited (1995)
    Springer
    Mathematical programming 71 (1995), S. 71-76 
    Details
    ISSN: 1436-4646
    Keywords: Location theory ; Fermat—Weber problem ; Weiszfeld's iterative algorithm
    Source: Springer Online Journal Archives 1860-2000
    Topics: Computer Science , Mathematics
    Notes: Abstract The Fermat—Weber location problem requires finding a point in ℝ N that minimizes the sum of weighted Euclidean distances tom given points. A one-point iterative method was first introduced by Weiszfeld in 1937 to solve this problem. Since then several research articles have been published on the method and generalizations thereof. Global convergence of Weiszfeld's algorithm was proven in a seminal paper by Kuhn in 1973. However, since them given points are singular points of the iteration functions, convergence is conditional on none of the iterates coinciding with one of the given points. In addressing this problem, Kuhn concluded that whenever them given points are not collinear, Weiszfeld's algorithm will converge to the unique optimal solution except for a denumerable set of starting points. As late as 1989, Chandrasekaran and Tamir demonstrated with counter-examples that convergence may not occur for continuous sets of starting points when the given points are contained in an affine subspace of ℝ N . We resolve this open question by proving that Weiszfeld's algorithm converges to the unique optimal solution for all but a denumerable set of starting points if, and only if, the convex hull of the given points is of dimensionN.
    Type of Medium: Electronic Resource
    URL: http://dx.doi.org/10.1007/BF01592245
    Location Call Number Expected Availability
    BibTip Others were also interested in ...
    Paper (German National Licenses)
    Fulltext
  • 17
    Electronic Resource
    Electronic Resource
    An efficient cost scaling algorithm for the assignment problem (1995)
    Springer
    Mathematical programming 71 (1995), S. 153-177 
    Details
    ISSN: 1436-4646
    Keywords: Network optimization ; Assignment problem ; Algorithms ; Experimental evaluation ; Cost scaling
    Source: Springer Online Journal Archives 1860-2000
    Topics: Computer Science , Mathematics
    Notes: Abstract The cost scaling push-relabel method has been shown to be efficient for solving minimum-cost flow problems. In this paper we apply the method to the assignment problem and investigate implementations of the method that take advantage of assignment's special structure. The results show that the method is very promising for practical use.
    Type of Medium: Electronic Resource
    URL: http://dx.doi.org/10.1007/BF01585996
    Location Call Number Expected Availability
    BibTip Others were also interested in ...
    Paper (German National Licenses)
    Fulltext
  • 18
    Electronic Resource
    Electronic Resource
    Superfluous matrices in linear complementarity (1995)
    Springer
    Mathematical programming 71 (1995), S. 195-206 
    Details
    ISSN: 1436-4646
    Keywords: Superfluous matrix ; Linear complementarity problem
    Source: Springer Online Journal Archives 1860-2000
    Topics: Computer Science , Mathematics
    Notes: Abstract Superfluous matrices were introduced by Howe (1983) in linear complementarity. In general, producing examples of this class is tedious (a few examples can be found in Chapter 6 of Cottle, Pang and Stone (1992)). To overcome this problem, we define a new class of matrices $$\bar Z$$ and establish that in $$\bar Z$$ superfluous matrices of any ordern ⩾ 4 can easily be constructed. For every integerk, an example of a superfluous matrix of degreek is exhibited in the end.
    Type of Medium: Electronic Resource
    URL: http://dx.doi.org/10.1007/BF01585998
    Location Call Number Expected Availability
    BibTip Others were also interested in ...
    Paper (German National Licenses)
    Fulltext
  • 19
    Electronic Resource
    Electronic Resource
    Balanced 0, ±1-matrices, bicoloring and total dual integrality (1995)
    Springer
    Mathematical programming 71 (1995), S. 249-258 
    Details
    ISSN: 1436-4646
    Keywords: Combinatorial optimization ; Integrality of polyhedra ; Generalized set packing ; Covering
    Source: Springer Online Journal Archives 1860-2000
    Topics: Computer Science , Mathematics
    Notes: Abstract A 0, ±1-matrixA is balanced if, in every submatrix with two nonzero entries per row and column, the sum of the entries is a multiple of four. This definition was introduced by Truemper (1978) and generalizes the notion of a balanced 0, 1-matrix introduced by Berge (1970). In this paper, we extend a bicoloring theorem of Berge (1970) and total dual integrality results of Fulkerson, Hoffman and Oppenheim (1974) to balanced 0, ±1-matrices.
    Type of Medium: Electronic Resource
    URL: http://dx.doi.org/10.1007/BF01590956
    Location Call Number Expected Availability
    BibTip Others were also interested in ...
    Paper (German National Licenses)
    Fulltext
  • 20
    Electronic Resource
    Electronic Resource
    A note on locally Lipschitzian functions (1995)
    Springer
    Mathematical programming 71 (1995), S. 369-370 
    Details
    ISSN: 1436-4646
    Keywords: Local Lipschitz property ; Infinite-dimensional Hilbert space
    Source: Springer Online Journal Archives 1860-2000
    Topics: Computer Science , Mathematics
    Notes: Abstract An oversight in a paper of Correa and Lemaréchal (this journal, 1993) is noted; a counterexample is given.
    Type of Medium: Electronic Resource
    URL: http://dx.doi.org/10.1007/BF01590961
    Location Call Number Expected Availability
    BibTip Others were also interested in ...
    Paper (German National Licenses)
    Fulltext
  • 21
    Electronic Resource
    Electronic Resource
    Strongly polynomial dual simplex methods for the maximum flow problem (1998)
    Springer
    Mathematical programming 80 (1998), S. 17-33 
    Details
    ISSN: 1436-4646
    Keywords: Dual simplex method ; Maximum flow ; Strongly polynomial ; Preflow algorithm ; Valid distance labels
    Source: Springer Online Journal Archives 1860-2000
    Topics: Computer Science , Mathematics
    Notes: Abstract This paper presents dual network simplex algorithms that require at most 2nm pivots and O(n 2 m) time for solving a maximum flow problem on a network ofn nodes andm arcs. Refined implementations of these algorithms and a related simplex variant that is not strictly speaking a dual simplex algorithm are shown to have a complexity of O(n 3). The algorithms are based on the concept of apreflow and depend upon the use of node labels that are underestimates of the distances from the nodes to the sink node in the extended residual graph associated with the current flow. © 1998 The Mathematical Programming Society, Inc. Published by Elsevier Science B.V.
    Type of Medium: Electronic Resource
    URL: http://dx.doi.org/10.1007/BF01582129
    Location Call Number Expected Availability
    BibTip Others were also interested in ...
    Paper (German National Licenses)
    Fulltext
  • 22
    Electronic Resource
    Electronic Resource
    Partitioning mathematical programs for parallel solution (1998)
    Springer
    Mathematical programming 80 (1998), S. 35-61 
    Details
    ISSN: 1436-4646
    Keywords: Graph partitioning ; Linear programming ; Bundle method ; Parallel optimization
    Source: Springer Online Journal Archives 1860-2000
    Topics: Computer Science , Mathematics
    Notes: Abstract This paper describes heuristics for partitioning a generalM × N matrix into arrowhead form. Such heuristics are useful for decomposing large, constrained, optimization problems into forms that are amenable to parallel processing. The heuristics presented can be easily implemented using publicly available graph partitioning algorithms. The application of such techniques for solving large linear programs is described. Extensive computational results on the effectiveness of our partitioning procedures and their usefulness for parallel optimization are presented. © 1998 The Mathematical Programming Society, Inc. Published by Elsevier Science B.V.
    Type of Medium: Electronic Resource
    URL: http://dx.doi.org/10.1007/BF01582130
    Location Call Number Expected Availability
    BibTip Others were also interested in ...
    Paper (German National Licenses)
    Fulltext
  • 23
    Electronic Resource
    Electronic Resource
    Local convergence of predictor—corrector infeasible-interior-point algorithms for SDPs and SDLCPs (1998)
    Springer
    Mathematical programming 80 (1998), S. 129-160 
    Details
    ISSN: 1436-4646
    Keywords: Semidefinite programming ; Infeasible-interior-point method ; Predictor—correctormethod ; Superlinear convergence ; Primal—dual nondegeneracy
    Source: Springer Online Journal Archives 1860-2000
    Topics: Computer Science , Mathematics
    Notes: Abstract An example of an SDP (semidefinite program) exhibits a substantial difficulty in proving the superlinear convergence of a direct extension of the Mizuno—Todd—Ye type predictor—corrector primal-dual interior-point method for LPs (linear programs) to SDPs, and suggests that we need to force the generated sequence to converge to a solution tangentially to the central path (or trajectory). A Mizuno—Todd—Ye type predictor—corrector infeasible-interior-point algorithm incorporating this additional restriction for monotone SDLCPs (semidefinite linear complementarity problems) enjoys superlinear convergence under strict complementarity and nondegeneracy conditions. © 1998 The Mathematical Programming Society, Inc. Published by Elsevier Science B.V.
    Type of Medium: Electronic Resource
    URL: http://dx.doi.org/10.1007/BF01581723
    Location Call Number Expected Availability
    BibTip Others were also interested in ...
    Paper (German National Licenses)
    Fulltext
  • 24
    Electronic Resource
    Electronic Resource
    A reduction method for variational inequalities (1998)
    Springer
    Mathematical programming 80 (1998), S. 161-169 
    Details
    ISSN: 1436-4646
    Keywords: Variational inequalities ; Complementarity problems ; Walrasian equilibrium ; Computational general equilibrium
    Source: Springer Online Journal Archives 1860-2000
    Topics: Computer Science , Mathematics
    Notes: Abstract This paper explains a method by which the number of variables in a variational inequality having a certain form can be substantially reduced by changing the set over which the variational inequality is posed. The method applies in particular to certain economic equilibrium problems occurring in applications. We explain and justify the method, and give examples of its application, including a numerical example in which the solution time for the reduced problem was approximately 2% of that for the problem in its original form. © 1998 The Mathematical Programming Society, Inc. Published by Elsevier Science B.V.
    Type of Medium: Electronic Resource
    URL: http://dx.doi.org/10.1007/BF01581724
    Location Call Number Expected Availability
    BibTip Others were also interested in ...
    Paper (German National Licenses)
    Fulltext
  • 25
    Electronic Resource
    Electronic Resource
    Cutting planes for integer programs with general integer variables (1998)
    Springer
    Mathematical programming 81 (1998), S. 201-214 
    Details
    ISSN: 1436-4646
    Keywords: Integer programming ; Cutting planes ; Cover inequalities ; Lifting ; Gomory mixed integer cuts ; Cut-and-branch
    Source: Springer Online Journal Archives 1860-2000
    Topics: Computer Science , Mathematics
    Notes: Abstract We investigate the use of cutting planes for integer programs with general integer variables. We show how cutting planes arising from knapsack inequalities can be generated and lifted as in the case of 0–1 variables. We also explore the use of Gomory's mixed-integer cuts. We address both theoretical and computational issues and show how to embed these cutting planes in a branch-and-bound framework. We compare results obtained by using our cut generation routines in two existing systems with a commercially available branch-and-bound code on a range of test problems arising from practical applications. © 1998 The Mathematical Programming Society, Inc. Published by Elsevier Science B.V.
    Type of Medium: Electronic Resource
    URL: http://dx.doi.org/10.1007/BF01581105
    Location Call Number Expected Availability
    BibTip Others were also interested in ...
    Paper (German National Licenses)
    Fulltext
  • 26
    Electronic Resource
    Electronic Resource
    The node capacitated graph partitioning problem: A computational study (1998)
    Springer
    Mathematical programming 81 (1998), S. 229-256 
    Details
    ISSN: 1436-4646
    Keywords: Branch-and-cut algorithm ; Clustering ; Compiler design ; Equipartitioning ; Finite element method ; Graph partitioning ; Layout of electronic circuits ; Separation heuristics
    Source: Springer Online Journal Archives 1860-2000
    Topics: Computer Science , Mathematics
    Notes: Abstract In this paper we consider the problem ofk-partitioning the nodes of a graph with capacity restrictions on the sum of the node weights in each subset of the partition, and the objective of minimizing the sum of the costs of the edges between the subsets of the partition. Based on a study of valid inequalities, we present a variety of separation heuristics for cycle, cycle with ears, knapsack tree and path-block cycle inequalities among others. The separation heuristics, plus primal heuristics, have been implemented in a branch-and-cut routine using a formulation including variables for the edges with nonzero costs and node partition variables. Results are presented for three classes of problems: equipartitioning problems arising in finite element methods and partitioning problems associated with electronic circuit layout and compiler design. © 1998 The Mathematical Programming Society, Inc. Published by Elsevier Science B.V.
    Type of Medium: Electronic Resource
    URL: http://dx.doi.org/10.1007/BF01581107
    Location Call Number Expected Availability
    BibTip Others were also interested in ...
    Paper (German National Licenses)
    Fulltext
  • 27
    Electronic Resource
    Electronic Resource
    Second-order global optimality conditions for convex composite optimization (1998)
    Springer
    Mathematical programming 81 (1998), S. 327-347 
    Details
    ISSN: 1436-4646
    Keywords: Convex composite function ; Second-order global optimality ; Second-order duality ; Variational inequality
    Source: Springer Online Journal Archives 1860-2000
    Topics: Computer Science , Mathematics
    Notes: Abstract In recent years second-order sufficient conditions of an isolated local minimizer for convex composite optimization problems have been established. In this paper, second-order optimality conditions are obtained of aglobal minimizer for convex composite problems with a non-finite valued convex function and a twice strictly differentiable function by introducing a generalized representation condition. This result is applied to a minimization problem with a closed convex set constraint which is shown to satisfy the basic constraint qualification. In particular, second-order necessary and sufficient conditions of a solution for a variational inequality problem with convex composite inequality constraints are obtained. © 1998 The Mathematical Programming Society, Inc. Published by Elsevier Science B.V.
    Type of Medium: Electronic Resource
    URL: http://dx.doi.org/10.1007/BF01580087
    Location Call Number Expected Availability
    BibTip Others were also interested in ...
    Paper (German National Licenses)
    Fulltext
  • 28
    Electronic Resource
    Electronic Resource
    Preface (1998)
    Springer
    Mathematical programming 82 (1998), S. 1-1 
    Details
    ISSN: 1436-4646
    Source: Springer Online Journal Archives 1860-2000
    Topics: Computer Science , Mathematics
    Type of Medium: Electronic Resource
    URL: http://dx.doi.org/10.1007/BF01585862
    Location Call Number Expected Availability
    BibTip Others were also interested in ...
    Paper (German National Licenses)
    Fulltext
  • 29
    Electronic Resource
    Electronic Resource
    Minimizing symmetric submodular functions (1998)
    Springer
    Mathematical programming 82 (1998), S. 3-12 
    Details
    ISSN: 1436-4646
    Keywords: Symmetric submodular function minimization ; Submodular function minimization ; Symmetric submodular functions ; Submodular functions ; Submodular systems
    Source: Springer Online Journal Archives 1860-2000
    Topics: Computer Science , Mathematics
    Notes: Abstract We describe a purely combinatorial algorithm which, given a submodular set functionf on a finite setV, finds a nontrivial subsetA ofV minimizingf[A] + f[V ∖ A]. This algorithm, an extension of the Nagamochi—Ibaraki minimum cut algorithm as simplified by Stoer and Wagner [M. Stoer, F. Wagner, A simple min cut algorithm, Proceedings of the European Symposium on Algorithms ESA '94, LNCS 855, Springer, Berlin, 1994, pp. 141–147] and by Frank [A. Frank, On the edge-connectivity algorithm of Nagamochi and Ibaraki, Laboratoire Artémis, IMAG, Université J. Fourier, Grenbole, 1994], minimizes any symmetric submodular function using O(|V|3) calls to a function value oracle. © 1998 The Mathematical Programming Society, Inc. Published by Elsevier Science B.V.
    Type of Medium: Electronic Resource
    URL: http://dx.doi.org/10.1007/BF01585863
    Location Call Number Expected Availability
    BibTip Others were also interested in ...
    Paper (German National Licenses)
    Fulltext
  • 30
    Electronic Resource
    Electronic Resource
    Random sampling and greedy sparsification for matroid optimization problems (1998)
    Springer
    Mathematical programming 82 (1998), S. 41-81 
    Details
    ISSN: 1436-4646
    Keywords: Random sampling ; Greedy algorithm ; Matroid basis ; Matroid partitioning
    Source: Springer Online Journal Archives 1860-2000
    Topics: Computer Science , Mathematics
    Notes: Abstract Random sampling is a powerful tool for gathering information about a group by considering only a small part of it. We discuss some broadly applicable paradigms for using random sampling in combinatorial optimization, and demonstrate the effectiveness of these paradigms for two optimization problems on matroids: finding an optimum matroid basis and packing disjoint matroid bases. Application of these ideas to the graphic matroid led to fast algorithms for minimum spanning trees and minimum cuts. An optimum matroid basis is typically found by agreedy algorithm that grows an independent set into an optimum basis one element at a time. This continuous change in the independent set can make it hard to perform the independence tests needed by the greedy algorithm. We simplify matters by using sampling to reduce the problem of finding an optimum matroid basis to the problem of verifying that a givenfixed basis is optimum, showing that the two problems can be solved in roughly the same time. Another application of sampling is to packing matroid bases, also known as matroid partitioning. Sampling reduces the number of bases that must be packed. We combine sampling with a greedy packing strategy that reduces the size of the matroid. Together, these techniques give accelerated packing algorithms. We give particular attention to the problem of packing spanning trees in graphs, which has applications in network reliability analysis. Our results can be seen as generalizing certain results from random graph theory. The techniques have also been effective for other packing problems. © 1998 The Mathematical Programming Society, Inc. Published by Elsevier Science B.V.
    Type of Medium: Electronic Resource
    URL: http://dx.doi.org/10.1007/BF01585865
    Location Call Number Expected Availability
    BibTip Others were also interested in ...
    Paper (German National Licenses)
    Fulltext
  • 31
    Electronic Resource
    Electronic Resource
    The quadratic assignment problem with a monotone anti-Monge and a symmetric Toeplitz matrix: Easy and hard cases (1998)
    Springer
    Mathematical programming 82 (1998), S. 125-158 
    Details
    ISSN: 1436-4646
    Keywords: Quadratic assignment ; Special cases ; Polynomially solvable ; Anti-Monge matrices ; Toeplitz matrices
    Source: Springer Online Journal Archives 1860-2000
    Topics: Computer Science , Mathematics
    Notes: Abstract This paper investigates a restricted version of the Quadratic Assignment Problem (QAP), where one of the coefficient matrices is an Anti-Monge matrix with non-decreasing rows and columns and the other coefficient matrix is a symmetric Toeplitz matrix. This restricted version is called the Anti-Monge—Toeplitz QAP. There are three well-known combinatorial problems that can be modeled via the Anti-Monge—Toeplitz QAP: (Pl) The “Turbine Problem”, i.e. the assignment of given masses to the vertices of a regular polygon such that the distance of the center of gravity of the resulting system to the center of the polygon is minimized. (P2) The Traveling Salesman Problem on symmetric Monge distance matrices. (P3) The arrangement of data records with given access probabilities in a linear storage medium in order to minimize the average access time. We identify conditions on the Toeplitz matrixB that lead to a simple solution for the Anti-Monge—Toeplitz QAP: The optimal permutation can be given in advance without regarding the numerical values of the data. The resulting theorems generalize and unify several known results on problems (P1), (P2), and (P3). We also show that the Turbine Problem is NP-hard and consequently, that the Anti-Monge—Toeplitz QAP is NP-hard in general. © 1998 The Mathematical Programming Society, Inc. Published by Elsevier Science B.V.
    Type of Medium: Electronic Resource
    URL: http://dx.doi.org/10.1007/BF01585868
    Location Call Number Expected Availability
    BibTip Others were also interested in ...
    Paper (German National Licenses)
    Fulltext
  • 32
    Electronic Resource
    Electronic Resource
    Bound constrained quadratic programming via piecewise quadratic functions (1999)
    Springer
    Mathematical programming 85 (1999), S. 135-156 
    Details
    ISSN: 1436-4646
    Keywords: Key words: bound constrained quadratic programming – Huber’s M–estimator – condition estimation – Newton iteration – factorization update
    Source: Springer Online Journal Archives 1860-2000
    Topics: Computer Science , Mathematics
    Notes: 1 , the smallest eigenvalue of a symmetric, positive definite matrix, and is solved by Newton iteration with line search. The paper describes the algorithm and its implementation including estimation of λ1, how to get a good starting point for the iteration, and up- and downdating of Cholesky factorization. Results of extensive testing and comparison with other methods for constrained QP are given.
    Type of Medium: Electronic Resource
    URL: http://dx.doi.org/10.1007/s101070050049
    Location Call Number Expected Availability
    BibTip Others were also interested in ...
    Paper (German National Licenses)
    Fulltext
  • 33
    Electronic Resource
    Electronic Resource
    Bimatrix games have quasi-strict equilibria (1999)
    Springer
    Mathematical programming 85 (1999), S. 35-49 
    Details
    ISSN: 1436-4646
    Keywords: Key words: bimatrix game – quasi-strict equilibrium ; Mathematics Subject Classification (1991): 90D05
    Source: Springer Online Journal Archives 1860-2000
    Topics: Computer Science , Mathematics
    Type of Medium: Electronic Resource
    URL: http://dx.doi.org/10.1007/s101070050045
    Location Call Number Expected Availability
    BibTip Others were also interested in ...
    Paper (German National Licenses)
    Fulltext
  • 34
    Electronic Resource
    Electronic Resource
    A smoothing method for mathematical programs with equilibrium constraints (1999)
    Springer
    Mathematical programming 85 (1999), S. 107-134 
    Details
    ISSN: 1436-4646
    Keywords: Key words: equilibrium constraints – variational inequality problems – strong monotonicity – optimality conditions – global convergence ; Mathematics Subject Classification (1991): 90C30, 90C33, 65K05
    Source: Springer Online Journal Archives 1860-2000
    Topics: Computer Science , Mathematics
    Type of Medium: Electronic Resource
    URL: http://dx.doi.org/10.1007/s10107990015a
    Location Call Number Expected Availability
    BibTip Others were also interested in ...
    Paper (German National Licenses)
    Fulltext
  • 35
    Electronic Resource
    Electronic Resource
    Tight representation of logical constraints as cardinality rules (1999)
    Springer
    Mathematical programming 85 (1999), S. 363-377 
    Details
    ISSN: 1436-4646
    Source: Springer Online Journal Archives 1860-2000
    Topics: Computer Science , Mathematics
    Notes: 1 ,...,Am are true, then at least ℓ of the propositions B1,...,Bn are true. The main result of the paper is that the procedure in fact provides a convex hull description.
    Type of Medium: Electronic Resource
    URL: http://dx.doi.org/10.1007/s101070050061
    Location Call Number Expected Availability
    BibTip Others were also interested in ...
    Paper (German National Licenses)
    Fulltext
  • 36
    Electronic Resource
    Electronic Resource
    Using continuous nonlinear relaxations to solve. constrained maximum-entropy sampling problems (1999)
    Springer
    Mathematical programming 85 (1999), S. 221-240 
    Details
    ISSN: 1436-4646
    Keywords: Key words: maximum-entropy sampling – branch and bound – nonlinear programming
    Source: Springer Online Journal Archives 1860-2000
    Topics: Computer Science , Mathematics
    Type of Medium: Electronic Resource
    URL: http://dx.doi.org/10.1007/s101070050055
    Location Call Number Expected Availability
    BibTip Others were also interested in ...
    Paper (German National Licenses)
    Fulltext
  • 37
    Electronic Resource
    Electronic Resource
    Q-matrix recognition via secondary and universal polytopes (1999)
    Springer
    Mathematical programming 85 (1999), S. 259-276 
    Details
    ISSN: 1436-4646
    Keywords: Key words: linear complementary problems – Q-matrices – polyhedral combinatorics – triangulations of point configurations – 0-1 polytopes
    Source: Springer Online Journal Archives 1860-2000
    Topics: Computer Science , Mathematics
    Notes: T (Mx+q)=0, Mx+q≥0, x≥0 has a solution. We explain how one can use the polyhedral structure of the set of all triangulations of a finite point set to determine if an n×n matrix M is a Q-matrix. Our implementation of the algorithm is practical for deciding the Q-nature for all M with n≤8.
    Type of Medium: Electronic Resource
    URL: http://dx.doi.org/10.1007/s101070050057
    Location Call Number Expected Availability
    BibTip Others were also interested in ...
    Paper (German National Licenses)
    Fulltext
  • 38
    Electronic Resource
    Electronic Resource
    Finiteness of conical algorithms with ω-subdivisions (1999)
    Springer
    Mathematical programming 85 (1999), S. 593-616 
    Details
    ISSN: 1436-4646
    Keywords: Key words: concave optimization – conical algorithms –ω-subdivisions Mathematics Subject Classification (1991): 90C26, 65K05
    Source: Springer Online Journal Archives 1860-2000
    Topics: Computer Science , Mathematics
    Notes: Abstract. In this paper the problem of finding the global optimum of a concave function over a polytope is considered. A well-known class of algorithms for this problem is the class of conical algorithms. In particular, the conical algorithm based on the so called ω-subdivision strategy is considered. It is proved that, for any given accuracy ε〉0, this algorithm stops in a finite time by returning an ε-optimal solution for the problem, while it is convergent for ε=0.
    Type of Medium: Electronic Resource
    URL: http://dx.doi.org/10.1007/s101070050073
    Location Call Number Expected Availability
    BibTip Others were also interested in ...
    Paper (German National Licenses)
    Fulltext
  • 39
    Electronic Resource
    Electronic Resource
    Lifted flow cover inequalities for mixed 0-1 integer programs (1999)
    Springer
    Mathematical programming 85 (1999), S. 439-467 
    Details
    ISSN: 1436-4646
    Keywords: Mathematics Subject Classification (1991): 90C11
    Source: Springer Online Journal Archives 1860-2000
    Topics: Computer Science , Mathematics
    Notes: Abstract. We investigate strong inequalities for mixed 0-1 integer programs derived from flow cover inequalities. Flow cover inequalities are usually not facet defining and need to be lifted to obtain stronger inequalities. However, because of the sequential nature of the standard lifting techniques and the complexity of the optimization problems that have to be solved to obtain lifting coefficients, lifting of flow cover inequalities is computationally very demanding. We present a computationally efficient way to lift flow cover inequalities based on sequence independent lifting techniques and give computational results that show the effectiveness of our lifting procedures.
    Type of Medium: Electronic Resource
    URL: http://dx.doi.org/10.1007/s101070050067
    Location Call Number Expected Availability
    BibTip Others were also interested in ...
    Paper (German National Licenses)
    Fulltext
  • 40
    Electronic Resource
    Electronic Resource
    Conditioning of semidefinite programs (1999)
    Springer
    Mathematical programming 85 (1999), S. 525-540 
    Details
    ISSN: 1436-4646
    Keywords: Key words: semidefinite programming – perturbation theory – Kantorovi theory – condition number Mathematics Subject Classification (1991): 90C31, 90C25, 90C05
    Source: Springer Online Journal Archives 1860-2000
    Topics: Computer Science , Mathematics
    Notes: theory. This approach also quantifies the size of permissible perturbations. We include a discussion of these results for block diagonal semidefinite programs, of which linear programming is a special case.
    Type of Medium: Electronic Resource
    URL: http://dx.doi.org/10.1007/s101070050070
    Location Call Number Expected Availability
    BibTip Others were also interested in ...
    Paper (German National Licenses)
    Fulltext
  • 41
    Electronic Resource
    Electronic Resource
    Approximating the complexity measure of Vavasis-Ye algorithm is NP-hard (1999)
    Springer
    Mathematical programming 86 (1999), S. 219-223 
    Details
    ISSN: 1436-4646
    Keywords: Key words: linear programming – computational complexity – complexity measure Mathematics Subject Classification (1991): 90C05, 90C60, 68Q25
    Source: Springer Online Journal Archives 1860-2000
    Topics: Computer Science , Mathematics
    Notes: Abstract. Given an m×n integer matrix A of full row rank, we consider the problem of computing the maximum of ∥B -1 A∥2 where B varies over all bases of A. This quantity appears in various places in the mathematical programming literature. More recently, logarithm of this number was the determining factor in the complexity bound of Vavasis and Ye’s primal-dual interior-point algorithm. We prove that the problem of approximating this maximum norm, even within an exponential (in the dimension of A) factor, is NP-hard. Our proof is based on a closely related result of L. Khachiyan [1].
    Type of Medium: Electronic Resource
    URL: http://dx.doi.org/10.1007/s101070050087
    Location Call Number Expected Availability
    BibTip Others were also interested in ...
    Paper (German National Licenses)
    Fulltext
  • 42
    Electronic Resource
    Electronic Resource
    Global convergence of a class of non-interior point algorithms using Chen-Harker-Kanzow-Smale functions for nonlinear complementarity problems (1999)
    Springer
    Mathematical programming 86 (1999), S. 105-133 
    Details
    ISSN: 1436-4646
    Keywords: Key words: non-interior point method – complementarity problem – smoothing function – homotopy method
    Source: Springer Online Journal Archives 1860-2000
    Topics: Computer Science , Mathematics
    Notes: Abstract. We propose a class of non-interior point algorithms for solving the complementarity problems(CP): Find a nonnegative pair (x,y)∈ℝ 2n satisfying y=f(x) and x i y i =0 for every i∈{1,2,...,n}, where f is a continuous mapping from ℝ n to ℝ n . The algorithms are based on the Chen-Harker-Kanzow-Smale smoothing functions for the CP, and have the following features; (a) it traces a trajectory in ℝ 3n which consists of solutions of a family of systems of equations with a parameter, (b) it can be started from an arbitrary (not necessarily positive) point in ℝ 2n in contrast to most of interior-point methods, and (c) its global convergence is ensured for a class of problems including (not strongly) monotone complementarity problems having a feasible interior point. To construct the algorithms, we give a homotopy and show the existence of a trajectory leading to a solution under a relatively mild condition, and propose a class of algorithms involving suitable neighborhoods of the trajectory. We also give a sufficient condition on the neighborhoods for global convergence and two examples satisfying it.
    Type of Medium: Electronic Resource
    URL: http://dx.doi.org/10.1007/s101070050082
    Location Call Number Expected Availability
    BibTip Others were also interested in ...
    Paper (German National Licenses)
    Fulltext
  • 43
    Electronic Resource
    Electronic Resource
    Linear convergence of epsilon-subgradient descent methods for a class of convex functions (1999)
    Springer
    Mathematical programming 86 (1999), S. 41-50 
    Details
    ISSN: 1436-4646
    Keywords: Key words: resolvent method – proximal point method – bundle method – bundle-trust region method – subgradient Mathematics Subject Classification (1991): 90C25, 49M45
    Source: Springer Online Journal Archives 1860-2000
    Topics: Computer Science , Mathematics
    Notes: Abstract. This paper establishes a linear convergence rate for a class of epsilon-subgradient descent methods for minimizing certain convex functions on ℝ n . Currently prominent methods belonging to this class include the resolvent (proximal point) method and the bundle method in proximal form (considered as a sequence of serious steps). Other methods, such as a variant of the proximal point method given by Correa and Lemaréchal, can also fit within this framework, depending on how they are implemented. The convex functions covered by the analysis are those whose conjugates have subdifferentials that are locally upper Lipschitzian at the origin, a property generalizing classical regularity conditions.
    Type of Medium: Electronic Resource
    URL: http://dx.doi.org/10.1007/s101070050078
    Location Call Number Expected Availability
    BibTip Others were also interested in ...
    Paper (German National Licenses)
    Fulltext
  • 44
    Electronic Resource
    Electronic Resource
    On existence and uniqueness of stationary points in semi-infinite optimization (1999)
    Springer
    Mathematical programming 86 (1999), S. 387-415 
    Details
    ISSN: 1436-4646
    Keywords: Key words: semi-infinite optimization – reduction approach – stationary point – strong stability – extended Mangasarian-Fromovitz constraint qualification Mathematics Subject Classification (1991): 90C30, 90C31, 90C34, 49M39
    Source: Springer Online Journal Archives 1860-2000
    Topics: Computer Science , Mathematics
    Notes: Abstract. The paper deals with semi-infinite optimization problems which are defined by finitely many equality constraints and infinitely many inequality constraints. We generalize the concept of strongly stable stationary points which was introduced by Kojima for finite problems; it refers to the local existence and uniqueness of a stationary point for each sufficiently small perturbed problem, where perturbations up to second order are allowed. Under the extended Mangasarian-Fromovitz constraint qualification we present equivalent conditions for the strong stability of a considered stationary point in terms of first and second derivatives of the involved functions. In particular, we discuss the case where the reduction approach is not satisfied.
    Type of Medium: Electronic Resource
    URL: http://dx.doi.org/10.1007/s101070050095
    Location Call Number Expected Availability
    BibTip Others were also interested in ...
    Paper (German National Licenses)
    Fulltext
  • 45
    Electronic Resource
    Electronic Resource
    An infeasible-interior-point potential-reduction algorithm for linear programming (1999)
    Springer
    Mathematical programming 86 (1999), S. 313-334 
    Details
    ISSN: 1436-4646
    Keywords: Key words: linear programming – potential functions – infeasible-interior-point methods – homogeneity – self-dual
    Source: Springer Online Journal Archives 1860-2000
    Topics: Computer Science , Mathematics
    Type of Medium: Electronic Resource
    URL: http://dx.doi.org/10.1007/s101070050091
    Location Call Number Expected Availability
    BibTip Others were also interested in ...
    Paper (German National Licenses)
    Fulltext
  • 46
    Electronic Resource
    Electronic Resource
    Basis- and partition identification for quadratic programming and linear complementarity problems (1999)
    Springer
    Mathematical programming 86 (1999), S. 261-282 
    Details
    ISSN: 1436-4646
    Keywords: Key words: basis recovery – partition – principal pivot transforms – Balinski-Tucker tableaus – quadratic programming – linear complementarity problems – interior point methods – sufficient matrices – crossover – Criss-Cross method
    Source: Springer Online Journal Archives 1860-2000
    Topics: Computer Science , Mathematics
    Notes: Abstract. Optimal solutions of interior point algorithms for linear and quadratic programming and linear complementarity problems provide maximally complementary solutions. Maximally complementary solutions can be characterized by optimal partitions. On the other hand, the solutions provided by simplex–based pivot algorithms are given in terms of complementary bases. A basis identification algorithm is an algorithm which generates a complementary basis, starting from any complementary solution. A partition identification algorithm is an algorithm which generates a maximally complementary solution (and its corresponding partition), starting from any complementary solution. In linear programming such algorithms were respectively proposed by Megiddo in 1991 and Balinski and Tucker in 1969. In this paper we will present identification algorithms for quadratic programming and linear complementarity problems with sufficient matrices. The presented algorithms are based on the principal pivot transform and the orthogonality property of basis tableaus.
    Type of Medium: Electronic Resource
    URL: http://dx.doi.org/10.1007/s101070050089
    Location Call Number Expected Availability
    BibTip Others were also interested in ...
    Paper (German National Licenses)
    Fulltext
  • 47
    Electronic Resource
    Electronic Resource
    Decision-making by hierarchies of discordant agents (1999)
    Springer
    Mathematical programming 86 (1999), S. 417-431 
    Details
    ISSN: 1436-4646
    Keywords: Mathematics Subject Classification (1991): 90A11, 90B50, 90C90, 90D65
    Source: Springer Online Journal Archives 1860-2000
    Topics: Computer Science , Mathematics
    Notes: Abstract. We study the following decision-making scenario: A linear program is solved by a set of agents arranged hierarchically in a tree, where each agent decides the level of certain variables, and has a distinct objective function, known to all agents. Authority is reflected in two ways: Agents higher in the tree set their variables first; and agents that are siblings in the tree resolve their game by focusing on the Nash equilibrium that is optimum for the agent above them. We give a necessary and sufficient condition for such a hierarchy to be efficient (i.e., to have perfect coordination, to ultimately optimize the objective of the firm). We study problems related to designing a hierarchy (assigning decision makers to positions in the tree) in order to achieve efficiency or otherwise optimize coordination.
    Type of Medium: Electronic Resource
    URL: http://dx.doi.org/10.1007/s101070050096
    Location Call Number Expected Availability
    BibTip Others were also interested in ...
    Paper (German National Licenses)
    Fulltext
  • 48
    Electronic Resource
    Electronic Resource
    A non-interior continuation method for generalized linear complementarity problems (1999)
    Springer
    Mathematical programming 86 (1999), S. 533-563 
    Details
    ISSN: 1436-4646
    Keywords: Key words: generalized linear complementarity problem – non-interior continuation method – Newton method – Q-quadratical convergence Mathematics Subject Classification (1991): 90C33
    Source: Springer Online Journal Archives 1860-2000
    Topics: Computer Science , Mathematics
    Notes: Abstract. In this paper, we propose a non-interior continuation method for solving generalized linear complementarity problems (GLCP) introduced by Cottle and Dantzig. The method is based on a smoothing function derived from the exponential penalty function first introduced by Kort and Bertsekas for constrained minimization. This smoothing function can also be viewed as a natural extension of Chen-Mangasarian’s neural network smooth function. By using the smoothing function, we approximate GLCP as a family of parameterized smooth equations. An algorithm is presented to follow the smoothing path. Under suitable assumptions, it is shown that the algorithm is globally convergent and local Q-quadratically convergent. Few preliminary numerical results are also reported.
    Type of Medium: Electronic Resource
    URL: http://dx.doi.org/10.1007/s101070050104
    Location Call Number Expected Availability
    BibTip Others were also interested in ...
    Paper (German National Licenses)
    Fulltext
  • 49
    Electronic Resource
    Electronic Resource
    On maximization of quadratic form over intersection of ellipsoids with common center (1999)
    Springer
    Mathematical programming 86 (1999), S. 463-473 
    Details
    ISSN: 1436-4646
    Keywords: Key words: semidefinite relaxations – quadratic programming Mathematics Subject Classification (1991): 20E28, 20G40, 20C20
    Source: Springer Online Journal Archives 1860-2000
    Topics: Computer Science , Mathematics
    Notes: Abstract. We demonstrate that if A 1,...,A m are symmetric positive semidefinite n×n matrices with positive definite sum and A is an arbitrary symmetric n×n matrix, then the relative accuracy, in terms of the optimal value, of the semidefinite relaxation $$\max_X\{\Tr(AX)\mid\, \Tr(A_iX)\le1,\,\,i=1,...,m;\,X\succeq0\} \eqno{\hbox{(SDP)}}$$ of the optimization program $$x^TAx\to\max\mid\, x^TA_ix\le 1,\,\,i=1,...,m \eqno{\hbox{(P)}}$$ is not worse than $$1-\frac{1}{{2\ln(2m^2)}}$$ . It is shown that this bound is sharp in order, as far as the dependence on m is concerned, and that a~feasible solution x to (P) with $$x^TAx\ge \frac{{\Opt(\hbox{{\rm SDP}})}}{{2\ln(2m^2)}} \eqno{(*)}$$ can be found efficiently. This somehow improves one of the results of Nesterov [4] where bound similar to (*) is established for the case when all Ai are of rank 1.
    Type of Medium: Electronic Resource
    URL: http://dx.doi.org/10.1007/s101070050100
    Location Call Number Expected Availability
    BibTip Others were also interested in ...
    Paper (German National Licenses)
    Fulltext
  • 50
    Electronic Resource
    Electronic Resource
    Lifting valid inequalities for the precedence constrained knapsack problem (1999)
    Springer
    Mathematical programming 86 (1999), S. 161-185 
    Details
    ISSN: 1436-4646
    Keywords: Mathematics Subject Classification (1991): 90C10
    Source: Springer Online Journal Archives 1860-2000
    Topics: Computer Science , Mathematics
    Notes: Abstract. This paper considers the precedence constrained knapsack problem. More specifically, we are interested in classes of valid inequalities which are facet-defining for the precedence constrained knapsack polytope. We study the complexity of obtaining these facets using the standard sequential lifting procedure. Applying this procedure requires solving a combinatorial problem. For valid inequalities arising from minimal induced covers, we identify a class of lifting coefficients for which this problem can be solved in polynomial time, by using a supermodular function, and for which the values of the lifting coefficients have a combinatorial interpretation. For the remaining lifting coefficients it is shown that this optimization problem is strongly NP-hard. The same lifting procedure can be applied to (1,k)-configurations, although in this case, the same combinatorial interpretation no longer applies. We also consider K-covers, to which the same procedure need not apply in general. We show that facets of the polytope can still be generated using a similar lifting technique. For tree knapsack problems, we observe that all lifting coefficients can be obtained in polynomial time. Computational experiments indicate that these facets significantly strengthen the LP-relaxation.
    Type of Medium: Electronic Resource
    URL: http://dx.doi.org/10.1007/s101070050084
    Location Call Number Expected Availability
    BibTip Others were also interested in ...
    Paper (German National Licenses)
    Fulltext
  • 51
    Electronic Resource
    Electronic Resource
    Block-stochastic matrices and associated finite-state languages (1966)
    Springer
    Computing 1 (1966), S. 50-61 
    Details
    ISSN: 1436-5057
    Source: Springer Online Journal Archives 1860-2000
    Topics: Computer Science
    Description / Table of Contents: Zusammenfassung Es werden Endliche Automaten betrachtet, deren Übergangsmatrix block-stochastisch ist. Die block-stochastische Struktur definiert eine Äquivalenzbeziehung zwischen Zuständen des Automaten. Die Bedeutung und Auswirkung dieser Relation wird untersucht, und zwar insbesonders in Hinsicht auf die in den einzelnen Zuständen des Automaten angenommenen Sprachen.
    Notes: Summary Finite automata are considered whose transition matrix is blockstochastic. The block-stochastic structure defines an equivalence relation among states of the automata. The implications of this relation are investigated, especially with respect to the languages accepted in the states of the automata.
    Type of Medium: Electronic Resource
    URL: http://dx.doi.org/10.1007/BF02235852
    Location Call Number Expected Availability
    BibTip Others were also interested in ...
    Paper (German National Licenses)
    Fulltext
  • 52
    Electronic Resource
    Electronic Resource
    Buchbesprechungen (1966)
    Springer
    Computing 1 (1966), S. 88-92 
    Details
    ISSN: 1436-5057
    Source: Springer Online Journal Archives 1860-2000
    Topics: Computer Science
    Type of Medium: Electronic Resource
    URL: http://dx.doi.org/10.1007/BF02235857
    Location Call Number Expected Availability
    BibTip Others were also interested in ...
    Paper (German National Licenses)
    Fulltext
  • 53
    Electronic Resource
    Electronic Resource
    Über die Nullstellen der ersten Ableitung von Besselfunktionen (1966)
    Springer
    Computing 1 (1966), S. 119-126 
    Details
    ISSN: 1436-5057
    Source: Springer Online Journal Archives 1860-2000
    Topics: Computer Science
    Description / Table of Contents: Summary This paper gives a contribution to the hypothesis ofLense regarding the movements of the second order zeros of the derivativesI′ ν (z) of Bessel functions for every negativ variable ν.
    Notes: Zusammenfassung Die Arbeit liefert einen Beitrag zur derLense'schen Vermutung über die Bewegung der Doppelnullstellen der AbleitungI′ ν (z) der Besselfunktionen bei veränderlichem negativen ν.
    Type of Medium: Electronic Resource
    URL: http://dx.doi.org/10.1007/BF02342621
    Location Call Number Expected Availability
    BibTip Others were also interested in ...
    Paper (German National Licenses)
    Fulltext
  • 54
    Electronic Resource
    Electronic Resource
    Ein Verfahren zum Erkennen von Transportproblemen aus der Simplexmatrix (1966)
    Springer
    Computing 1 (1966), S. 133-145 
    Details
    ISSN: 1436-5057
    Source: Springer Online Journal Archives 1860-2000
    Topics: Computer Science
    Description / Table of Contents: Summary In linear programming often it is important whether a given linear programming problem is equivalent to a transportation problem. In this case, the stepping-stone method could be taken for solving the problem, instead of the simplex method, which requires more storage capacity and computing time.—To decide this question a so-called simplex matrix is used, which results from the given linear programming problem treated by the simplex method. By help of two necessary conditions as well as a necessary and sufficient condition it can be concluded whether the linear programming problem belonging to that simplex matrix is equivalent to a transportation problem or not.—The practical handling of the developed algorithm is shown by an example.
    Notes: Zusammenfassung In der linearen Planungsrechnung interessiert oft, ob ein gegebenes lineares Optimierungsproblem sogar ein Transportproblem ist. Dann könnte man nämlich zur Lösung des Problems statt der Simplexmethode die Stepping-Stone-Methode anwenden, die weniger Speicherplatz und Rechenzeit erfordert.—Zur Klärung dieser Frage geht man von einer sogenannten Simplexmatrix aus, die aus dem mit der Simplexmethode behandelten linearen Optimierungsproblem entstanden ist. Mit Hilfe von zwei notwendigen Bedingungen sowie einer notwendigen und hinreichenden Bedingung läßt sich dann entscheiden, ob das zu jener Simplexmatrix gehörige lineare Optimierungsproblem ein Transportproblem ist oder nicht.—Die praktische Handhabung des entwickelten Verfahrens wird an einem Beispiel gezeigt.
    Type of Medium: Electronic Resource
    URL: http://dx.doi.org/10.1007/BF02342623
    Location Call Number Expected Availability
    BibTip Others were also interested in ...
    Paper (German National Licenses)
    Fulltext
  • 55
    Electronic Resource
    Electronic Resource
    Die Anwendung des Analogrechners in der Unternehmensforschung (1966)
    Springer
    Computing 1 (1966), S. 197-213 
    Details
    ISSN: 1436-5057
    Source: Springer Online Journal Archives 1860-2000
    Topics: Computer Science
    Description / Table of Contents: Summary Besides the electronic digital computers electronic analog computers and their generalisations to iterativ-analog computers or analog computers controlled by digital computers and finally the connection of analog and digital computers in hybrid computers are of increasing importance especially for those mathematical problems, which do not need the high accuracy of digital computers, whereas the typical possibilities of the analog computers allow a quick survey of the features of the solutions. From these applications we choose a few problems of operations research.
    Notes: Zusammenfassung Neben den elektronischen Digitalrechenanlagen gewinnt heute der elektronische Analogrechner und seine Verallgemeinerung zum iterativen Analogrechner, sowie der durch einen Digitalrechner gesteuerte Analogrechner und schließlich die Verbindung von Analog- und Digitalrechner im Hybridrechner zunehmende Bedeutung. Das gilt vor allem für solche mathematische Problemstellungen, bei denen die große Genauigkeit des Digitalrechners nicht erforderlich ist, andererseits aber die typischen Eigenschaften des Analogrechners einen raschen Überblick über die Eigenschaften der Lösungen ermöglichen. Aus der Fülle derartiger Anwendungen seien im folgenden Probleme der Unternehmungsforschung herausgegriffen.
    Type of Medium: Electronic Resource
    URL: http://dx.doi.org/10.1007/BF02234363
    Location Call Number Expected Availability
    BibTip Others were also interested in ...
    Paper (German National Licenses)
    Fulltext
  • 56
    Electronic Resource
    Electronic Resource
    Tagungsbericht (1966)
    Springer
    Computing 1 (1966), S. 282-282 
    Details
    ISSN: 1436-5057
    Source: Springer Online Journal Archives 1860-2000
    Topics: Computer Science
    Type of Medium: Electronic Resource
    URL: http://dx.doi.org/10.1007/BF02234371
    Location Call Number Expected Availability
    BibTip Others were also interested in ...
    Paper (German National Licenses)
    Fulltext
  • 57
    Electronic Resource
    Electronic Resource
    Über Matrixnormen, Gerschgorinkreise und Jacobi-Rotation (1966)
    Springer
    Computing 1 (1966), S. 273-280 
    Details
    ISSN: 1436-5057
    Source: Springer Online Journal Archives 1860-2000
    Topics: Computer Science
    Description / Table of Contents: Summary There exists a general principle for finite matrices, according to which to every matrix norm corresponds an inclusion theorem for eigenvalues. If the norm is the row-sum norm, we have theGershgorin theorem. Another inclusion theorem is used for obtaining bounds for the deviations of the eigenvalues from the diagonal elements, involving the order of the matrix, the maximal modulus of the off-diagonal elements and the distances of the diagonal elements. These bounds yield estimates for theJacobi method for determination of eigenvalues of symmetric matrices.
    Notes: Zusammenfassung Für endliche Matrizen wird ein allgemeines Prinzip gezeigt, das jeder Matrixnorm einen Einschließungssatz für eigenwerte zuordnet. Für die Norm der maximalen Zeilenbetragssumme ergibt sich speziell der Satz vonGerschcorin. Ein anderer Einschließungssatz wird dazu benutzt, für die Abweichungen der Eigenwerte von den Diagonalelementen Schranken aufzustellen, die von der Ordnung der Matrix, dem Maximalbetrag der Nichtdiagonalelemente und den Abständen der Diagonalelemente abhängen. Diese Schranken liefern Fehlerabschätzungen für dasJacobi-Verfahren zur Bestimmung der Eigenwerte symmetrischer Matrizen.
    Type of Medium: Electronic Resource
    URL: http://dx.doi.org/10.1007/BF02234369
    Location Call Number Expected Availability
    BibTip Others were also interested in ...
    Paper (German National Licenses)
    Fulltext
  • 58
    Electronic Resource
    Electronic Resource
    Some results on the relation between automata and their automorphism groups (1966)
    Springer
    Computing 1 (1966), S. 327-340 
    Details
    ISSN: 1436-5057
    Source: Springer Online Journal Archives 1860-2000
    Topics: Computer Science
    Description / Table of Contents: Zusammenfassung In dieser Arbeit wird die algebraische Struktur von abstrakten Automaten untersucht. Als Hilfsmittel dazu dient die Automorphismengruppe von Automaten, das ist die Gruppe aller Zustandspermutationen, bei welchen die Übergangsfunktion erhalten bleibt. Die Zustandsmenge eines Automaten wird in Äquivalenzklassen von “eng verbundenen” (strongly connected) Teilmengen zerlegt. In der Menge dieser Äquivalenzklassen erklären wir eine Teilordnung, deren minimale Elemente “Quellklassen” (source-classes) genannt werden. Wenn nur eine Quellklasse existiert, dann heißt der Automat zyklisch (Oehmke [3]); wenn jeder Automorphismus alle eng verbundenen Äquivalenzklassen auf sich selbst abbildet, dann nennen wir den Automaten normal. In den bisherigen Arbeiten wurden fast ausschließlich nur eng verbundene Automaten behandelt. Hier hingegen erstrecken sich die Untersuchungen auf zyklische und normale Automaten. Dabei werden auch einige Resultate vonA. Fleck [1] über eng verbundene Automaten verallgemeinert. Gelegentlich beschränken wir uns auf abelsche Automaten.
    Notes: Summary In this paper the structure of automata is investigated using the concept of the automorphism group. The investigations about strongly connected automata are extended to cyclic (Oehmke) and normal automata. The set of states is divided into equivalence classes of strongly connected subsets (SCEC). In the set of all SCEC we explain a partial ordering whose minimal elements are called sourceclasses. If there is only one source-classe, the automaton is called cyclic. If each automorphism maps every SCEC onto itself, then the automaton is said to be normal. We generalize some results ofA. Fleck [1]. In some cases we restrict ourselves to Abelian automata.
    Type of Medium: Electronic Resource
    URL: http://dx.doi.org/10.1007/BF02345486
    Location Call Number Expected Availability
    BibTip Others were also interested in ...
    Paper (German National Licenses)
    Fulltext
  • 59
    Electronic Resource
    Electronic Resource
    Algorithmus 3 Umwandlung von BELL-Programmen in ALGOL-Programme (1966)
    Springer
    Computing 1 (1966), S. 358-367 
    Details
    ISSN: 1436-5057
    Source: Springer Online Journal Archives 1860-2000
    Topics: Computer Science
    Type of Medium: Electronic Resource
    URL: http://dx.doi.org/10.1007/BF02345489
    Location Call Number Expected Availability
    BibTip Others were also interested in ...
    Paper (German National Licenses)
    Fulltext
  • 60
    Electronic Resource
    Electronic Resource
    Buchbesprechungen (1966)
    Springer
    Computing 1 (1966), S. 370-380 
    Details
    ISSN: 1436-5057
    Source: Springer Online Journal Archives 1860-2000
    Topics: Computer Science
    Type of Medium: Electronic Resource
    URL: http://dx.doi.org/10.1007/BF02345491
    Location Call Number Expected Availability
    BibTip Others were also interested in ...
    Paper (German National Licenses)
    Fulltext
  • 61
    Electronic Resource
    Electronic Resource
    Einige abstrakte Begriffe in der numerischen Mathematik (Anwendungen der Halbordnung) (1966)
    Springer
    Computing 1 (1966), S. 233-255 
    Details
    ISSN: 1436-5057
    Source: Springer Online Journal Archives 1860-2000
    Topics: Computer Science
    Description / Table of Contents: Summary As in many branches of science, there has been a change of inner structure taking place in Applied Mathematics in recent times, with a marked turn towards abstraction, exemplified by the wide use of methods of functional analysis. In this summarizing lecture, an attempt is made to demonstrate the useful application of abstract notions in Numerical Mathematics, especially by means of the concept of partial order. This concept is used, for instance, in connection withRiesz' partially ordered Banachspaces, pseudometric spaces, intervals, monotone and positive operators, linear and nonlinear optimization. Applications of monotone operators are given for benting of beams, boundary value problems for linear and nonlinear elliptic differential equations, extrapolation for initial value problems and eigenvalue problems. Emphasis is laid on the interrelation between various problem areas, e.g. between boundary value problems and optimization problems.
    Notes: Zusammenfassung In vielen Wissenschaften, so auch in der Angewandten Mathematik, hat sich in letzter Zeit ein innerer Strukturwandel, insbesondere eine starke Wendung zum Abstrakten hin, vollzogen, welche sich z. B. in der ausgiebigen Verwendung funktionalanalytischer Methoden äußert. In diesem zusammenfassenden Vortrag wird versucht, am Beispiel der Halbordnung die Verwendung und den Nutzen abstrakter Begriffe in der Numerischen Mathematik zu zeigen. Die Halbordnung wird u. a. benutzt bei den Begriffen:Rieszscher Halbordnungs-Banachraum, pseudometrischer Raum, Intervall, monotoner Operator, positiver Operator, lineare und nichtlineare Optimierung. Anwendungen der monotonen Operatoren werden beschrieben bei der Biegegleichung für Träger, bei Randwertaufgaben linearer und nichtlinearer elliptischer Differentialgleichungen, bei der Extrapolation für Anfangswertaufgaben und bei Eigenwertaufgaben. Es werden die Zusammenhänge zwischen verschiedenen Gebieten betont, z. B. zwischen Randwertaufgaben und Optimierungsaufgaben.
    Type of Medium: Electronic Resource
    URL: http://dx.doi.org/10.1007/BF02234366
    Location Call Number Expected Availability
    BibTip Others were also interested in ...
    Paper (German National Licenses)
    Fulltext
  • 62
    Electronic Resource
    Electronic Resource
    Buchbesprechungen (1966)
    Springer
    Computing 1 (1966), S. 283-292 
    Details
    ISSN: 1436-5057
    Source: Springer Online Journal Archives 1860-2000
    Topics: Computer Science
    Type of Medium: Electronic Resource
    URL: http://dx.doi.org/10.1007/BF02234372
    Location Call Number Expected Availability
    BibTip Others were also interested in ...
    Paper (German National Licenses)
    Fulltext
  • 63
    Electronic Resource
    Electronic Resource
    Eine neue Rekursionsformel für die Legendre-Polynome und ihre Ableitungen für maschinentechnische Anwendungen (1966)
    Springer
    Computing 1 (1966), S. 309-315 
    Details
    ISSN: 1436-5057
    Source: Springer Online Journal Archives 1860-2000
    Topics: Computer Science
    Description / Table of Contents: Summary In this paper a universal recurrence formular is given for the calculation of theLegendre-Polynomials an their derivates. The first values for the beginning of the recurrence are calculated. Then there are given some simple formulas for the values of functions with the arguments 0 and 1 at the ends of the considered interval. At last the functional equations are generalized.
    Notes: Zusammenfassung Der vorliegende Beitrag gibt eine universelle Rekursionsformel zur Berechnung derLegendre-Polynome und ihrer Ableitungen an. Die Ausgangswerte der Rekursion werden berechnet. Ferner werden einfache Ausdrücke zur Berechnung der Funktionen an den Intervallenden hergeleitet. In einem letzten Abschnitt werden die bekannten Differentialbeziehungen derLegendre-Polynome verallgemeinert und die Differentialgleichung der (m-1) ten Ableitung des Polynomesn-ten Grades angegeben.
    Type of Medium: Electronic Resource
    URL: http://dx.doi.org/10.1007/BF02345484
    Location Call Number Expected Availability
    BibTip Others were also interested in ...
    Paper (German National Licenses)
    Fulltext
  • 64
    Electronic Resource
    Electronic Resource
    Segments in enumerating faces (1995)
    Springer
    Mathematical programming 70 (1995), S. 27-45 
    Details
    ISSN: 1436-4646
    Keywords: Convex polytopes ; Enumeration of faces ; Adjacency ; Segments
    Source: Springer Online Journal Archives 1860-2000
    Topics: Computer Science , Mathematics
    Notes: Abstract We introduce the concept of a segment of a degenerate convex polytope specified by a system of linear constraints, and explain its importance in developing algorithms for enumerating the faces. Using segments, we describe an algorithm that enumerates all the faces, in time polynomial in their number. The role of segments in the unsolved problem of enumerating the extreme points of a convex polytope specified by a degenerate system of linear constraints, in time polynomial in the number of extreme points, is discussed.
    Type of Medium: Electronic Resource
    URL: http://dx.doi.org/10.1007/BF01585927
    Location Call Number Expected Availability
    BibTip Others were also interested in ...
    Paper (German National Licenses)
    Fulltext
  • 65
    Electronic Resource
    Electronic Resource
    On bilevel programming, Part I: General nonlinear cases (1995)
    Springer
    Mathematical programming 70 (1995), S. 47-72 
    Details
    ISSN: 1436-4646
    Keywords: Bilevel programming ; Nonlinear nonconvex ; Nondifferentiable optimization ; Economic planning ; Sensitivity analysis
    Source: Springer Online Journal Archives 1860-2000
    Topics: Computer Science , Mathematics
    Notes: Abstract This paper is concerned with general nonlinear nonconvex bilevel programming problems (BLPP). We derive necessary and sufficient conditions at a local solution and investigate the stability and sensitivity analysis at a local solution in the BLPP. We then explore an approach in which a bundle method is used in the upper-level problem with subgradient information from the lower-level problem. Two algorithms are proposed to solve the general nonlinear BLPP and are shown to converge to regular points of the BLPP under appropriate conditions. The theoretical analysis conducted in this paper seems to indicate that a sensitivity-based approach is rather promising for solving general nonlinear BLPP.
    Type of Medium: Electronic Resource
    URL: http://dx.doi.org/10.1007/BF01585928
    Location Call Number Expected Availability
    BibTip Others were also interested in ...
    Paper (German National Licenses)
    Fulltext
  • 66
    Electronic Resource
    Electronic Resource
    Pseudopower expansion of solutions of generalized equations and constrained optimization problems (1995)
    Springer
    Mathematical programming 70 (1995), S. 123-148 
    Details
    ISSN: 1436-4646
    Keywords: Generalized equations ; Variational inequalities ; Nonlinear programming ; Sensitivity analysis ; Power series ; Strong regularity ; Constrained optimization ; Perturbation theory
    Source: Springer Online Journal Archives 1860-2000
    Topics: Computer Science , Mathematics
    Notes: Abstract We show that the solution of a strongly regular generalized equation subject to a scalar perturbation expands in pseudopower series in terms of the perturbation parameter, i.e., the expansion of orderk is the solution of generalized equations expanded to orderk and thus depends itself on the perturbation parameter. In the polyhedral case, this expansion reduces to a usual Taylor expansion. These results are applied to the problem of regular perturbation in constrained optimization. We show that, if the strong regularity condition is satisfied, the property of quadratic growth holds and, at least locally, the solutions of the optimization problem and of the associated optimality system coincide. If, in addition the number of inequality constraints is finite, the solution and the Lagrange multiplier can be expanded in Taylor series. If the data are analytic, the solution and the multiplier are analytic functions of the perturbation parameter.
    Type of Medium: Electronic Resource
    URL: http://dx.doi.org/10.1007/BF01585932
    Location Call Number Expected Availability
    BibTip Others were also interested in ...
    Paper (German National Licenses)
    Fulltext
  • 67
    Electronic Resource
    Electronic Resource
    A note on packing paths in planar graphs (1995)
    Springer
    Mathematical programming 70 (1995), S. 201-209 
    Details
    ISSN: 1436-4646
    Keywords: Disjoint paths ; Joins ; Packing cuts
    Source: Springer Online Journal Archives 1860-2000
    Topics: Computer Science , Mathematics
    Notes: Abstract Seymour (1981) proved that the cut criterion is necessary and sufficient for the solvability of the edge-disjoint paths problem when the union of the supply graph and the demand graph is planar and Eulerian. When only planarity is required, Middendorf and Pfeiffer (1993) proved the problem to be NP-complete. For this case, Korach and Penn (1992) proved that the cut criterion is sufficient for the existence of a near-complete packing of paths. Here we generalize this result by showing how a natural strengthening of the cut criterion yields better packings of paths. Analogously to Seymour's approach, we actually prove a theorem on packing cuts in an arbitrary graph and then the planar edge-disjoint paths case is obtained by planar dualization. The main result is derived from a theorem of Sebő (1990) on the structure of ±1 weightings of a bipartite graph with no negative circuits.
    Type of Medium: Electronic Resource
    URL: http://dx.doi.org/10.1007/BF01585937
    Location Call Number Expected Availability
    BibTip Others were also interested in ...
    Paper (German National Licenses)
    Fulltext
  • 68
    Electronic Resource
    Electronic Resource
    Linear programming, complexity theory and elementary functional analysis (1995)
    Springer
    Mathematical programming 70 (1995), S. 279-351 
    Details
    ISSN: 1436-4646
    Keywords: Linear programming ; Complexity theory ; Interior-point methods ; Semi-definite programming ; Condition numbers ; Convex programming
    Source: Springer Online Journal Archives 1860-2000
    Topics: Computer Science , Mathematics
    Notes: Abstract We propose analyzing interior-point methods using notions of problem-instance size which are direct generalizations of the condition number of a matrix. The notions pertain to linear programming quite generally; the underlying vector spaces are not required to be finite-dimensional and, more importantly, the cones defining nonnegativity are not required to be polyhedral. Thus, for example, the notions are appropriate in the context of semi-definite programming. We prove various theorems to demonstrate how the notions can be used in analyzing interior-point methods. These theorems assume little more than that the interiors of the cones (defining nonnegativity) are the domains of self-concordant barrier functions.
    Type of Medium: Electronic Resource
    URL: http://dx.doi.org/10.1007/BF01585941
    Location Call Number Expected Availability
    BibTip Others were also interested in ...
    Paper (German National Licenses)
    Fulltext
  • 69
    Electronic Resource
    Electronic Resource
    A descent method with linear programming subproblems for nondifferentiable convex optimization (1995)
    Springer
    Mathematical programming 71 (1995), S. 17-28 
    Details
    ISSN: 1436-4646
    Keywords: Descent method ; Proximal algorithm ; Direction-finding subproblem
    Source: Springer Online Journal Archives 1860-2000
    Topics: Computer Science , Mathematics
    Notes: Abstract Most of the descent methods developed so far suffer from the computational burden due to a sequence of constrained quadratic subproblems which are needed to obtain a descent direction. In this paper we present a class of proximal-type descent methods with a new direction-finding subproblem. Especially, two of them have a linear programming subproblem instead of a quadratic subproblem. Computational experience of these two methods has been performed on two well-known test problems. The results show that these methods are another very promising approach for nondifferentiable convex optimization.
    Type of Medium: Electronic Resource
    URL: http://dx.doi.org/10.1007/BF01592242
    Location Call Number Expected Availability
    BibTip Others were also interested in ...
    Paper (German National Licenses)
    Fulltext
  • 70
    Electronic Resource
    Electronic Resource
    Smoothing methods for convex inequalities and linear complementarity problems (1995)
    Springer
    Mathematical programming 71 (1995), S. 51-69 
    Details
    ISSN: 1436-4646
    Keywords: Smoothing ; Convex inequalities ; Linear complementarity
    Source: Springer Online Journal Archives 1860-2000
    Topics: Computer Science , Mathematics
    Notes: Abstract A smooth approximationp (x, α) to the plus function max{x, 0} is obtained by integrating the sigmoid function 1/(1 + e−αx ), commonly used in neural networks. By means of this approximation, linear and convex inequalities are converted into smooth, convex unconstrained minimization problems, the solution of which approximates the solution of the original problem to a high degree of accuracy forα sufficiently large. In the special case when a Slater constraint qualification is satisfied, an exact solution can be obtained for finiteα. Speedup over MINOS 5.4 was as high as 1142 times for linear inequalities of size 2000 × 1000, and 580 times for convex inequalities with 400 variables. Linear complementarity problems are converted into a system of smooth nonlinear equations and are solved by a quadratically convergent Newton method. For monotone LCPs with as many as 10 000 variables, the proposed approach was as much as 63 times faster than Lemke's method.
    Type of Medium: Electronic Resource
    URL: http://dx.doi.org/10.1007/BF01592244
    Location Call Number Expected Availability
    BibTip Others were also interested in ...
    Paper (German National Licenses)
    Fulltext
  • 71
    Electronic Resource
    Electronic Resource
    A closed-form representation of mixed-integer program value functions (1995)
    Springer
    Mathematical programming 71 (1995), S. 127-136 
    Details
    ISSN: 1436-4646
    Keywords: Parametric optimization ; Mixed-integer program ; Value functions
    Source: Springer Online Journal Archives 1860-2000
    Topics: Computer Science , Mathematics
    Notes: Abstract We identify a class of formulas computable in polynomial time such that the functions defined by these formulas are precisely the value functions of mixed-integer programs with rational constraint coefficients.
    Type of Medium: Electronic Resource
    URL: http://dx.doi.org/10.1007/BF01585994
    Location Call Number Expected Availability
    BibTip Others were also interested in ...
    Paper (German National Licenses)
    Fulltext
  • 72
    Electronic Resource
    Electronic Resource
    Lower bounds for the quadratic assignment problem via triangle decompositions (1995)
    Springer
    Mathematical programming 71 (1995), S. 137-151 
    Details
    ISSN: 1436-4646
    Keywords: Quadratic assignment problem ; Lower bounds
    Source: Springer Online Journal Archives 1860-2000
    Topics: Computer Science , Mathematics
    Notes: Abstract We consider transformations of the (metric) Quadratic Assignment Problem (QAP) that exploit the metric structure of a given instance. We show in particular how the structural properties of rectangular grids can be used to improve a given lower bound. Our work is motivated by previous research of Palubetskes (1988), and it extends a bounding approach proposed by Chakrapani and Skorin-Kapov (1993). Our computational results indicate that the present approach is practical; it has been applied to problems of dimension up ton = 150. Moreover, the new approach yields by far the best lower bounds on most of the instances of metric QAPs that we considered.
    Type of Medium: Electronic Resource
    URL: http://dx.doi.org/10.1007/BF01585995
    Location Call Number Expected Availability
    BibTip Others were also interested in ...
    Paper (German National Licenses)
    Fulltext
  • 73
    Electronic Resource
    Electronic Resource
    A generalized subgradient method with relaxation step (1995)
    Springer
    Mathematical programming 71 (1995), S. 207-219 
    Details
    ISSN: 1436-4646
    Keywords: Subgradient optimization ; Relaxation methods ; Projection methods
    Source: Springer Online Journal Archives 1860-2000
    Topics: Computer Science , Mathematics
    Notes: Abstract We study conditions for convergence of a generalized subgradient algorithm in which a relaxation step is taken in a direction, which is a convex combination of possibly all previously generated subgradients. A simple condition for convergence is given and conditions that guarantee a linear convergence rate are also presented. We show that choosing the steplength parameter and convex combination of subgradients in a certain sense optimally is equivalent to solving a minimum norm quadratic programming problem. It is also shown that if the direction is restricted to be a convex combination of the current subgradient and the previous direction, then an optimal choice of stepsize and direction is equivalent to the Camerini—Fratta—Maffioli modification of the subgradient method.
    Type of Medium: Electronic Resource
    URL: http://dx.doi.org/10.1007/BF01585999
    Location Call Number Expected Availability
    BibTip Others were also interested in ...
    Paper (German National Licenses)
    Fulltext
  • 74
    Electronic Resource
    Electronic Resource
    Presolving in linear programming (1995)
    Springer
    Mathematical programming 71 (1995), S. 221-245 
    Details
    ISSN: 1436-4646
    Keywords: Linear programming ; Presolving ; Interior-point methods
    Source: Springer Online Journal Archives 1860-2000
    Topics: Computer Science , Mathematics
    Notes: Abstract Most modern linear programming solvers analyze the LP problem before submitting it to optimization. Some examples are the solvers WHIZARD (Tomlin and Welch, 1983), OB1 (Lustig et al., 1994), OSL (Forrest and Tomlin, 1992), Sciconic (1990) and CPLEX (Bixby, 1994). The purpose of the presolve phase is to reduce the problem size and to discover whether the problem is unbounded or infeasible. In this paper we present a comprehensive survey of presolve methods. Moreover, we discuss the restoration procedure in detail, i.e., the procedure that undoes the presolve. Computational results on the NETLIB problems (Gay, 1985) are reported to illustrate the efficiency of the presolve methods.
    Type of Medium: Electronic Resource
    URL: http://dx.doi.org/10.1007/BF01586000
    Location Call Number Expected Availability
    BibTip Others were also interested in ...
    Paper (German National Licenses)
    Fulltext
  • 75
    Electronic Resource
    Electronic Resource
    Eine Methode zur Bestimmung günstiger Konvergenzfaktoren für asymptotische Entwicklungen (1967)
    Springer
    Computing 2 (1967), S. 246-256 
    Details
    ISSN: 1436-5057
    Source: Springer Online Journal Archives 1860-2000
    Topics: Computer Science
    Description / Table of Contents: Summary We are concerned with the numerical solution of a differential equation which possesses an asymptotic power series. Especially we are interested in arguments from the critical domain. This leads us to the determination of nearly-optimal converging factors. Using the theory of singularVolterra integral equations we obtain for the remainder terms as functions of the converging factors rather good lower and upper bounds. Minimizing these bounds we gain nearly-optimal converging factors, with an error only little greater than the error of the exact optimal converging factors. Moreover we give an estimate of the rapidity of convergence of the approximation sequence. An example shows the effectiveness of our method.
    Notes: Zusammenfassung Wir befassen uns mit der numerischen Lösung einer Differentialgleichung, bei der eine asymptotische Potenzreihe zur Verfügung steht. Besonders interessieren wir uns für Argumente aus dem kritischen Bereich. Dabei tritt das Problem der Bestimmung günstiger Konvergenzfaktoren auf. Es wird für den Formelfehler in Abhängigkeit von den verwendeten Konvergenzfaktoren eine recht genaue Abschätzung sowohl nach oben wie auch nach unten angegeben. Zur Herleitung der Fehlerschranken wird die Theorie der singulärenVolterraschen Integralgleichungen benützt. Die Minimierung der Fehlerschranken liefert dann sehr günstige Konvergenzfaktoren, bei denen der zugehörige Fehler nur wenig über dem Fehler der theoretisch optimalen Lösung liegt. Ferner ergeben sich Aussagen über die Konvergenzgeschwindigkeit der Approximationsfolge. Ein Beispiel zeigt die Wirksamkeit des Verfahrens.
    Type of Medium: Electronic Resource
    URL: http://dx.doi.org/10.1007/BF02236610
    Location Call Number Expected Availability
    BibTip Others were also interested in ...
    Paper (German National Licenses)
    Fulltext
  • 76
    Electronic Resource
    Electronic Resource
    Beweisalgorithmen für die Prädikatenlogik (1967)
    Springer
    Computing 2 (1967), S. 263-283 
    Details
    ISSN: 1436-5057
    Source: Springer Online Journal Archives 1860-2000
    Topics: Computer Science
    Description / Table of Contents: Summary Starting from a special formulation of first order functional calculus two procedures are presented producing refutations of inconsistent formulas. Both procedures are based on the notion of interconnecting literals. The first one goes back toHerbrand's Theorem. LetF n be the conjunction ofn copies of the formulaF. An algorithm is introduced to decide whether, for a fixedn, there is an assignment β for the variables ofF n making the formula βF n completely interconnected. By applying this algorithm forn=1,2,... a truth-functionally inconsistent formula of minimal length is constructed. The basic idea of the second procedure is to produce fromF new oneliteral clauses (which are consisten withF). In many cases this proofprocedure, while not complete, is very effective in comparison with other programs; some examples of machine-refutations are given in the appendix. The method may be generalized; in particular it suggests a possibility of man-machine interaction in theorem-proving.
    Notes: Zusammenfassung Ausgehend von einer speziellen Formulierung des Prädikatenkalküls 1. Stufe werden zwei Verfahren entwickelt, welche Widerlegungen inkonsistenter FormelnF liefern. Grundlegend für beide Verfahren ist der Begriff der Verkettung von Literals. Das erste beruht auf demHerbrad-Theorem. SeiF n die Konjunktion vonn Exemplaren der FormelF. Es wird ein Algorithmus angegeben, der entscheidet, ob es bei gegebenemn eine Belegung β der Variablen vonF n gibt, bei welcher die Formel βF n vollständig verkettet ist. Die Anwendung dieses Algorithmus fürn=1,2, ... führt zur Konstruktion einer aussagenlogisch inkonsistenten Formel minimaler Länge. Das zweite Verfahren beruht darauf, daß neue Clausen erzeugt werden, die aus nur einem Literal bestehen (und die mitF konsistent sind). Dieses Verfahren ist nicht vollständig, liefert aber in vielen Fällen schnellere Widerlegungen als andere Methoden; einige Maschinen-Protokolle solcher Widerlegungen sind im Anhang zusammengestellt. Das Verfahren läßt sich verallgemeinern; insbesondere bietet es eine Möglichkeit des Zusammenwirkens von Mensch und Maschine beim Beweisen mathematischer Sätze.
    Type of Medium: Electronic Resource
    URL: http://dx.doi.org/10.1007/BF02236612
    Location Call Number Expected Availability
    BibTip Others were also interested in ...
    Paper (German National Licenses)
    Fulltext
  • 77
    Electronic Resource
    Electronic Resource
    Buchbesprechungen (1967)
    Springer
    Computing 2 (1967), S. 291-308 
    Details
    ISSN: 1436-5057
    Source: Springer Online Journal Archives 1860-2000
    Topics: Computer Science
    Type of Medium: Electronic Resource
    URL: http://dx.doi.org/10.1007/BF02236615
    Location Call Number Expected Availability
    BibTip Others were also interested in ...
    Paper (German National Licenses)
    Fulltext
  • 78
    Electronic Resource
    Electronic Resource
    Bestimmung der Automorphismengruppe spezieller Klassen von Graphen (1967)
    Springer
    Computing 2 (1967), S. 332-335 
    Details
    ISSN: 1436-5057
    Source: Springer Online Journal Archives 1860-2000
    Topics: Computer Science
    Description / Table of Contents: Summary In this article there will be treated a method to get the involutoric automorphisms of a graph without the execution of any permutation. If a graph has the property that each of it's vertices can be permuted with not more than one other vertex, all automorphisms of the graph are involutoric. In that case the result is the whole group of automorphisms. At the end an ALGOL-procedure is given which computes the involutions if for each vertex the possible image is known.
    Notes: Zusammenfassung In dieser Arbeit wird eine Methode behandelt, die involutorischen Automorphismen von Graphen allein aus den Eigenschaften der Inzidenzmatrix ohne Anwendung von Permutationen aufzustellen. Hat ein Graph die Eigenschaft, daß jeder seiner Punkte mit höchstens einem anderen vertauscht werden kann, so besteht seine Automorphismengruppe aus lauter Involutionen. In diesem Falle erhält man die ganze Automorphismengruppe. Abschließend wird eine ALGOL-Prozedur zur Ermittlung der Involutionen angegeben, wenn für jeden Punkt sein möglicher Bildpunkt bekannt ist.
    Type of Medium: Electronic Resource
    URL: http://dx.doi.org/10.1007/BF02235810
    Location Call Number Expected Availability
    BibTip Others were also interested in ...
    Paper (German National Licenses)
    Fulltext
  • 79
    Electronic Resource
    Electronic Resource
    Some results on the set of congruence relations in a finite, strongly connected automaton (1967)
    Springer
    Computing 2 (1967), S. 353-367 
    Details
    ISSN: 1436-5057
    Source: Springer Online Journal Archives 1860-2000
    Topics: Computer Science
    Description / Table of Contents: Zusammenfassung Die Kongruenzrelationen eines Automaten sind aus verschiedenen Gründen von Interesse. Zum Beispiel bilden sie die Grundlage für Minimisierungsverfahren, oder sie geben die Möglichkeit, einen Automaten in einer Weise zu zerlegen, die technisch bedeutsam ist [Hartmanis et al.]. In der vorliegenden Arbeit haben wir den Zusammenhang zwischen der AutomorphismengruppeG (A) und dem KongruenzenverbandR (A) eines Automaten untersucht. Dieser Zusammenhang beruht hauptsächlich auf einer Galoisverbindung zwischen dem Untergruppenverband vonG (A) und dem VerbandR (A). Dadurch ist eine Teilmenge vonR (A) durch Gruppen zu kennzeichnen. Unterstellt man, daß die Gruppentheorie der triviale Teil der Theorie der Halbgruppen ist, so richtet sich das Interesse auf den verbleibenden Anteil vonR (A), der nicht durchG (A) charakterisiert wird. Ihn in Allgemeinheit zu untersuchen scheint ein aussichtsloses Unterfangen zu sein, weshalb wir uns auf die Klasse der sogenannten rechtsregulären Automaten beschränkt haben. Im letzten Abschnitt wird der theoretische Hintergrund für ein Verfhren entwickelt, das sowohl die Kongruenzen eines Automaten als auch dessen Endomorphismenhalbgruppe systematisch zu erstellen gestattet.
    Notes: Summary The congruence relations of an automaton are of interest for various reasons. For example they are relevant for minimization procedures and they are suitable for decomposing the automaton in a specific way which is of technical importance [Hartmanis et al.]. In this paper we have investigated the interconnection between the automorphism groupG (A) and the latticeR (A) of congruence relations of an automaton. This interconnection is primarily based on a Galois connection between the subgroup lattice ofG (A) and the latticeG (A), which characterizes a subset ofR (A) in terms of groups. Assuming that group theory is the trivial part of the theory of semigroups, the attention is directed to the remainder ofR (A) which is not characterized byG (A) in the way mentioned above. This remainder, however, has not been inspected for the general case, which seems to be a hopeless task, but for the class of so called right regular automata. In the last section some theoretical background for a systematic procedure in obtaining all congruence relations of an automaton as well as its endomorphism semigroup has been developed.
    Type of Medium: Electronic Resource
    URL: http://dx.doi.org/10.1007/BF02235812
    Location Call Number Expected Availability
    BibTip Others were also interested in ...
    Paper (German National Licenses)
    Fulltext
  • 80
    Electronic Resource
    Electronic Resource
    Erratum (1998)
    Springer
    Mathematical programming 80 (1998), S. 125-125 
    Details
    ISSN: 1436-4646
    Source: Springer Online Journal Archives 1860-2000
    Topics: Computer Science , Mathematics
    Type of Medium: Electronic Resource
    URL: http://dx.doi.org/10.1007/BF01582133
    Location Call Number Expected Availability
    BibTip Others were also interested in ...
    Paper (German National Licenses)
    Fulltext
  • 81
    Electronic Resource
    Electronic Resource
    On the complexity of linear programming under finite precision arithmetic (1998)
    Springer
    Mathematical programming 80 (1998), S. 91-123 
    Details
    ISSN: 1436-4646
    Keywords: Complexity of linear programming ; Interior point methods ; Conditioning ; Error analysis
    Source: Springer Online Journal Archives 1860-2000
    Topics: Computer Science , Mathematics
    Notes: Abstract In this paper we study the complexity of solving linear programs in finite precision arithmetic. This is the normal setup in scientific computation, as digital computers work in finite precision. We analyze two aspects of the complexity: one is the number of arithmetic operations required to solve the problem approximately, and the other is the working precision required to carry out some critical computations safely. We show how the “conditioning” of the problem instance affects the working precision required and the computational requirements of a classical logarithmic barrier algorithm to approximate the optimal value of the problem within a given tolerance. Our results show that these complexity measures depend linearly on the logarithm of a certain condition measure. We carry out the analysis by looking at how well Newton's Method can follow the central trajectory of the feasible set, and computing error bounds in terms of the condition measure. These results can be interpreted as a theoretical indication of “good” numerical behavior of the logarithmic barrier method, in the sense that a problem instance “twice as hard” as the other from the numerical point of view, requires only at most twice as much precision to be solved. © 1998 The Mathematical Programming Society, Inc. Published by Elsevier Science B.V.
    Type of Medium: Electronic Resource
    URL: http://dx.doi.org/10.1007/BF01582132
    Location Call Number Expected Availability
    BibTip Others were also interested in ...
    Paper (German National Licenses)
    Fulltext
  • 82
    Electronic Resource
    Electronic Resource
    Max Horn SAT and the minimum cut problem in directed hypergraphs (1998)
    Springer
    Mathematical programming 80 (1998), S. 213-237 
    Details
    ISSN: 1436-4646
    Keywords: Maximum satisfiability ; Horn clauses ; Directed hypergraphs ; Minimum cut ; Generalized set covering
    Source: Springer Online Journal Archives 1860-2000
    Topics: Computer Science , Mathematics
    Notes: Abstract In this paper we consider the Maximum Horn Satisfiability problem, which is reduced to the problem of finding a minimum cardinality cut on a directed hypergraph. For the latter problem, we propose different IP formulations, related to three different definitions of hyperpath weight. We investigate the properties of their linear relaxations, showing that they define a hierarchy. The weakest relaxation is shown to be equivalent to the relaxation of a well known IP formulation of Max Horn SAT, and to a max-flow problem on hypergraphs. The tightest relaxation, which is a disjunctive programming problem, is shown to have integer optimum. The intermediate relaxation consists in a set covering problem with a possible exponential number of constraints. This latter relaxation provides an approximation of the convex hull of the integer solutions which, as proven by the experimental results given, is much tighter than the one known in the literature. © 1998 The Mathematical Programming Society, Inc. Published by Elsevier Science B.V.
    Type of Medium: Electronic Resource
    URL: http://dx.doi.org/10.1007/BF01581727
    Location Call Number Expected Availability
    BibTip Others were also interested in ...
    Paper (German National Licenses)
    Fulltext
  • 83
    Electronic Resource
    Electronic Resource
    A service system with two parallel queues (1969)
    Springer
    Computing 4 (1969), S. 24-29 
    Details
    ISSN: 1436-5057
    Source: Springer Online Journal Archives 1860-2000
    Topics: Computer Science
    Description / Table of Contents: Zusammenfassung Die vorliegende Arbeit bringt einige ergänzende Resultate über ein in [4] betrachtetes Wartesystem. Die in [4] entwickelten numerischen Methoden zur Berechnung von Gleichgewichtswahrscheinlichkeiten werden diskutiert.
    Notes: Summary In an earlier paper [4] a certain service system has been investigated. The present paper adds some further results and discusses the numerical methods developed in [4] for the calculation of equilibrium probabilities.
    Type of Medium: Electronic Resource
    URL: http://dx.doi.org/10.1007/BF02236539
    Location Call Number Expected Availability
    BibTip Others were also interested in ...
    Paper (German National Licenses)
    Fulltext
  • 84
    Electronic Resource
    Electronic Resource
    Zertifikat zu Algorithmus 8 (1969)
    Springer
    Computing 4 (1969), S. 75-75 
    Details
    ISSN: 1436-5057
    Source: Springer Online Journal Archives 1860-2000
    Topics: Computer Science
    Type of Medium: Electronic Resource
    URL: http://dx.doi.org/10.1007/BF02236543
    Location Call Number Expected Availability
    BibTip Others were also interested in ...
    Paper (German National Licenses)
    Fulltext
  • 85
    Electronic Resource
    Electronic Resource
    ALGOL-Prozeduren zu den modifizierten Algorithmen nach Minty und Moore ALGOL-Procedures to the Modified Algorithms According to Minty and Moore (1969)
    Springer
    Computing 4 (1969), S. 76-81 
    Details
    ISSN: 1436-5057
    Source: Springer Online Journal Archives 1860-2000
    Topics: Computer Science
    Type of Medium: Electronic Resource
    URL: http://dx.doi.org/10.1007/BF02236544
    Location Call Number Expected Availability
    BibTip Others were also interested in ...
    Paper (German National Licenses)
    Fulltext
  • 86
    Electronic Resource
    Electronic Resource
    Berichtigung (1969)
    Springer
    Computing 4 (1969), S. 92-92 
    Details
    ISSN: 1436-5057
    Source: Springer Online Journal Archives 1860-2000
    Topics: Computer Science
    Type of Medium: Electronic Resource
    URL: http://dx.doi.org/10.1007/BF02236546
    Location Call Number Expected Availability
    BibTip Others were also interested in ...
    Paper (German National Licenses)
    Fulltext
  • 87
    Electronic Resource
    Electronic Resource
    On the numerical solution of higher order nonlinear parabolic equations (1968)
    Springer
    Computing 3 (1968), S. 139-150 
    Details
    ISSN: 1436-5057
    Source: Springer Online Journal Archives 1860-2000
    Topics: Computer Science
    Description / Table of Contents: Zusammenfassung Diese Arbeit behandelt die numerische Approximation von schwachen Lösungen der ersten Anfangs-Randwertaufgabe für die nichtlineare parabolische Gleichung höherer Ordnung $$\sum\limits_{|\alpha | , |\beta | \leqq p} {D^\alpha (a_{\alpha \beta } (x,t)) \leqq D^\beta u - \partial u/\partial t = f} $$ wof=f(x, t, D v u), |v|≤p−1, p≥1 ganz, und wo α, β,v multi-Indices sind.
    Notes: Summary This paper deals with the numerical approximation of weak solutions of the first initial, boundary value problem for the higher order, nonlinear parabolic equation $$\sum\limits_{|\alpha | , |\beta | \leqq p} {D^\alpha (a_{\alpha \beta } (x,t)) \leqq D^\beta u - \partial u/\partial t = f} $$ wheref=f(x, t, D v u), |v|≤p−1, p≥1 is an integer and α, β,v are multi-indices.
    Type of Medium: Electronic Resource
    URL: http://dx.doi.org/10.1007/BF02277456
    Location Call Number Expected Availability
    BibTip Others were also interested in ...
    Paper (German National Licenses)
    Fulltext
  • 88
    Electronic Resource
    Electronic Resource
    Isomorphism of chordal (6, 3) graphs (1995)
    Springer
    Computing 54 (1995), S. 303-316 
    Details
    ISSN: 1436-5057
    Keywords: 05 C 60 ; 05 C 85 ; Graph isomorphism ; automorphism partition ; polynomial algorithm ; chordal graphs ; graphs with fewP 4s
    Source: Springer Online Journal Archives 1860-2000
    Topics: Computer Science
    Description / Table of Contents: Zusammenfassung Ein Graph ist chordal, wenn er keine sehnenlosen Kreise der Länge mindestens vier enthält und (q, t), wenn keine Menge von höchstensq Knoten mehr alst Wege der Länge drei induziert. Es ist bekannt, daß das Isomorphieproblem für chordale Graphen und für (6, 3) Graphen Isomorphie-vollständig ist. Wir stellen polynomiale Verfahren vor zur Bestimmung der Automorphiepartition und zum Testen der Isomorphie von Graphen, die sowohl chrodal als auch (6, 3) sind. Der zugang basiert auf dem Studium von simplizialen Partitionen von chordalen Graphen. Es wird gezeigt, daß für chordale (6, 3) Graphen die Automorphiepartition mit der gröbsten regulären simplizialen Partition übereinstimmt. Dies führt zu einemO(n+m logn) isomorphietest.
    Notes: Abstract A graph is chordal if it contains no chordless cycles of length at least four and (q, t) if no set of at mostq vertices induces more thant paths of length three. It is known that the isomorphism problem is isomorphism complete for chordal graphs and for (6, 3) graphs. We present polynomial methods to determine the automorphism partition and to test isomorphism of graphs which are both chordal and (6, 3). The approach is based on the study of simplicial partitions of chordal graphs. It is proved that for chordal (6, 3) graphs the automorphism partition coincides with the coarsest regular simplicial partition. This yields anO(n+m logn) isomorphism test.
    Type of Medium: Electronic Resource
    URL: http://dx.doi.org/10.1007/BF02238229
    Location Call Number Expected Availability
    BibTip Others were also interested in ...
    Paper (German National Licenses)
    Fulltext
  • 89
    Electronic Resource
    Electronic Resource
    Fourier mode analysis of the multigrid waveform relaxation and time-parallel multigrid methods (1995)
    Springer
    Computing 54 (1995), S. 317-330 
    Details
    ISSN: 1436-5057
    Keywords: 65M06 ; 65M55 ; 65Y05 ; Parabolic partial differential equation ; Multigird ; parallel computing
    Source: Springer Online Journal Archives 1860-2000
    Topics: Computer Science
    Description / Table of Contents: Zusammenfassung Die Erscheinung von Parallelrechnern hat zur Entwicklung neuer Lösungsverfahren for zeitabhängige partielle Differentialgleichungen geführt. Zwei der in letzter Zeit entwickelten Verfahren — die Mehrgitter-Wellenformrelaxations-Methode und die zeitparallele Mehrgittermethode —haben zum Ziel, die Lösung zu vielen verschiedenen diskreten Zeitpunkten simultan zu berechnen. In dieser Arbeit wird anhand der Ergebnisse einer Fourier-Analyse für ein Modell-problem das Konvergenzverhalten beider Methoden verglichen.
    Notes: Abstract The advent of parallel computers has led to the development of new solution algorithms for time-dependent partial differential equations. Two recently developed methods, multigrid waveform relaxation and time-parallel multigrid, have been designed to solve parabolic partial differential equations on many time-levels simultaneously. This paper compares the convergence properties of these methods, based on the results of an exponential Fourier mode analysis for a model problem.
    Type of Medium: Electronic Resource
    URL: http://dx.doi.org/10.1007/BF02238230
    Location Call Number Expected Availability
    BibTip Others were also interested in ...
    Paper (German National Licenses)
    Fulltext
  • 90
    Electronic Resource
    Electronic Resource
    Iterations for solving linear variational inequalities on domains with nonlinear boundaries (1995)
    Springer
    Computing 54 (1995), S. 251-272 
    Details
    ISSN: 1436-5057
    Keywords: Iterative process ; variational inequality ; non-accurate iteration ; projection
    Source: Springer Online Journal Archives 1860-2000
    Topics: Computer Science
    Description / Table of Contents: Zusammenfassung Diese Arbeit behandelt numerische Methoden zur Lösung linearer Variations-Ungleichungen auf einer abgeschlossenen konvexen Teilmenge des ℝn. Es gibt zwar zahlreiche Iterationsverfahren für den FallC=ℝ + n für den Fall einer beliebigen abgeschlossenen konvexen TeilmengeC wurde aber nur wenig vorgeschlagen. Die wesentliche Schwierigkeit in diesem Fall liegt in den Nichtlinearitäten des Randes vonC. In dieser Arbeit werden Iterationsverfahren zur Lösung linearer Variations-Ungleichungen auf einer beliebigen abgeschlossenen konvexen TeilmengeC entwickelt. In unseren Algorithmen wird die Berechnung einer linearen Variations-Ungleichung zerlegt in eine Folge von Projektionen eines Vektors auf die abgeschlossene konvexe TeilmengeC, die berechnet werden können, solange die Bestimmungsgleichungen des Randes gegeben sind. Insbesondere kann mit unseren Iterationsverfahren leicht eine Lösung berechnet werden fürC als Würfel, Kugel, Ellipsoid etc. Außerdem werden Näherungs-Iterationen, Abschätzung der Lösungen für unbeschränkte Bereiche und die Theorie der Randapproximation untersucht. Weiters wird eine notwendige und hinreichende Bedingung dafür angegeben, daß ein Vektor eine Näherungslösung ist. Schließlich werden einige numerische Beispiele präsentiert, die zeigen, daß die vorgestellten Algorithmen effektiv und effizient sind.
    Notes: Abstract This paper deals with numerical methods for solving linear variational inequalities on an arbitrary closed convex subsetC of ℝ n . Although there were numerous iterations studied for the caseC=ℝ + n , few were proposed for the case whenC is a closed convex subset. The essential difficulty in this case is the nonlinearities ofC's boundaries. In this paper iteration processes are designed for solving linear variational inequalities on an arbitrary closed convex subsetC. In our algorithms the computation of a linear variational inequality is decomposed into a sequence of problems of projecting a vector to the closed convex subsetC, which are computable as long as the equations describing the boundaries are given. In particular, using our iterations one can easily compute a solution whenC is one of the common closed convex subsets such as cube, ball, ellipsoid, etc. The non-accurate iteration, the estimate of the solutions on unbounded domains and the theory of approximating the boundaries are also established. Moreover, a necessary and sufficient condition is given for a vector to be an approximate solution. Finally, some numerical examples are presented, which show that the designed algorithms are effective and efficient. The exposition of this paper is self-contained.
    Type of Medium: Electronic Resource
    URL: http://dx.doi.org/10.1007/BF02253616
    Location Call Number Expected Availability
    BibTip Others were also interested in ...
    Paper (German National Licenses)
    Fulltext
  • 91
    Electronic Resource
    Electronic Resource
    Robustness of the additive and multiplicative frequency decomposition multi-level method (1995)
    Springer
    Computing 54 (1995), S. 331-346 
    Details
    ISSN: 1436-5057
    Keywords: 65N55 ; 65N30 ; Frequency decomposition ; multi-level method ; finite elements ; hierarchical basis ; additive and multiplicative Schwarz methods ; subspace decomposition ; robustness
    Source: Springer Online Journal Archives 1860-2000
    Topics: Computer Science
    Description / Table of Contents: Zusammenfassung Kürzlich haben wir eine effektive Modifizierung des Frequenzzerlegungs-Mehrgitterverfahrens vorgestellt. In diesem Artikel wird die multiplikative Variante dieses Verfahrens untersucht. Unter Verwendung der Theorie der Unterraumkorrekturverfahren wird die Robustheit sowohl für die multiplikative als auch für die additive Variante bei Anwendung auf anisotrope Probleme mit beliebiger Raumdimension bewiesen. Die Implementierung beider Varianten wird diskutiert und numerische Ergebnisse werden angegeben.
    Notes: Abstract Recently, we introduced a cheap modification of Hackbusch'sFrequency Decomposition multi-level method. In this paper, the multiplicative variant of this method is studied. Using the theory of Subspace Correction Methods robustness is proved of both the multiplicative and additive variant applied to anisotropic problems in an arbitrary number of space dimensions. Implementation of both variants is discussed and numerical results are given.
    Type of Medium: Electronic Resource
    URL: http://dx.doi.org/10.1007/BF02238231
    Location Call Number Expected Availability
    BibTip Others were also interested in ...
    Paper (German National Licenses)
    Fulltext
  • 92
    Electronic Resource
    Electronic Resource
    Reducing the wrapping effect (1995)
    Springer
    Computing 54 (1995), S. 347-357 
    Details
    ISSN: 1436-5057
    Keywords: 65G10 ; 65L05 ; 65L07 ; Interval arithmetic ; interval methods for the initial value problem
    Source: Springer Online Journal Archives 1860-2000
    Topics: Computer Science
    Description / Table of Contents: Zusammenfassung Wenn Systeme gewöhnlicher Differentialgleichungen mit Intervallmethoden gelöst werden, besteht die Hauptschwierigkeit in der Reduktion des Wrappingeffekts. Die verschiedenen bis jetzt vorgeschlagenen Lösungen sind nur bei engen Anfangsintervallen oder speziellen Gleichungsklassen anwendbar. Diese Arbeit beschreibt einen Algorithmus, der statt Intervallen eine größere Familie von Mengen verwendet. Der Algorithmus führt zu einem sehr geringen Wrappingeffekt und ist bei beliebigem Gleichungstyp und weiten Anfangsintervallen anwendbar. Zum gegenwärtigen Zeitpunkt können nur 2-dimensionale Probleme behandelt werden.
    Notes: Abstract When solving ODEs by interval methods, the main difficulty is reducing the wrapping effect. Various solutions have been put forward, all of which are applicable for narrow initial intervals or to particular classes of equations only. This paper describes an algorithm which, instead of intervals, uses a larger family of sets. The algorithm exhibits a very small wrapping effect and applies to any type of equation and initial region. For the time being it handles only two-dimensional equations.
    Type of Medium: Electronic Resource
    URL: http://dx.doi.org/10.1007/BF02238232
    Location Call Number Expected Availability
    BibTip Others were also interested in ...
    Paper (German National Licenses)
    Fulltext
  • 93
    Electronic Resource
    Electronic Resource
    An algorithm for locating all zeros of a real polynomial (1995)
    Springer
    Computing 54 (1995), S. 359-375 
    Details
    ISSN: 1436-5057
    Keywords: AMS(MOS) ; 65H05 ; Polynomial zeros ; Eulidean division of Chebyshev expansions ; Sturm sequences
    Source: Springer Online Journal Archives 1860-2000
    Topics: Computer Science
    Description / Table of Contents: Zusammenfassung Wir stellen einen global konvergenten Algorithmus zur Berechnung aller Nullstellen eines Polynomsp n ,p n (z) = ∑ v = 0 n a v z v, mit reellen Koeffizienten vor. Durch Aufspalten vonp n (exp(it)) in seinen Real-und Imaginärteil können wir mittels Euklidischer Division von Čebyševentwicklungen und durch Argumentation mit Sturmschen Ketten entscheiden, obp n Nullstellen im Einheitskreis hat und wie viele Nullstellen auf dem Rand und im Inneren davon liegen. Somit erhalten wir mittels einer Bisektionsstrategie die Beträge aller Nullstellen bis auf eine vorgegebene Genauigkeit, und zusätzlich finden wir die Argumente als reelle Nullstellen eines Polynoms niedrigen Grades. Auf diese Weise erzeugen wir Startnäherungen für alle Nullstellen, die in einem letzten Schritt mittels eines iterativen Prozesses höherer Konvergenzordnung verbessert werden (z.B. Newton- oder Bairstowverfahren).
    Notes: Abstract We present a globally convergent algorithm for calculating all zeros of a polynomialp n ,p n (z) = ∑ v = 0 n a v z v, with real coefficients. Splittingp n (exp(it)) into its real and imaginary part we can decide via Euclidean division of Chebyshev expansions and Sturm sequence argumentations whetherp n has some zeros on the unit circle and how many zeros lie on the boundary and in the interior of it. Hence, by a bisection strategy we get the moduli of all zeros to a prescribed accuracy, and additionally we find the arguments as real zeros of a low degree polynomial. In this way we generate starting approximations for all zeros which in a final step are refined by an iterative process of higher order of convergence (e.g. Newton's or Bairstow's method).
    Type of Medium: Electronic Resource
    URL: http://dx.doi.org/10.1007/BF02238233
    Location Call Number Expected Availability
    BibTip Others were also interested in ...
    Paper (German National Licenses)
    Fulltext
  • 94
    Electronic Resource
    Electronic Resource
    Monte Carlo radiosity (1995)
    Springer
    Computing 55 (1995), S. 23-42 
    Details
    ISSN: 1436-5057
    Keywords: Radiosity ; Monte Carlo ; algorithms ; stochastic convergence ; transillumination method ; stochastic shooting method ; variance reduction
    Source: Springer Online Journal Archives 1860-2000
    Topics: Computer Science
    Description / Table of Contents: Zusammenfassung Die vorgestellten neuen Radiosity Methoden für diffuse Szenen sind besonders geeignet, um die Lichtausbreitung in sehr komplexen Umgebungen in linearer Zeit zu berechnen. Die Verfahren beruhen auf rekursiven Algorithmen, die das Radiosity-Gleichungssystem mittels stochastischer Konvergenz löseu. Approximationen der ‘gathering-’ und ‘shooting-’ Verfahren werden statt einer exakten Berechnung jedes Reflexionsschrittes verwendet. Die Effizienz der Verfahren kann durch geeignete Varianzreduktionsmethoden verbessert werden.
    Notes: Abstract The fast radiosity-type methods for very complex diffuse environments, introduced herein, present a nearly linear-time solution. The outlined procedures rely on recursive algorithms with stochastic convergence for solving the radiosity equation system. Approximations of gathering and shooting at very low computational cost—rather than the exact matrix of a single reflection—are used. The efficiency of the methods will be increased by applying variance reduction techniques.
    Type of Medium: Electronic Resource
    URL: http://dx.doi.org/10.1007/BF02238235
    Location Call Number Expected Availability
    BibTip Others were also interested in ...
    Paper (German National Licenses)
    Fulltext
  • 95
    Electronic Resource
    Electronic Resource
    Bernstein form is inclusion monotone (1995)
    Springer
    Computing 55 (1995), S. 43-53 
    Details
    ISSN: 1436-5057
    Keywords: Interval analysis ; range computation ; inclusion monotonicity ; Bernstein coefficients
    Source: Springer Online Journal Archives 1860-2000
    Topics: Computer Science
    Description / Table of Contents: Zusammenfassung Bekanntlich ist der Wertebereich eines Polynomsf über einem Intervall durch den kleinsten und größten Koeffizienten vonf bezüglich der Bernstein Basis auf dem Intervall eingeschränkt. Dadurch wird eine IntervallerweiterungF vonf definiert, die sogenannte Bernstein Form. In dieser Arbeit zeigen wir, daß die Bernstein Form inklusionsmonoton ist, d. h. wenn.X⊇Y dannF(X)⊇F(Y).
    Notes: Abstract It is well known that the range of polynomialf over an interval is bounded by the smallest and the largest coefficient off with respect to the Bernstein basis over the interval. This defines an interval extensionF off, which is called Bernstein form. In this paper we show that the bernstein form is inclusion monotone, i.e.X⊇Y impliesF(X)⊇F(Y).
    Type of Medium: Electronic Resource
    URL: http://dx.doi.org/10.1007/BF02238236
    Location Call Number Expected Availability
    BibTip Others were also interested in ...
    Paper (German National Licenses)
    Fulltext
  • 96
    Electronic Resource
    Electronic Resource
    Variable steps for reversible integration methods (1995)
    Springer
    Computing 55 (1995), S. 1-22 
    Details
    ISSN: 1436-5057
    Keywords: 65L ; 34C ; Reversible integration ; symplectic integrators ; variable step size ; long time integration
    Source: Springer Online Journal Archives 1860-2000
    Topics: Computer Science
    Description / Table of Contents: Zusammenfassung Werden symplektische oder reversible Integrationsverfahren mit herkömmlichen Schrittweitensteuerungen verwendet, so geht die symplektische, bzw. die reversible Struktur des Problems verloren. In dieser Arbeit wird gezeigt, dass die symplektische Struktur des Verfahrens nur dann erhalten wird, wenn die Schrittweite fast konstant bleibt. Für reversible Verfahren sind echt variable Schrittweiten möglich, die Schrittweite muss jedoch für “gespiegelte” Schritte gleich sein. Es werden verschiedene Wege aufgezeigt, um reversible, variable Schrittweiten zu konstruieren. Numerische Experimente zeigen, dass für das Keplerproblem die neuen Methoden den herkömmlichen Schrittweitensteuerungen oder den symplektischen Verfahren mit konstanter Schrittweite überlegen sind. Insbesondere wächst der globale Fehler linear.
    Notes: Abstract Conventional variable-step implementation of symplectic or reversible integration methods destroy the symplectic or reversible structure of the system. We show that to preserve the symplectic structure of a method the step size has to be kept almost constant. For reversible methods variable steps are possible but the step size has to be equal for “reflected” steps. We demonstrate possible ways to construct reversible variable step size methods. Numerical experiments show that for the Kepler problem the new methods perform better than conventional variable step size methods or symplectic constant step size methods. In particular they exhibit linear growth of the global error (as symplectic methods with constant step size).
    Type of Medium: Electronic Resource
    URL: http://dx.doi.org/10.1007/BF02238234
    Location Call Number Expected Availability
    BibTip Others were also interested in ...
    Paper (German National Licenses)
    Fulltext
  • 97
    Electronic Resource
    Electronic Resource
    On the numerical solution of nonlinear eigenvalue problems (1995)
    Springer
    Computing 55 (1995), S. 91-111 
    Details
    ISSN: 1436-5057
    Keywords: 65F15 (47A56) ; Nonlinear eigenvalue problem ; numerical solution ; condition number
    Source: Springer Online Journal Archives 1860-2000
    Topics: Computer Science
    Description / Table of Contents: Zusammenfassung Wir betrachten die numerische Lösung des nichtlinearen EigenwertproblemsA(λ)x=0, wobei die MatrixA(λ) in nichtlinearer Weise vom Eigenwertparameter λ abhängt. Einige neue Methoden (die BDS Methoden) werden zusammen mit einer Untersuchung der Bedingungen dieser Methoden vorgestellt. Numerische Beispiele, welche diese Methoden vergleichen, werden präsentiert.
    Notes: Abstract We consider the numerical solution of the nonlinear eigenvalue problemA(λ)x=0, where the matrixA(λ) is dependent on the eigenvalue parameter λ nonlinearly. Some new methods (the BDS methods) are presented, together with the analysis of the condition of the methods. Numerical examples comparing the methods are given.
    Type of Medium: Electronic Resource
    URL: http://dx.doi.org/10.1007/BF02238095
    Location Call Number Expected Availability
    BibTip Others were also interested in ...
    Paper (German National Licenses)
    Fulltext
  • 98
    Electronic Resource
    Electronic Resource
    Set-Oriented retrieval of complex objects in inheritance hierarchies (1995)
    Springer
    Computing 55 (1995), S. 55-73 
    Details
    ISSN: 1436-5057
    Keywords: 68P [Theory of data] ; 68P05 Data structures ; 68P20 information storage and retrieval ; Object-oriented data models ; ISA hierarchy ; complex objects ; transitive closure
    Source: Springer Online Journal Archives 1860-2000
    Topics: Computer Science
    Description / Table of Contents: Zusammenfassung In den letzten Jahren sind viele objekt-orientierte Datenmodelle vorgeschlagen worden und dieses Gebiet ist zu einem der vielversprechendsten für die Entwicklung neuer Datenbanksysteme geworden. Bei Verwendung von komplexen Datenstrukturen, auf denen eine ISA Hierarchie definiert ist, wird effizientes Speichern and Zugreifen auf Objekte um vieles wichtiger. In dieser Arbeit schlagen wir effiziente mengenorientierte Algorithmen zur Speicherung und zum Zugriff auf komplexe Objekte in einer „Inheritance Hierarchie” vor.
    Notes: Abstract Many object oriented data models have been proposed in the past few years, and this field is one of the most promising for the development of new generation database systems. With complex data structures where an ISA hierarchy has been defined, the problem of efficiently storing and retrieving (a collection of) objects increases its relevance dramatically. This paper proposes efficient set-oriented algorithms for the storage and retrieval of complex objects in an inheritance hierarchy.
    Type of Medium: Electronic Resource
    URL: http://dx.doi.org/10.1007/BF02238237
    Location Call Number Expected Availability
    BibTip Others were also interested in ...
    Paper (German National Licenses)
    Fulltext
  • 99
    Electronic Resource
    Electronic Resource
    Fast approximate matching of words against a dictionary (1995)
    Springer
    Computing 55 (1995), S. 75-89 
    Details
    ISSN: 1436-5057
    Keywords: 68Q20 ; 90C39 ; String edit distance ; finte state automaton ; nearest neighbor search ; doctionary lookup
    Source: Springer Online Journal Archives 1860-2000
    Topics: Computer Science
    Description / Table of Contents: Zusammenfassung Es wird ein neuer Algorithmus für die Berechnung der Editierdistanz von Zeichenketten angegeben. Der Algorithmus beruht auf der Annahme, dass eine der beiden zu vergleichenden Zeichenketten ein a priori bekannter Eintrag in einen Wörterbuch ist. Dieser Wörterbucheintrag wird in einer off-line Phase in einen deterministischen endlichen Automaten konvertiert. Für einen gegebenen Automaten und ein Eingabewort entspricht die Berechnung der Editiordistanz einer Traversierung verschiedener Zustände dieses Automaten. Diese Prozedur benötigt Zeit, die lediglich linear von der Länge des Eingabeworts abhängt. Die Zeit ist unabhängig von der Länge des Wörterbucheintrags. Die endlichen Automaten, welche zuN verschiedenen Wörterbucheinträgen gehören, können zu einem einzigen Automaten zusammengefasst werden. Auf diese Weise benötigen die Berechnung der Editierdistanz zwischen dem Eingabewort und jedem Wörterbucheintrag sowie die Bestimmung des nächsten Nachbarn im Wörterbuch lediglich lineare Zeit hinsichtlich der Länge des Eingabeworts. Die Anzahl der Zustände des Automaten ist jedoch von exponentieller Grössenordnung.
    Notes: Abstract A new algorithm for string edit distance computation is given. The algorithm assumes that one of the two strings to be compared is a dictionary entry that is known a priori. This dictionary word is converted in an off-line phase into a deterministic finite state automaton. Given an input string and the automaton derived from the dictionary word, the computation of the edit distance between the two strings corresponds to a traversal of the states of the automaton. This procedure needs time which is only linear in the length of the input string. It is independent of the length of the dictionary word. Given not only one butN different dictionary words, their corresponding automata can be combined into a single deterministic finite state automaton. Thus the computation of the edit distance between the input word and each dictionary entry, and the determination of the nearest neighbor in the dictionary need time that is only linear in the length of the input string. However, the number os states of the automation is exponential.
    Type of Medium: Electronic Resource
    URL: http://dx.doi.org/10.1007/BF02238238
    Location Call Number Expected Availability
    BibTip Others were also interested in ...
    Paper (German National Licenses)
    Fulltext
  • 100
    Electronic Resource
    Electronic Resource
    On the stability of numerical methods of Hopf points using backward error analysis (1995)
    Springer
    Computing 55 (1995), S. 163-180 
    Details
    ISSN: 1436-5057
    Keywords: 65L05 ; Hopf bifurcation ; Runge-Kutta ; Poincare map
    Source: Springer Online Journal Archives 1860-2000
    Topics: Computer Science
    Description / Table of Contents: Zusammenfassung Um das Verhalten bestimmter Ein- und Mehrschrittverfahren für gewöhnliche Differentialgleichungen an schwach anziehenden Fixpunkten bzw. schwach anziehenden periodischen Lösungen zu untersuchen, wird Rückwärts-Fehleranalyse eingesetzt. Bei vielen Methoden tritt eine Hopf-Verzweigung auf; der Effekt einer adaptiven Gitteranpassung für solche Situationen wird an einem Spezialfall demonstriert.
    Notes: Abstract Backward error analysis is used to analyze the behavior of selected one-step and multi-step methods for ordinary differential equations at weakly attracting fixed points and weakly attracting periodic solutions. For many methods, a Hopf bifurcation for maps occurs. The effect of an adaptive mesh selection procedure on these results is presented for a special case.
    Type of Medium: Electronic Resource
    URL: http://dx.doi.org/10.1007/BF02238099
    Location Call Number Expected Availability
    BibTip Others were also interested in ...
    Paper (German National Licenses)
    Fulltext
Close ⊗
This website uses cookies and the analysis tool Matomo. More information can be found here...