ALBERT

All Library Books, journals and Electronic Records Telegrafenberg

Ihre E-Mail wurde erfolgreich gesendet. Bitte prüfen Sie Ihren Maileingang.

Leider ist ein Fehler beim E-Mail-Versand aufgetreten. Bitte versuchen Sie es erneut.

Vorgang fortführen?

Exportieren
Filter
  • Artikel  (47)
  • Linear programming  (24)
  • 41A15  (23)
  • Springer  (47)
  • American Chemical Society
  • American Institute of Physics (AIP)
  • Blackwell Publishing Ltd
  • Cambridge University Press
  • 2020-2024
  • 1990-1994  (37)
  • 1985-1989  (7)
  • 1975-1979  (3)
  • 1965-1969
  • 1940-1944
  • 1930-1934
  • 2020
  • 1993  (37)
  • 1985  (7)
  • 1977  (3)
  • 1933
  • Mathematik  (46)
  • Land- und Forstwirtschaft, Gartenbau, Fischereiwirtschaft, Hauswirtschaft  (1)
  • Pädagogik
  • Geographie
  • Energietechnik
Sammlung
  • Artikel  (47)
Schlagwörter
Verlag/Herausgeber
  • Springer  (47)
  • American Chemical Society
  • American Institute of Physics (AIP)
  • Blackwell Publishing Ltd
  • Cambridge University Press
Erscheinungszeitraum
  • 2020-2024
  • 1990-1994  (37)
  • 1985-1989  (7)
  • 1975-1979  (3)
  • 1965-1969
  • +
Jahr
Thema
  • 1
    Digitale Medien
    Digitale Medien
    Springer
    Mathematical programming 58 (1993), S. 243-255 
    ISSN: 1436-4646
    Schlagwort(e): Linear programming ; interior point algorithm ; primal—dual potential function
    Quelle: Springer Online Journal Archives 1860-2000
    Thema: Informatik , Mathematik
    Notizen: Abstract This paper is concerned with selection of theρ-parameter in the primal—dual potential reduction algorithm for linear programming. Chosen from [n + $$\sqrt n $$ , ∞), the level ofρ determines the relative importance placed on the centering vs. the Newton directions. Intuitively, it would seem that as the iterate drifts away from the central path towards the boundary of the positive orthant,ρ must be set close ton + $$\sqrt n $$ . This increases the relative importance of the centering direction and thus helps to ensure polynomial convergence. In this paper, we show that this is unnecessary. We find for any iterate thatρ can be sometimes chosen in a wide range [n + $$\sqrt n $$ , ∞) while still guaranteeing the currently best convergence rate of O( $$\sqrt n $$ L) iterations. This finding is encouraging since in practice large values ofρ have resulted in fast convergence rates. Our finding partially complements the recent result of Zhang, Tapia and Dennis (1990) concerning the local convergence rate of the algorithm.
    Materialart: Digitale Medien
    Standort Signatur Erwartet Verfügbarkeit
    BibTip Andere fanden auch interessant ...
  • 2
    Digitale Medien
    Digitale Medien
    Springer
    Mathematical programming 59 (1993), S. 133-150 
    ISSN: 1436-4646
    Schlagwort(e): Linear programming ; interior-point methods ; combined phase I—phase II
    Quelle: Springer Online Journal Archives 1860-2000
    Thema: Informatik , Mathematik
    Notizen: Abstract This paper describes an affine potential reduction algorithm for linear programming that simultaneously seeks feasibility and optimality. The algorithm is closely related to a similar method of Anstreicher. The new features are that we use a two-dimensional programming problem to derive better lower bounds than Anstreicher, that our direction-finding subproblem treats phase I and phase II more symmetrically, and that we do not need an initial lower bound. Our method also allows for the generation of a feasible solution (so that phase I is terminated) during the course of the iterations, and we describe two ways to encourage this behavior.
    Materialart: Digitale Medien
    Standort Signatur Erwartet Verfügbarkeit
    BibTip Andere fanden auch interessant ...
  • 3
    Digitale Medien
    Digitale Medien
    Springer
    Mathematical programming 59 (1993), S. 151-162 
    ISSN: 1436-4646
    Schlagwort(e): Linear programming ; primal and dual ; superlinear and quadratic convergence ; polynomiality
    Quelle: Springer Online Journal Archives 1860-2000
    Thema: Informatik , Mathematik
    Notizen: Abstract Recently, Ye, Tapia and Zhang (1991) demonstrated that Mizuno—Todd—Ye's predictor—corrector interior-point algorithm for linear programming maintains the O( $$\sqrt n $$ L)-iteration complexity while exhibiting superlinear convergence of the duality gap to zero under the assumption that the iteration sequence converges, and quadratic convergence of the duality gap to zero under the assumption of nondegeneracy. In this paper we establish the quadratic convergence result without any assumption concerning the convergence of the iteration sequence or nondegeneracy. This surprising result, to our knowledge, is the first instance of a demonstration of polynomiality and superlinear (or quadratic) convergence for an interior-point algorithm which does not assume the convergence of the iteration sequence or nondegeneracy.
    Materialart: Digitale Medien
    Standort Signatur Erwartet Verfügbarkeit
    BibTip Andere fanden auch interessant ...
  • 4
    Digitale Medien
    Digitale Medien
    Springer
    Mathematical programming 59 (1993), S. 413-420 
    ISSN: 1436-4646
    Schlagwort(e): Linear programming ; prize collecting ; rounding fractional solutions ; traveling salesman problem ; worst-case analysis
    Quelle: Springer Online Journal Archives 1860-2000
    Thema: Informatik , Mathematik
    Notizen: Abstract We study the version of the prize collecting traveling salesman problem, where the objective is to find a tour that visits a subset of vertices such that the length of the tour plus the sum of penalties associated with vertices not in the tour is as small as possible. We present an approximation algorithm with constant bound. The algorithm is based on Christofides' algorithm for the traveling salesman problem as well as a method to round fractional solutions of a linear programming relaxation to integers, feasible for the original problem.
    Materialart: Digitale Medien
    Standort Signatur Erwartet Verfügbarkeit
    BibTip Andere fanden auch interessant ...
  • 5
    Digitale Medien
    Digitale Medien
    Springer
    Mathematical programming 62 (1993), S. 517-535 
    ISSN: 1436-4646
    Schlagwort(e): Linear programming ; Karmarkar's algorithm ; Projective algorithm ; Standard form
    Quelle: Springer Online Journal Archives 1860-2000
    Thema: Informatik , Mathematik
    Notizen: Abstract In a recent paper, Shaw and Goldfarb show that a version of the standard form projective algorithm can achieve $$O\left( {\sqrt {nL} } \right)$$ step complexity, as opposed to the O(nL) step complexity originally demonstrated for the algorithm. The analysis of Shaw and Goldfarb shows that the algorithm, using a constant, fixed steplength, approximately follows the central trajectory. In this paper we show that simple modifications of the projective algorithm obtain the same complexity improvement, while permitting a linesearch of the potential function on each step. An essential component is the addition of a single constraint, motivated by Shaw and Goldfarb's analysis, which makes the standard form algorithm strictly monotone in the true objective.
    Materialart: Digitale Medien
    Standort Signatur Erwartet Verfügbarkeit
    BibTip Andere fanden auch interessant ...
  • 6
    Digitale Medien
    Digitale Medien
    Springer
    European journal of nutrition 32 (1993), S. 79-92 
    ISSN: 1436-6215
    Schlagwort(e): Lineare Programmierung ; Ernährungsoptimierung ; Privathaushalt ; Optimierungsmodelle ; Linear programming ; nutrition optimization ; private households ; optimization models
    Quelle: Springer Online Journal Archives 1860-2000
    Thema: Land- und Forstwirtschaft, Gartenbau, Fischereiwirtschaft, Hauswirtschaft , Medizin
    Beschreibung / Inhaltsverzeichnis: Summary Members of private households have different nutrient requirements. In general, they eat the same dishes in different quantities. The menu plan is admissible if it corresponds to the recommended dietary allowances. It is acceptable if it meets the eating habits. It is optimal if it meets the constraints mentioned and best reaches an objective. It is the aim of this paper to describe models for the determination of optimal nutrition and to evaluate them with respect to their suitability for solving decision problems in private, multi-person-households. The fewer the model-intern restrictions in the variability of quantities of food stuffs, kind and/or quantities of dishes, the better are the “optimal” solutions that are found with the model. A simultaneous determination of kind and quantity of dishes reaches the model purpose better than a stepwise determination. This is shown in an example problem.
    Notizen: Zusammenfassung In privaten Haushalten haben die Mitglieder unterschiedliche Nährstoffbedarfe. Sie verzehren im allgemeinen gleiche Speisen in unterschiedlichen Mengen. Der Speisenplan ist bedarfsgerecht, wenn er den Empfehlungen für die Nährstoffzufuhr der einzelnen Personen entspricht. Er ist akzeptabel, wenn er den Verzehrgewohnheiten der Personen entspricht. Er ist optimal, wenn er die genannten Bedingungen einhält und zusätzlich ein gegebenes Ziel bestmöglich erreicht. Die Bestimmung eines optimalen Speisenplans erfolgt anhand von Modellen. Es ist das Ziel des Beitrags, verschiedene Modelle zur Bestimmung einer optimalen Ernährung darzustellen und im Hinblick auf ihre Eignung zur Anwendung auf Entscheidungsprobleme im privaten Mehrpersonenhaushalt zu beurteilen. Je geringer die modellinterne Einschränkung in der Variabilität von Lebensmittelmengen, Speisenarten und/oder Speisenmengen, desto bessere ‚optimale‘ Lösungen können mit dem Modell gefunden werden. Eine simultane Bestimmung von Speisenart und -menge erfüllt den Modellzweck besser als eine sukzessive Bestimmung. Dies konnte anhand eines Beispielproblems gezeigt werden.
    Materialart: Digitale Medien
    Standort Signatur Erwartet Verfügbarkeit
    BibTip Andere fanden auch interessant ...
  • 7
    Digitale Medien
    Digitale Medien
    Springer
    Mathematical programming 59 (1993), S. 23-31 
    ISSN: 1436-4646
    Schlagwort(e): Linear programming ; duality theorem ; unimodular ; totally unimodular ; interior point methods
    Quelle: Springer Online Journal Archives 1860-2000
    Thema: Informatik , Mathematik
    Notizen: Abstract In this paper we consider a linear programming problem with the underlying matrix unimodular, and the other data integer. Given arbitrary near optimum feasible solutions to the primal and the dual problems, we obtain conditions under which statements can be made about the value of certain variables in optimal vertices. Such results have applications to the problem of determining the stopping criterion in interior point methods like the primal—dual affine scaling method and the path following methods for linear programming.
    Materialart: Digitale Medien
    Standort Signatur Erwartet Verfügbarkeit
    BibTip Andere fanden auch interessant ...
  • 8
    Digitale Medien
    Digitale Medien
    Springer
    Annals of operations research 46-47 (1993), S. 409-430 
    ISSN: 1572-9338
    Schlagwort(e): Linear programming ; Phase I ; nonlinear programming ; least squares ; quadratic programming ; strict improvement ; degeneracy
    Quelle: Springer Online Journal Archives 1860-2000
    Thema: Mathematik , Wirtschaftswissenschaften
    Notizen: Abstract Instead of trying to recognize and avoid degenerate steps in the simplex method (as some variants do), we have developed a new Phase I algorithm that is impervious to degeneracy. The new algorithm solves a non-negative least-squares problem in order to find a Phase I solution. In each iteration, a simple two-variable least-squares subproblem is used to select an incoming column to augment a set of independent columns (called “basic”) to get a strictly better fit to the right-hand side. Although this is analogous in many ways to the simplex method, it can be proved that strict improvement is attained at each iteration, even in the presence of degeneracy. Thus cycling cannot occur, and convergence is guaranteed. This algorithm is closely related to a number of existing algorithms proposed for non-negative least-squares and quadratic programs. When used on the 30 smallest NETLIB linear programming test problems, the computational results for the new Phase I algorithm were almost 3.5 times faster than a particular implementation of the simplex method; on some problems, it was over 10 times faster. Best results were generally seen on the more degenerate problems.
    Materialart: Digitale Medien
    Standort Signatur Erwartet Verfügbarkeit
    BibTip Andere fanden auch interessant ...
  • 9
    Digitale Medien
    Digitale Medien
    Springer
    Annals of operations research 46-47 (1993), S. 107-138 
    ISSN: 1572-9338
    Schlagwort(e): Linear programming ; interior point methods ; degeneracy ; polynomial algorithms ; global and local convergence ; basis recovery ; numerical performance ; sensitivity analysis
    Quelle: Springer Online Journal Archives 1860-2000
    Thema: Mathematik , Wirtschaftswissenschaften
    Notizen: Abstract The publication of Karmarkar's paper has resulted in intense research activity into Interior Point Methods (IPMs) for linear programming. Degeneracy is present in most real-life problems and has always been an important issue in linear programming, especially in the Simplex method. Degeneracy is also an important issue in IPMs. However, the difficulties are different in the two methods. In this paper, we survey the various theoretical and practical issues related to degeneracy in IPMs for linear programming. We survey results, which, for the most part, have already appeared in the literature. Roughly speaking, we shall deal with the effect of degeneracy on the following: the convergence of IPMs, the trajectories followed by the algorithms, numerical performance, and finding basic solutions.
    Materialart: Digitale Medien
    Standort Signatur Erwartet Verfügbarkeit
    BibTip Andere fanden auch interessant ...
  • 10
    Digitale Medien
    Digitale Medien
    Springer
    Annals of operations research 46-47 (1993), S. 235-248 
    ISSN: 1572-9338
    Schlagwort(e): Linear programming ; generalized networks ; simplex method ; degeneracy ; lexicography ; cycling
    Quelle: Springer Online Journal Archives 1860-2000
    Thema: Mathematik , Wirtschaftswissenschaften
    Notizen: Abstract This paper introduces an analytical approach for studying lexicography in generalized network problems. The equations obtained can help us to understand and to extend the existing theory. First, it is verified that all nonzero elements have the same sign in each row vector of a basis inverse for a generalized network (GN) problem with positive multipliers. However, this property does not necessarily hold when there exist negative multipliers. Second, we developed a strategy to select the dropping arc in the GN simplex algorithm when addressing GN problems with positive andnegative multipliers. This strategy is also based on lexicography and requires performing some comparisons. However, the values to be compared are already known since they can be obtained as a by-product of the calculations necessary to compute the basis representation of the entering arc. Consequently, the computational effort per pivot step isO(n) in the worst case. This worst case effort is the same as that required by the strongly convergent rules for selecting the dropping arc in the method of strong convergence.
    Materialart: Digitale Medien
    Standort Signatur Erwartet Verfügbarkeit
    BibTip Andere fanden auch interessant ...
  • 11
    Digitale Medien
    Digitale Medien
    Springer
    Annals of operations research 46-47 (1993), S. 203-233 
    ISSN: 1572-9338
    Schlagwort(e): Linear programming ; simplex method ; pivot rules ; cycling ; recursion ; minimal index rule ; parametric programming
    Quelle: Springer Online Journal Archives 1860-2000
    Thema: Mathematik , Wirtschaftswissenschaften
    Notizen: Abstract The purpose of this paper is to discuss the various pivot rules of the simplex method and its variants that have been developed in the last two decades, starting from the appearance of the minimal index rule of Bland. We are mainly concerned with finiteness properties of simplex type pivot rules. Well known classical results concerning the simplex method are not considered in this survey, but the connection between the new pivot methods and the classical ones, if there is any, is discussed. In this paper we discuss three classes of recently developed pivot rules for linear programming. The first and largest class is the class of essentially combinatorial pivot rules including minimal index type rules and recursive rules. These rules only use labeling and signs of the variables. The second class contains those pivot rules which can actually be considered as variants or generalizations or specializations of Lemke's method, and so they are closely related to parametric programming. The last class has the common feature that the rules all have close connections to certain interior point methods. Finally, we mention some open problems for future research.
    Materialart: Digitale Medien
    Standort Signatur Erwartet Verfügbarkeit
    BibTip Andere fanden auch interessant ...
  • 12
    Digitale Medien
    Digitale Medien
    Springer
    Annals of operations research 46-47 (1993), S. 431-442 
    ISSN: 1572-9338
    Schlagwort(e): Linear programming ; degeneracy ; network simplex algorithm ; pivoting ; minimal cost network flow
    Quelle: Springer Online Journal Archives 1860-2000
    Thema: Mathematik , Wirtschaftswissenschaften
    Notizen: Abstract A characteristic feature of the primal network simplex algorithm (NSA) is that it usually makes a large number of degenerate iterations. Though cycling and even stalling can be avoided by recently introduced pivot rules for NSA, the practical efficiency of these rules is not known yet. For the case when the simplex algorithm is used to solve the continuous linear programming (LP) problem there exists a practical anti-cycling procedure that proved to be efficient. It is based on an expanding relaxation of the individual bound on the variables. In this paper we discuss the adaptation of this method to NSA, taking advantage of the special integer nature of network problems. We also give an account of our experience with these ideas as they are experimentally implemented in the MINET network LP solver. Reductions of CPU time have been achieved on a smaller set of specially structured real-life problems.
    Materialart: Digitale Medien
    Standort Signatur Erwartet Verfügbarkeit
    BibTip Andere fanden auch interessant ...
  • 13
    Digitale Medien
    Digitale Medien
    Springer
    BIT 33 (1993), S. 512-528 
    ISSN: 1572-9125
    Schlagwort(e): 65D10 ; 65D07 ; 41A15 ; 41A29 ; Data fitting ; smoothing ; shape preservation ; constrained least squares approximation ; polynomial splines ; B-splines
    Quelle: Springer Online Journal Archives 1860-2000
    Thema: Mathematik
    Notizen: Abstract An efficient algorithm for computing a smoothing polynomial splines under inequality constraints on derivatives is introduced where both order and breakpoints ofs can be prescribed arbitrarily. By using the B-spline representation ofs, the original semi-infinite constraints are replaced by stronger finite ones, leading to a least squares problem with linear inequality constraints. Then these constraints are transformed into simple box constraints by an appropriate substitution of variables so that efficient standard techniques for solving such problems can be applied. Moreover, the smoothing term commonly used is replaced by a cheaply computable approximation. All matrix transformations are realized by numerically stable Givens rotations, and the band structure of the problem is exploited as far as possible.
    Materialart: Digitale Medien
    Standort Signatur Erwartet Verfügbarkeit
    BibTip Andere fanden auch interessant ...
  • 14
    Digitale Medien
    Digitale Medien
    Springer
    Advances in computational mathematics 1 (1993), S. 1-37 
    ISSN: 1572-9044
    Schlagwort(e): Refinement equations ; up-function ; entire functions of exponential type ; subdivision algorithms ; cube spline ; (AMS) 34K99 ; 41A15 ; 41A25 ; 41A63
    Quelle: Springer Online Journal Archives 1860-2000
    Thema: Mathematik
    Notizen: Abstract This paper is concerned with the study of a general class of functional equations covering as special cases the relation which defines theup-function as well as equations which arise in multiresolution analysis for wavelet construction. We discuss various basic properties of solutions to these functional equations such as regularity, polynomial containment within the space spanned by their integer shifts and their computability by subdivision algorithms.
    Materialart: Digitale Medien
    Standort Signatur Erwartet Verfügbarkeit
    BibTip Andere fanden auch interessant ...
  • 15
    Digitale Medien
    Digitale Medien
    Springer
    Numerische Mathematik 66 (1993), S. 123-137 
    ISSN: 0945-3245
    Schlagwort(e): 41A55 ; 41A15 ; 41A05 ; 65D32 ; 65D30 ; 65D07 ; 65D05
    Quelle: Springer Online Journal Archives 1860-2000
    Thema: Mathematik
    Notizen: Summary The Gregory rule is a well-known example in numerical quadrature of a trapezoidal rule with endpoint corrections of a given order. In the literature, the methods of constructing the Gregory rule have, in contrast to Newton-Cotes quadrature,not been based on the integration of an interpolant. In this paper, after first characterizing an even-order Gregory interpolant by means of a generalized Lagrange interpolation operator, we proceed to explicitly construct such an interpolant by employing results from nodal spline interpolation, as established in recent work by the author and C.H. Rohwer. Nonoptimal order error estimates for the Gregory rule of even order are then easily obtained.
    Materialart: Digitale Medien
    Standort Signatur Erwartet Verfügbarkeit
    BibTip Andere fanden auch interessant ...
  • 16
    Digitale Medien
    Digitale Medien
    Springer
    Mathematical programming 59 (1993), S. 345-360 
    ISSN: 1436-4646
    Schlagwort(e): Linear programming ; interior point method ; active set strategy
    Quelle: Springer Online Journal Archives 1860-2000
    Thema: Informatik , Mathematik
    Notizen: Abstract We will present a potential reduction method for linear programming where only the constraints with relatively small dual slacks—termed “active constraints”—will be taken into account to form the ellipsoid constraint at each iteration of the process. The algorithm converges to the optimal feasible solution in O( $$\sqrt n $$ L) iterations with the same polynomial bound as in the full constraints case, wheren is the number of variables andL is the data length. If a small portion of the constraints is active near the optimal solution, the computational cost to find the next direction of movement in one iteration may be considerably reduced by the proposed strategy.
    Materialart: Digitale Medien
    Standort Signatur Erwartet Verfügbarkeit
    BibTip Andere fanden auch interessant ...
  • 17
    Digitale Medien
    Digitale Medien
    Springer
    Mathematical programming 61 (1993), S. 39-52 
    ISSN: 1436-4646
    Schlagwort(e): Linear programming ; quadratic programming ; convex programming ; randomized algorithms ; fixed dimension optimization problems ; complexity
    Quelle: Springer Online Journal Archives 1860-2000
    Thema: Informatik , Mathematik
    Notizen: Abstract We extend Clarkson's randomized algorithm for linear programming to a general scheme for solving convex optimization problems. The scheme can be used to speed up existing algorithms on problems which have many more constraints than variables. In particular, we give a randomized algorithm for solving convex quadratic and linear programs, which uses that scheme together with a variant of Karmarkar's interior point method. For problems withn constraints,d variables, and input lengthL, ifn = Ω(d 2), the expected total number of major Karmarkar's iterations is O(d 2(logn)L), compared to the best known deterministic bound of O( $$\sqrt n$$ L). We also present several other results which follow from the general scheme.
    Materialart: Digitale Medien
    Standort Signatur Erwartet Verfügbarkeit
    BibTip Andere fanden auch interessant ...
  • 18
    Digitale Medien
    Digitale Medien
    Springer
    Mathematical programming 62 (1993), S. 41-67 
    ISSN: 1436-4646
    Schlagwort(e): Linear programming ; Dantzig—Wolfe decomposition ; large-scale systems ; parallel processing ; hypercube architecture
    Quelle: Springer Online Journal Archives 1860-2000
    Thema: Informatik , Mathematik
    Notizen: Abstract Decomposition algorithms for block-angular linear programs give rise to a natural, coarse-grained parallelism that can be exploited by processing the subproblems concurrently within a distributed-memory environment. The parallel efficiency of the distributed approach, however, is critically dependent on the duration of the inherently serial master phase relative to that of the bottleneck subproblem. This paper investigates strategies for improving efficiency in distributed Dantzig—Wolfe decomposition by better balancing the load between the master and subproblem processors. We report computational experience on an Intel iPSC/2 hypercube multiprocessor with test problems having dimensions up to about 30 000 rows, 87 000 columns, and 200 coupling constraints.
    Materialart: Digitale Medien
    Standort Signatur Erwartet Verfügbarkeit
    BibTip Andere fanden auch interessant ...
  • 19
    Digitale Medien
    Digitale Medien
    Springer
    Mathematical programming 62 (1993), S. 15-39 
    ISSN: 1436-4646
    Schlagwort(e): Linear programming ; interior-point methods ; symmetric indefinite systems
    Quelle: Springer Online Journal Archives 1860-2000
    Thema: Informatik , Mathematik
    Notizen: Abstract We describe an implementation of a primal—dual path following method for linear programming that solves symmetric indefinite “augmented” systems directly by Bunch—Parlett factorization, rather than reducing these systems to the positive definite “normal equations” that are solved by Cholesky factorization in many existing implementations. The augmented system approach is seen to avoid difficulties of numerical instability and inefficiency associated with free variables and with dense columns in the normal equations approach. Solving the indefinite systems does incur an extra overhead, whose median is about 40% in our tests; but the augmented system approach proves to be faster for a minority of cases in which the normal equations have relatively dense Cholesky factors. A detailed analysis shows that the augmented system factorization is reliable over a fairly large range of the parameter settings that control the tradeoff between sparsity and numerical stability.
    Materialart: Digitale Medien
    Standort Signatur Erwartet Verfügbarkeit
    BibTip Andere fanden auch interessant ...
  • 20
    Digitale Medien
    Digitale Medien
    Springer
    Mathematical programming 62 (1993), S. 119-131 
    ISSN: 1436-4646
    Schlagwort(e): Linear programming ; interior point algorithm ; complexity ; potential function
    Quelle: Springer Online Journal Archives 1860-2000
    Thema: Informatik , Mathematik
    Notizen: Abstract We propose a potential-reduction algorithm which always uses the primal—dual affine-scaling direction as a search direction. We choose a step size at each iteration of the algorithm such that the potential function does not increase, so that we can take a longer step size than the minimizing point of the potential function. We show that the algorithm is polynomial-time bounded. We also propose a low-complexity algorithm, in which the centering direction is used whenever an iterate is far from the path of centers.
    Materialart: Digitale Medien
    Standort Signatur Erwartet Verfügbarkeit
    BibTip Andere fanden auch interessant ...
  • 21
    Digitale Medien
    Digitale Medien
    Springer
    Mathematical programming 62 (1993), S. 497-515 
    ISSN: 1436-4646
    Schlagwort(e): Linear programming ; primal—dual methods ; optimal face ; strict complementarity
    Quelle: Springer Online Journal Archives 1860-2000
    Thema: Informatik , Mathematik
    Notizen: Abstract We study the problem of finding a point in the relative interior of the optimal face of a linear program. We prove that in the worst case such a point can be obtained in O(n 3 L) arithmetic operations. This complexity is the same as the complexity for solving a linear program. We also show how to find such a point in practice. We report and discuss computational results obtained for the linear programming problems in the NETLIB test set.
    Materialart: Digitale Medien
    Standort Signatur Erwartet Verfügbarkeit
    BibTip Andere fanden auch interessant ...
  • 22
    Digitale Medien
    Digitale Medien
    Springer
    Algorithmica 9 (1993), S. 64-83 
    ISSN: 1432-0541
    Schlagwort(e): Linear programming ; Interior-point methods ; Projective methods ; Combined phase 1-phase 2
    Quelle: Springer Online Journal Archives 1860-2000
    Thema: Informatik , Mathematik
    Notizen: Abstract We compare the projective methods for linear programming due to de Ghellinck and Vial, Anstreicher, Todd, and Fraley. These algorithms have the feature that they approach feasibility and optimality simultaneously, rather than requiring an initial feasible point. We compare the directions used in these methods and the lower-bound updates employed. In many cases the directions coincide and two of the lower-bound updates give the same result. It appears that Todd's direction and Fraley's lower-bound update have slight advantages, and this is borne out in limited computational testing.
    Materialart: Digitale Medien
    Standort Signatur Erwartet Verfügbarkeit
    BibTip Andere fanden auch interessant ...
  • 23
    Digitale Medien
    Digitale Medien
    Springer
    Algorithmica 9 (1993), S. 184-197 
    ISSN: 1432-0541
    Schlagwort(e): Linear programming ; Karmarkar's algorithm ; Potential function ; Primal-dual, Modified method ; Rank-one updates
    Quelle: Springer Online Journal Archives 1860-2000
    Thema: Informatik , Mathematik
    Notizen: Abstract We consider partial updating in Kojima, Mizuno, and Yoshise's primal-dual potential reduction algorithm for linear programming. We use a simple safeguard condition to control the number of updates incurred on combined primal-dual steps. Our analysis allows for unequal steplengths in the primal and dual variables, which appears to be a computationally significant factor for primal-dual methods. The safeguard we use is a primal-dual Goldstein-Armijo condition, modified to deal with the unequal primal and dual steplengths.
    Materialart: Digitale Medien
    Standort Signatur Erwartet Verfügbarkeit
    BibTip Andere fanden auch interessant ...
  • 24
    Digitale Medien
    Digitale Medien
    Springer
    Numerische Mathematik 65 (1993), S. 63-75 
    ISSN: 0945-3245
    Schlagwort(e): 41A15 ; 65DO5 ; 65D15
    Quelle: Springer Online Journal Archives 1860-2000
    Thema: Mathematik
    Notizen: Summary We give a complete characterization of the Hermite interpolation problem by periodic splines with Birkhoff knots. As a dual result we derive the characterization of the Birkhoff interpolation by periodic splines with multiple knots.
    Materialart: Digitale Medien
    Standort Signatur Erwartet Verfügbarkeit
    BibTip Andere fanden auch interessant ...
  • 25
    Digitale Medien
    Digitale Medien
    Springer
    Numerische Mathematik 66 (1993), S. 281-294 
    ISSN: 0945-3245
    Schlagwort(e): 41A15 ; 60F15
    Quelle: Springer Online Journal Archives 1860-2000
    Thema: Mathematik
    Notizen: Summary The purpose of this paper is to study the convergence of smoothingD m -splines relative to sets of data perturbed by a random noise. Conditions of almost sure convergence and error estimates are given.
    Materialart: Digitale Medien
    Standort Signatur Erwartet Verfügbarkeit
    BibTip Andere fanden auch interessant ...
  • 26
    Digitale Medien
    Digitale Medien
    Springer
    Constructive approximation 9 (1993), S. 123-166 
    ISSN: 1432-0940
    Schlagwort(e): Primary 41A63 ; 46C99 ; Secondary 41A30 ; 41A15 ; 42B99 ; 46E20 ; Wavelets ; Multiresolution ; Shift-invariant spaces ; Box splines
    Quelle: Springer Online Journal Archives 1860-2000
    Thema: Mathematik
    Notizen: Abstract A new approach for the construction of wavelets and prewavelets onR d from multiresolution is presented. The method uses only properties of shift-invariant spaces and orthogonal projectors fromL 2(R d ) onto these spaces, and requires neither decay nor stability of the scaling function. Furthermore, this approach allows a simple derivation of previous, as well as new, constructions of wavelets, and leads to a complete resolution of questions concerning the nature of the intersection and the union of a scale of spaces to be used in a multiresolution.
    Materialart: Digitale Medien
    Standort Signatur Erwartet Verfügbarkeit
    BibTip Andere fanden auch interessant ...
  • 27
    Digitale Medien
    Digitale Medien
    Springer
    Constructive approximation 9 (1993), S. 191-208 
    ISSN: 1432-0940
    Schlagwort(e): Primary 28C20 ; 41A15 ; 46E30 ; 60J65 ; Secondary 60E15 ; 62J10 ; Wiener measure ; Brownian motion ; Spline approximation ; Orthonormal spline system ; Franklin system ; Orlicz spaces ; Hölder classes ; Covariance ; Correlation ; Gaussian vectors
    Quelle: Springer Online Journal Archives 1860-2000
    Thema: Mathematik
    Notizen: Abstract There are three results proved in this paper. The first one characterizes the Hölder classes in Orlicz spaces by the coefficients of the orthogonal spline expansions of the Franklin type. The second one gives a sharp estimate for the correlation of two random variables obtained as a composition of two Borel functions with the components of a given two-dimensional Gaussian vector. The third one is obtained with the help of the first two and it states that the Wiener measure is concentrated on the Banach space of Hölder functions with exponent 1/2 but in the norm of the Orlicz spaceL M * withM(t)=expt(t 2)−1.
    Materialart: Digitale Medien
    Standort Signatur Erwartet Verfügbarkeit
    BibTip Andere fanden auch interessant ...
  • 28
    Digitale Medien
    Digitale Medien
    Springer
    Constructive approximation 9 (1993), S. 209-236 
    ISSN: 1432-0940
    Schlagwort(e): Primary 41A63 ; 46C99 ; Secondary 41A30 ; 41A15 ; 42B99 ; 46E20 ; Courant interpolating function ; Linear splines ; Hexagonal filter banks ; Biorthogonal wavelets ; multiresolution analysis
    Quelle: Springer Online Journal Archives 1860-2000
    Thema: Mathematik
    Notizen: Abstract We study a class of subband coding schemes allowing perfect reconstruction for a bidimensional signal sampled on the hexagonal grid. From these schemes we construct biorthogonal wavelet bases ofL 2(R 2) which are compactly supported and such that the sets of generating functionsψ 1,ψ 2,ψ 3 for the synthesis and $$\tilde \psi _1 , \tilde \psi _2 , \tilde \psi _3 ,$$ for the analysis, as well as the scaling functions φ and $$\tilde \varphi $$ , are globally invariant by a rotation of 2π/3. We focus on the particular case of linear splines and we discuss how to obtain a higher regularity. We finally present the possibilities of sharp angular frequency resolution provided by these new bases.
    Materialart: Digitale Medien
    Standort Signatur Erwartet Verfügbarkeit
    BibTip Andere fanden auch interessant ...
  • 29
    Digitale Medien
    Digitale Medien
    Springer
    Constructive approximation 9 (1993), S. 263-281 
    ISSN: 1432-0940
    Schlagwort(e): 15A23 ; 15A24 ; 39B42 ; 41A15 ; 42C15 ; 47A62 ; Splines ; Wavelets ; Matrix equations ; Hurwitz matrices ; Toeplitz matrices ; Two-slanted matrices ; Matrix factorization ; Total positivity
    Quelle: Springer Online Journal Archives 1860-2000
    Thema: Mathematik
    Notizen: Abstract Given two function spacesV 0,V 1 with compactly supported basis functionsC i, Fi, i∈Z, respectively, such thatC i can be written as a finite linear combination of theF i's, we study the problem of decomposingV 1 into a direct sum ofV 0 and some subspaceW ofV 1 in such a way thatW is spanned by compactly supported functions and that eachF i can be written as a finite linear combination of the basis functions inV 0 andW. The problem of finding such locally finite decompositions is shown to be equivalent to solving certain matrix equations involving two-slanted matrices. These relations may be reinterpreted in terms of banded matrices possessing banded inverses. Our approach to solving the matrix equations is based on factorization techniques which work under certain conditions on minors. In particular, we apply these results to univariate splines with arbitrary knot sequences.
    Materialart: Digitale Medien
    Standort Signatur Erwartet Verfügbarkeit
    BibTip Andere fanden auch interessant ...
  • 30
    Digitale Medien
    Digitale Medien
    Springer
    Constructive approximation 9 (1993), S. 373-389 
    ISSN: 1432-0940
    Schlagwort(e): 41A05 ; 41A15 ; 41A20 ; 65D05 ; 65D07 ; 65D17 ; 68U07 ; Geometric rational curve interpolation ; Shape preservation ; Convexity ; Parametric splines ; Conics ; Approximation order
    Quelle: Springer Online Journal Archives 1860-2000
    Thema: Mathematik
    Notizen: Abstract Five points in general position inR 2 always lie on a unique conic, and three points plus two tangents also have a unique interpolating conic, the type of which depends on the data. These well-known facts from projective geometry are generalized: an odd number 2n+1≥5 of points inR 2, if they can be interpolated at all by a smooth curve with nonvanishing curvature, will have a uniqueGC 2 interpolant consisting of pieces of conics of varying type. This interpolation process reproduces conics of arbitrary type and preserves strict convexity. Under weak additional assumptions its approximation order is ϑ(h 5), whereh is the maximal distance of adjacent data pointsf(t i ) sampled from a smooth and regular planar curvef with nonvanishing curvature. Two algorithms for the construction of the interpolant are suggested, and some examples are presented.
    Materialart: Digitale Medien
    Standort Signatur Erwartet Verfügbarkeit
    BibTip Andere fanden auch interessant ...
  • 31
    Digitale Medien
    Digitale Medien
    Springer
    Constructive approximation 9 (1993), S. 407-433 
    ISSN: 1432-0940
    Schlagwort(e): 41A15 ; 41A25 ; 41A30 ; Quasi-interpolation ; Thin-plate spline ; Radial basis functions ; Order of convergence
    Quelle: Springer Online Journal Archives 1860-2000
    Thema: Mathematik
    Notizen: Abstract Quasi-interpolation is one method of generating approximations from a space of translates of dilates of a single function ψ. This method has been applied widely to approximation by radial basis functions. However, such analysis has most often been performed in the setting of an infinite uniform grid of centers. In this paper we develop general error bounds for approximation by quasiinterpolation on ann-cube. The quasi-interpolant analyzed involves a finite number, growing ash −n , of translates of dilates of the function ψ, and a bounded number of edge functions. The centers of the translates of dilates of ψ form a uniformly spaced grid within the cube. These error bounds are then applied to approximation by thin-plate splines on a square. The result is an O(ω(f, [-1,1]2,h)) error bound for approximation by thin-plate splines supplemented with eight arctan functions.
    Materialart: Digitale Medien
    Standort Signatur Erwartet Verfügbarkeit
    BibTip Andere fanden auch interessant ...
  • 32
    Digitale Medien
    Digitale Medien
    Springer
    Numerical algorithms 5 (1993), S. 71-81 
    ISSN: 1572-9265
    Schlagwort(e): Approximation order ; multivariate splines ; polynomial splines ; 41A15 ; 65D07
    Quelle: Springer Online Journal Archives 1860-2000
    Thema: Informatik , Mathematik
    Notizen: Abstract We give an algorithm which computes the approximation order of spaces of periodic piece-wise polynomial functions, given the degree, the smoothness and tesselation. The algorithm consists of two steps. The first gives an upper bound and the second a lower bound on the approximation order. In all known cases the two bounds coincide.
    Materialart: Digitale Medien
    Standort Signatur Erwartet Verfügbarkeit
    BibTip Andere fanden auch interessant ...
  • 33
    Digitale Medien
    Digitale Medien
    Springer
    Numerical algorithms 5 (1993), S. 591-601 
    ISSN: 1572-9265
    Schlagwort(e): Quadratic box splines in three variables ; isosurface sampling ; Boltzmann transport equation ; 41A15
    Quelle: Springer Online Journal Archives 1860-2000
    Thema: Informatik , Mathematik
    Notizen: Abstract Numerical approximation has played a valuable supporting role in VLSI device simulation. Examples include (1) tensor product variation diminishing splines for models of transistor charges and currents and (2) continuation to find a safe operating region avoiding avalanche breakdown. More recently, quadratic box splines in three variables have been studied for use in Monte Carlo solution of the Boltzmann transport equation. The bivariate Zwart-Powell element does not directly generalize, but another particular box spline is constructed.
    Materialart: Digitale Medien
    Standort Signatur Erwartet Verfügbarkeit
    BibTip Andere fanden auch interessant ...
  • 34
    Digitale Medien
    Digitale Medien
    Springer
    Numerical algorithms 4 (1993), S. 323-337 
    ISSN: 1572-9265
    Schlagwort(e): Multivariate polynomials ; B-patch ; B-spline ; product ; tensor product ; conversion ; pyramidal algorithm ; de Casteljau algorithm ; blossom ; polar form ; 41A15 ; 65D07
    Quelle: Springer Online Journal Archives 1860-2000
    Thema: Informatik , Mathematik
    Notizen: Abstract Products and tensor products of multivariate polynomials in B-patch form are viewed as linear combinations of higher degree B-patches. Univariate B-spline segments and certain regions of simplex splines are examples of B-patches. A recursive scheme for transforming tensor product B-patch representations into B-patch representations of more variables is presented. The scheme can also be applied for transforming ann-fold product of B-patch expansions into a B-patch expansion of higher degree. Degree raising formulas are obtained as special cases. The scheme calculates the blossom of the (tensor) product surface and generalizes the pyramidal recursive scheme for B-patches.
    Materialart: Digitale Medien
    Standort Signatur Erwartet Verfügbarkeit
    BibTip Andere fanden auch interessant ...
  • 35
    Digitale Medien
    Digitale Medien
    Springer
    Numerical algorithms 5 (1993), S. 121-129 
    ISSN: 1572-9265
    Schlagwort(e): Surface splines ; scattered data interpolation ; incompressible fluid flow ; 41A05 ; 41A15 ; 41A29 ; 41A63 ; 65D05 ; 65D07 ; 65D25 ; 76B99 ; 76D99
    Quelle: Springer Online Journal Archives 1860-2000
    Thema: Informatik , Mathematik
    Notizen: Abstract We show how one may interpolate a vector-valued function in two or three dimensions, whose value is (wholly or partly) known at a sufficient (but not large) number of points disposed in almost any configuration, under the condition that the interpolating function has zero divergence. The technique is based on the theory of thin-plate splines. One may use a similar scheme in the case where the data consist of flux integrals (or other linear functionals) of the unknown function.
    Materialart: Digitale Medien
    Standort Signatur Erwartet Verfügbarkeit
    BibTip Andere fanden auch interessant ...
  • 36
    Digitale Medien
    Digitale Medien
    Springer
    Numerical algorithms 5 (1993), S. 229-245 
    ISSN: 1572-9265
    Schlagwort(e): Stable decompositions ; periodic multiresolution analysis ; pseudodifferential equations ; preconditioning ; decompositions of refinable spaces ; matrix equations ; 41A65 ; 41A15 ; 15A12 ; 15A24 ; 65N40 ; 47G05
    Quelle: Springer Online Journal Archives 1860-2000
    Thema: Informatik , Mathematik
    Notizen: Abstract This paper presents a brief survey of several recent applications of multilevel techniques, in particular, in connection with the solution of periodic pseudodifferential equations. It is pointed out that these applications naturally lead to certain decompositions of refinable spaces which are induced by a class of linear projectors. Then recent results on the construction of such nonorthogonal wavelets are reviewed and extended to the particular needs of the present context.
    Materialart: Digitale Medien
    Standort Signatur Erwartet Verfügbarkeit
    BibTip Andere fanden auch interessant ...
  • 37
    Digitale Medien
    Digitale Medien
    Springer
    Advances in computational mathematics 1 (1993), S. 109-126 
    ISSN: 1572-9044
    Schlagwort(e): Hilbert space ; commuting unitary operators ; Riesz basis ; wandering subspaces ; multiresolution approximation ; duality principle ; box splines ; 41A15 ; 42C15 ; 47B37
    Quelle: Springer Online Journal Archives 1860-2000
    Thema: Mathematik
    Notizen: Abstract Let (U=U 1, ...,U d ) be an orderedd-tuple of distinct, pairwise commuting, unitary operators on a complex Hilbert space ℋ, and letX:={x 1, ...,x r } ⊂ ℋ such that $$U^{\mathbb{Z}^d } X: = \{ U_1^{n_1 } \ldots U_d^{n_d } x_j :(n_1 , \ldots ,n_d ) \in \mathbb{Z}^d ,j = 1, \ldots ,r\} $$ is a Riesz basis of the closed linear spanV 0 of $$U^{\mathbb{Z}^d } X$$ . Suppose there is unitary operatorD on ℋ such thatV 0 ⊂D V 0 =:V 1 andU n D=DU An for alln ∈ ℤ d , whereA is ad ×d matrix with integer entries and Δ := det(A) ≠ 0. Then there is a subset Λ inV 1, withr(Δ − 1) vectors, such that $$U^{\mathbb{Z}^d } (\Gamma )$$ is a Riesz basis ofW 0, the orthogonal complement ofV 0 inV 1. The resulting multiscale and decomposition relations can be expressed in a Fourier representation by one single equation, in terms of which the duality principle follows easily. These results are a consequence of an extension, to a set of commuting unitary operators, of Robertson's Theorems on wandering subspace for a single unitary operator [24]. Conditions are given in order that $$U^{\mathbb{Z}^d } (\Gamma )$$ is a Riesz basis ofW 0. They are used in the construction of a class of linear spline wavelets on a four-direction mesh.
    Materialart: Digitale Medien
    Standort Signatur Erwartet Verfügbarkeit
    BibTip Andere fanden auch interessant ...
  • 38
    Digitale Medien
    Digitale Medien
    Springer
    Numerische Mathematik 47 (1985), S. 191-215 
    ISSN: 0945-3245
    Schlagwort(e): AMS(MOS): 30B70 ; 40A15 ; 41A15 ; CR: G1.2
    Quelle: Springer Online Journal Archives 1860-2000
    Thema: Mathematik
    Notizen: Summary For continued fractionsK(a n /1) the concept of limit region is discussed, and its use for obtaining modified truncation error estimates is illustrated on examples. A certain strategy for numerical computation of limit regions is presented and illustrated on examples.
    Materialart: Digitale Medien
    Standort Signatur Erwartet Verfügbarkeit
    BibTip Andere fanden auch interessant ...
  • 39
    Digitale Medien
    Digitale Medien
    Springer
    Constructive approximation 1 (1985), S. 137-154 
    ISSN: 1432-0940
    Schlagwort(e): 41A15 ; 41A5 ; 41A65 ; Perfect splines ; Monosplines ; Extended totally positive kernels ; Monotone norms ; Optimal quadrature formulas ; Optimal interpolation ; N-widths ; Optimal spaces
    Quelle: Springer Online Journal Archives 1860-2000
    Thema: Mathematik
    Notizen: Abstract Generalized monosplines of least norm are shown to exist and to determine optimal approximation processes such as numerical integration, interpolation and best approximating spaces. This extends various classical results related to monosplines and perfect splines, which are particular cases of generalized monosplines. The analysis here also provides for a unified treatment of the two classical classes of monosplines and perfect splines of least norm, and of their extremal properties.
    Materialart: Digitale Medien
    Standort Signatur Erwartet Verfügbarkeit
    BibTip Andere fanden auch interessant ...
  • 40
    Digitale Medien
    Digitale Medien
    Springer
    Constructive approximation 1 (1985), S. 305-322 
    ISSN: 1432-0940
    Schlagwort(e): 41A15 ; Box spline ; Convergence rate ; Subdivision algorithms ; Control net
    Quelle: Springer Online Journal Archives 1860-2000
    Thema: Mathematik
    Notizen: Abstract Dahmen and Micchelli [8] have shown that in general the coefficients of the refined control nets of a box spline surface converge to the surface at (at least) the rate of the refinement. The purpose of this article is to show that under mild additional assumptions the convergence rate is even quadratic. Although this rate is in general best possible, we point out under what circumstances even higher rates are obtained (locally).
    Materialart: Digitale Medien
    Standort Signatur Erwartet Verfügbarkeit
    BibTip Andere fanden auch interessant ...
  • 41
    Digitale Medien
    Digitale Medien
    Springer
    Constructive approximation 1 (1985), S. 15-62 
    ISSN: 1432-0940
    Schlagwort(e): 41A46 ; 41A15 ; n-Widths ; Total positivity ; Eigenvalues ; Eigenfunctions ; Implicit function theorem
    Quelle: Springer Online Journal Archives 1860-2000
    Thema: Mathematik
    Notizen: Abstract LetW p (r) ={f:f∈C r−1[0, 1],f (r−1) abs.cont., ∥f (r)∥ p 〈∞}, and setB p (r) ={f:f∈W p (r) ,∥f (r)∥ p ≤1}. We find the exact Kolmogorov, Gel'fand, linear, and Bernsteinn-widths ofB p (r) inL p for allp∈(1, ∞). For the Kolmogorovn-width we show that forn≥r there exists an optimal subspace of splines of degreer−1 withn−r fixed simple knots depending onp.
    Materialart: Digitale Medien
    Standort Signatur Erwartet Verfügbarkeit
    BibTip Andere fanden auch interessant ...
  • 42
    Digitale Medien
    Digitale Medien
    Springer
    Constructive approximation 1 (1985), S. 155-173 
    ISSN: 1432-0940
    Schlagwort(e): 41A15 ; 65D07 ; Chebyshevian B-splines ; generalized divided differences
    Quelle: Springer Online Journal Archives 1860-2000
    Thema: Mathematik
    Notizen: Abstract The fundamental recurrence relation for polynomialB-splines is generalized to ChebyshevianB-splines.
    Materialart: Digitale Medien
    Standort Signatur Erwartet Verfügbarkeit
    BibTip Andere fanden auch interessant ...
  • 43
    Digitale Medien
    Digitale Medien
    Springer
    Constructive approximation 1 (1985), S. 183-193 
    ISSN: 1432-0940
    Schlagwort(e): 41A05 ; 41A15 ; 41A63 ; Bivariate ; Box-splines ; Interpolation ; Convergence ; Exponential type ; Whittaker operator
    Quelle: Springer Online Journal Archives 1860-2000
    Thema: Mathematik
    Notizen: Abstract We give necessary and sufficient conditions for the convergence of cardinal interpolation with bivariate box splines as the degree tends to infinity.
    Materialart: Digitale Medien
    Standort Signatur Erwartet Verfügbarkeit
    BibTip Andere fanden auch interessant ...
  • 44
    Digitale Medien
    Digitale Medien
    Springer
    Journal of optimization theory and applications 45 (1985), S. 33-39 
    ISSN: 1573-2878
    Schlagwort(e): Linear programming ; simplex method ; unrestricted variables ; simplex multipliers ; LU-factorization
    Quelle: Springer Online Journal Archives 1860-2000
    Thema: Mathematik
    Notizen: Abstract Suppose that the simplex method is applied to a linear programming problem havingm equality constraints andr unrestricted variables. We give a method of performing the steps of the simplex method which reduces the arithmetic operation count byrm at each iteration. This savings in operations is achieved, since the method does not update the rows of the basis inverse associated with the unrestricted variables. Similar computational savings are achieved when the method is applied to the updating of anLU-factorization of the basis matrix.
    Materialart: Digitale Medien
    Standort Signatur Erwartet Verfügbarkeit
    BibTip Andere fanden auch interessant ...
  • 45
    Digitale Medien
    Digitale Medien
    Springer
    Mathematical programming 13 (1977), S. 1-13 
    ISSN: 1436-4646
    Schlagwort(e): Assignment problems ; Linear programming ; Manpower planning ; Networks ; Personnel assignment ; Transportation problems
    Quelle: Springer Online Journal Archives 1860-2000
    Thema: Informatik , Mathematik
    Notizen: Abstract The purpose of this paper is to present a new primal extreme point algorithm for solving assignment problems which both circumvents and exploits degeneracy. The algorithm is based on the observation that the degeneracy difficulties of the simplex method result from the unnecessary inspection of alternative basis representations of the extreme points. This paper characterizes a subsetQ of all bases that are capable of leading to an optimal solution to the problem if one exists. Using this characterization, an extreme point algorithm is developed which considers only those bases inQ. Computational results disclose that the new algorithm is substantially more efficient than previously developed primal and primal-dual extreme point (“simplex”) methods for assignment problems.
    Materialart: Digitale Medien
    Standort Signatur Erwartet Verfügbarkeit
    BibTip Andere fanden auch interessant ...
  • 46
    Digitale Medien
    Digitale Medien
    Springer
    Mathematical programming 13 (1977), S. 272-279 
    ISSN: 1436-4646
    Schlagwort(e): Linear programming ; Basis matrix ; LU factorization ; Pricing
    Quelle: Springer Online Journal Archives 1860-2000
    Thema: Informatik , Mathematik
    Notizen: Abstract Many implementations of the simplex method require the row of the inverse of the basis matrixB corresponding to the pivot row at each iteration for updating either a pricing vector or the nonbasic reduced costs. In this note we show that if the Bartels—Golub algorithm [1, 2] or one of its variants is used to update theLU factorization ofB, then less computing is needed if one works with the factors of the updatedB than with those ofB. These results are discussed as they apply to the column selection algorithms recently proposed by Goldfarb and Reid [4, 5] and Harris [6].
    Materialart: Digitale Medien
    Standort Signatur Erwartet Verfügbarkeit
    BibTip Andere fanden auch interessant ...
  • 47
    ISSN: 1436-4646
    Schlagwort(e): Linear programming ; Integer programming ; Mixed integer programming ; Large scale programming ; Branch and bound ; Triangular factorization ; etc. Sparse matrix methods ; Degeneracy ; Numerical stability ; Computational results ; Mathematical programming language
    Quelle: Springer Online Journal Archives 1860-2000
    Thema: Informatik , Mathematik
    Notizen: Abstract First, this paper presents the results of experiments with algorithmic techniques for efficiently solving medium and large scale linear and mixed integer programming problems. The techniques presented here are either original or recent. The solution of a great number of problems has shown that efficient problem solving requires automatic adaptation of algorithmic techniques upon problem characteristics. We show when a given technique should be used for a particular problem. The last part of this paper describes an attempt to provide a powerful mathematical programming language, allowing an easy programming of specific studies on medium-size models such as the recursive use of LP or the build-up of algorithms based on the simplex method. All these features have been implemented in the IBM Mathematical Programming System, MPSX/370, and its feature MIP/370. Extensive numerical results and comparisons on real-life problems are provided and commented upon.
    Materialart: Digitale Medien
    Standort Signatur Erwartet Verfügbarkeit
    BibTip Andere fanden auch interessant ...
Schließen ⊗
Diese Webseite nutzt Cookies und das Analyse-Tool Matomo. Weitere Informationen finden Sie hier...