Library

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
  • 11
    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
    Library Location Call Number Volume/Issue/Year Availability
    BibTip Others were also interested in ...
    Paper (German National Licenses)
    Fulltext
  • 12
    Electronic Resource
    Electronic Resource
    A primal simplex algorithm that solves the maximum flow problem in at mostnm pivots and O(n 2 m) time (1990)
    Springer
    Mathematical programming 47 (1990), S. 353-365 
    Details
    ISSN: 1436-4646
    Keywords: Simplex method ; maximum flow ; strongly polynomial ; network flow
    Source: Springer Online Journal Archives 1860-2000
    Topics: Computer Science , Mathematics
    Notes: Abstract We propose a primal network simplex algorithm for solving the maximum flow problem which chooses as the arc to enter the basis one that isclosest to the source node from amongst all possible candidates. We prove that this algorithm requires at mostnm pivots to solve a problem withn nodes andm arcs, and give implementations of it which run in O(n 2 m) time. Our algorithm is, as far as we know, the first strongly polynomial primal simplex algorithm for solving the maximum flow problem.
    Type of Medium: Electronic Resource
    URL: http://dx.doi.org/10.1007/BF01580869
    Library Location Call Number Volume/Issue/Year Availability
    BibTip Others were also interested in ...
    Paper (German National Licenses)
    Fulltext
  • 13
    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
    Library Location Call Number Volume/Issue/Year Availability
    BibTip Others were also interested in ...
    Paper (German National Licenses)
    Fulltext
  • 14
    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
    Library Location Call Number Volume/Issue/Year Availability
    BibTip Others were also interested in ...
    Paper (German National Licenses)
    Fulltext
  • 15
    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
    Library Location Call Number Volume/Issue/Year Availability
    BibTip Others were also interested in ...
    Paper (German National Licenses)
    Fulltext
  • 16
    Book
    Book
    ¬An¬ O(nm)-time network simplex algorithm for the shortest path problem
    Details
    Title: ¬An¬ O(nm)-time network simplex algorithm for the shortest path problem
    Author: Goldfarb, Donald
    Contributer: Jin, Zhiying
    Type of Medium: Book
    Library Location Call Number Volume/Issue/Year Availability
    BibTip Others were also interested in ...
    ZIB Catalog
    Zuse Institute Berlin get availability status
Close ⊗
This website uses cookies and the analysis tool Matomo. More information can be found here...