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
  • 1
    Electronic Resource
    Electronic Resource
    Polynomial-time primal simplex algorithms for the minimum cost network flow problem (1992)
    Springer
    Algorithmica 8 (1992), S. 145-160 
    Details
    ISSN: 1432-0541
    Keywords: Simplex method ; Minimum cost network flows ; Strongly polynomial ; Maximum flow ; Minimum mean augmenting cycle ; Cost scaling ; Polytope diameter
    Source: Springer Online Journal Archives 1860-2000
    Topics: Computer Science , Mathematics
    Notes: Abstract We present two variants of the primal network simplex algorithm which solve the minimum cost network flow problem in at mostO(n 2 logn) pivots. Here we define the network simplex method as a method which proceeds from basis tree to adjacent basis tree regardless of the change in objective function value; i.e., the objective function is allowed to increase on some iterations. The first method is an extension of theminimum mean augmenting cycle-canceling method of Goldberg and Tarjan. The second method is a combination of a cost-scaling technique and a primal network simplex method for the maximum flow problem. We also show that the diameter of the primal network flow polytope is at mostn 2 m.
    Type of Medium: Electronic Resource
    URL: http://dx.doi.org/10.1007/BF01758840
    Location Call Number Expected Availability
    BibTip Others were also interested in ...
    Paper (German National Licenses)
    Fulltext
  • 2
    Electronic Resource
    Electronic Resource
    Conjugate Gradient Method for Nonlinear Programming Problems with Linear Constraints (1968)
    s.l. : American Chemical Society
    Industrial and engineering chemistry 7 (1968), S. 142-151 
    Details
    Source: ACS Legacy Archives
    Topics: Chemistry and Pharmacology , Process Engineering, Biotechnology, Nutrition Technology
    Type of Medium: Electronic Resource
    URL: http://dx.doi.org/10.1021/i160025a024
    Location Call Number Expected Availability
    BibTip Others were also interested in ...
    Paper (German National Licenses)
    Fulltext
  • 3
    Electronic Resource
    Electronic Resource
    Curvilinear path steplength algorithms for minimization which use directions of negative curvature (1980)
    Springer
    Mathematical programming 18 (1980), S. 31-40 
    Details
    ISSN: 1436-4646
    Keywords: Step-size Procedures ; Line Search ; Gradient Methods ; Unconstrained Minimization ; Negative Curvature
    Source: Springer Online Journal Archives 1860-2000
    Topics: Computer Science , Mathematics
    Notes: Abstract The Armijo and Goldstein step-size rules are modified to allow steps along a curvilinear path of the formx(α) + x + αs + α2 d, wherex is the current estimate of the minimum,s is a descent direction andd is a nonascent direction of negative curvature. By using directions of negative curvature when they exist, we are able to prove, under fairly mild assumptions, that the sequences of iterates produced by these algorithms converge to stationary points at which the Hessian matrix of the objective function is positive semidefinite.
    Type of Medium: Electronic Resource
    URL: http://dx.doi.org/10.1007/BF01588294
    Location Call Number Expected Availability
    BibTip Others were also interested in ...
    Paper (German National Licenses)
    Fulltext
  • 4
    Electronic Resource
    Electronic Resource
    A relaxed version of Karmarkar's method (1988)
    Springer
    Mathematical programming 40 (1988), S. 289-315 
    Details
    ISSN: 1436-4646
    Keywords: Linear programming ; Karmarkar's method ; inexact projections
    Source: Springer Online Journal Archives 1860-2000
    Topics: Computer Science , Mathematics
    Notes: Abstract A relaxed version of Karmarkar's method is developed. This method is proved to have the same polynomial time complexity as Karmarkar's method and its efficient implementation using inexact projections is discussed. Computational results obtained using a preliminary implementation of the method are presented which indicate that the method is practicable.
    Type of Medium: Electronic Resource
    URL: http://dx.doi.org/10.1007/BF01580737
    Location Call Number Expected Availability
    BibTip Others were also interested in ...
    Paper (German National Licenses)
    Fulltext
  • 5
    Electronic Resource
    Electronic Resource
    Relaxed variants of Karmarkar's algorithm for linear programs with unknown optimal objective value (1988)
    Springer
    Mathematical programming 40 (1988), S. 183-195 
    Details
    ISSN: 1436-4646
    Keywords: Karmarkar's method ; linear programming ; inexact projections
    Source: Springer Online Journal Archives 1860-2000
    Topics: Computer Science , Mathematics
    Notes: Abstract Variants of Karmarkar's algorithm are given for solving linear programs with unknown optimal objective valuez *. These new methods combine the approach of Goldfarb and Mehrotra for relaxing the requirement that certain projections be computed exactly with the approach of Todd and Burrell for generating an improving sequence of lower bounds forz * using dual feasible solutions. These methods retain the polynomial-time complexity of Karmarkar's algorithm.
    Type of Medium: Electronic Resource
    URL: http://dx.doi.org/10.1007/BF01580729
    Location Call Number Expected Availability
    BibTip Others were also interested in ...
    Paper (German National Licenses)
    Fulltext
  • 6
    Electronic Resource
    Electronic Resource
    An O(n 3 L) primal—dual potential reduction algorithm for solving convex quadratic programs (1993)
    Springer
    Mathematical programming 61 (1993), S. 161-170 
    Details
    ISSN: 1436-4646
    Keywords: Interior point method ; Karmarkar's method ; primal—dual potential function ; convex quadratic programming ; rank-one update
    Source: Springer Online Journal Archives 1860-2000
    Topics: Computer Science , Mathematics
    Notes: Abstract In this paper we combine partial updating and an adaptation of Anstreicher's safeguarded linesearch of the primal—dual potential function with Kojima, Mizuno and Yoshise's potential reduction algorithm for the linear complementarity problem to obtain an O(n 3 L) algorithm for convex quadratic programming. Our modified algorithm is a long step method that requires at most O( $$\sqrt n$$ L) steps.
    Type of Medium: Electronic Resource
    URL: http://dx.doi.org/10.1007/BF01582145
    Location Call Number Expected Availability
    BibTip Others were also interested in ...
    Paper (German National Licenses)
    Fulltext
  • 7
    Electronic Resource
    Electronic Resource
    A primal projective interior point method for linear programming (1991)
    Springer
    Mathematical programming 51 (1991), S. 17-43 
    Details
    ISSN: 1436-4646
    Keywords: Interior point methods ; linear programming ; fractional linear programming ; projective algorithm ; Karmarkar's algorithm ; polynomial-type algorithm
    Source: Springer Online Journal Archives 1860-2000
    Topics: Computer Science , Mathematics
    Notes: Abstract We present a new projective interior point method for linear programming with unknown optimal value. This algorithm requires only that an interior feasible point be provided. It generates a strictly decreasing sequence of objective values and within polynomial time, either determines an optimal solution, or proves that the problem is unbounded. We also analyze the asymptotic convergence rate of our method and discuss its relationship to other polynomial time projective interior point methods and the affine scaling method.
    Type of Medium: Electronic Resource
    URL: http://dx.doi.org/10.1007/BF01586924
    Location Call Number Expected Availability
    BibTip Others were also interested in ...
    Paper (German National Licenses)
    Fulltext
  • 8
    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
  • 9
    Electronic Resource
    Electronic Resource
    Matrix factorizations in optimization of nonlinear functions subject to linear constraints (1976)
    Springer
    Mathematical programming 10 (1976), S. 1-31 
    Details
    ISSN: 1436-4646
    Source: Springer Online Journal Archives 1860-2000
    Topics: Computer Science , Mathematics
    Notes: Abstract Several ways of implementing methods for solving nonlinear optimization problems involving linear inequality and equality constraints using numerically stable matrix factorizations are described. The methods considered all follow an active constraint set approach and include quadratic programming, variable metric, and modified Newton methods.
    Type of Medium: Electronic Resource
    URL: http://dx.doi.org/10.1007/BF01580651
    Location Call Number Expected Availability
    BibTip Others were also interested in ...
    Paper (German National Licenses)
    Fulltext
  • 10
    Electronic Resource
    Electronic Resource
    Modifications and implementation of the ellipsoid algorithm for linear programming (1982)
    Springer
    Mathematical programming 23 (1982), S. 1-19 
    Details
    ISSN: 1436-4646
    Keywords: Ellipsoid Algorithm ; Linear Programming ; Polynomial Boundedness ; Khachian's Method ; Linear Inequalities
    Source: Springer Online Journal Archives 1860-2000
    Topics: Computer Science , Mathematics
    Notes: Abstract We give some modifications of the ellipsoid algorithm for linear programming and describe a numerically stable implementation. We are concerned with practical problems where user-supplied bounds can usually be provided. Our implementation allows constraint dropping and updates bounds on the optimal value, and should be able to terminate with an indication of infeasibility or with a provably good feasible solution in a moderate number of iterations.
    Type of Medium: Electronic Resource
    URL: http://dx.doi.org/10.1007/BF01583776
    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...