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
    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
  • 2
    Electronic Resource
    Electronic Resource
    An algorithm for linear programming which requires O(((m+n)n 2+(m+n)1.5 n)L) arithmetic operations (1990)
    Springer
    Mathematical programming 47 (1990), S. 175-201 
    Details
    ISSN: 1436-4646
    Keywords: Optimization ; linear programming ; complexity ; polynomial time algorithms
    Source: Springer Online Journal Archives 1860-2000
    Topics: Computer Science , Mathematics
    Notes: Abstract We present an algorithm for linear programming which requires O(((m+n)n 2+(m+n)1.5 n)L) arithmetic operations wherem is the number of constraints, andn is the number of variables. Each operation is performed to a precision of O(L) bits.L is bounded by the number of bits in the input. The worst-case running time of the algorithm is better than that of Karmarkar's algorithm by a factor of $$\sqrt {m + n} $$ .
    Type of Medium: Electronic Resource
    URL: http://dx.doi.org/10.1007/BF01580859
    Location Call Number Expected Availability
    BibTip Others were also interested in ...
    Paper (German National Licenses)
    Fulltext
  • 3
    Electronic Resource
    Electronic Resource
    A scaling technique for finding the weighted analytic center of a polytope (1992)
    Springer
    Mathematical programming 57 (1992), S. 163-192 
    Details
    ISSN: 1436-4646
    Source: Springer Online Journal Archives 1860-2000
    Topics: Computer Science , Mathematics
    Notes: Abstract Let a bounded full dimensional polytope be defined by the systemAx ⩾b whereA is anm × n matrix. Leta i denote theith row of the matrixA, and define theweighted analytic center of the polytope to be the point that minimizes the strictly convex barrier function −∑ i=1 m w i ln(a i T x −b i ). The proper selection of weightsw i can make any desired point in the interior of the polytope become the weighted analytic center. As a result, the weighted analytic center has applications in both linear and general convex programming. For simplicity we assume that the weights are positive integers. If some of thew i 's are much larger than others, then Newton's method for minimizing the resulting barrier function is very unstable and can be very slow. Previous methods for finding the weighted analytic center relied upon a rather direct application of Newton's method potentially resulting in very slow global convergence. We present a method for finding the weighted analytic center that is based on the scaling technique of Edmonds and Karp and is an enhancement of Newton's method. The scaling algorithm runs in $$O(\sqrt m \log W)$$ iterations, wherem is the number of constraints defining the polytope andW is the largest weight given on any constraint. Each iteration involves taking a step in the Newton direction and its complexity is dominated by the time needed to solve a system of linear equations.
    Type of Medium: Electronic Resource
    URL: http://dx.doi.org/10.1007/BF01581079
    Location Call Number Expected Availability
    BibTip Others were also interested in ...
    Paper (German National Licenses)
    Fulltext
  • 4
    Electronic Resource
    Electronic Resource
    Approximate minimum weight matching on points ink-dimensional space (1989)
    Springer
    Algorithmica 4 (1989), S. 569-583 
    Details
    ISSN: 1432-0541
    Keywords: Geometric matching ; Approximation algorithms
    Source: Springer Online Journal Archives 1860-2000
    Topics: Computer Science , Mathematics
    Notes: Abstract We study the problem of finding a minimum weight complete matching in the complete graph on a set V ofn points ink-dimensional space. The points are the vertices of the graph and the weight of an edge between any two points is the distance between the points under someL q,-metric. We give anO((2c q )1.5k ɛ−1.5k (α(n, n))0.5 n 1.5(logn)2.5) algorithm for finding an almost minimum weight complete matching in such a graph, wherec q =6k 1/q for theL q -metric, α is the inverse Ackermann function, and ɛ ≤ 1. The weight of the complete matching obtained by our algorithm is guaranteed to be at most (1 + ɛ) times the weight of a minimum weight complete matching.
    Type of Medium: Electronic Resource
    URL: http://dx.doi.org/10.1007/BF01553909
    Location Call Number Expected Availability
    BibTip Others were also interested in ...
    Paper (German National Licenses)
    Fulltext
  • 5
    Electronic Resource
    Electronic Resource
    AnO(n logn) algorithm for the all-nearest-neighbors Problem (1989)
    Springer
    Discrete & computational geometry 4 (1989), S. 101-115 
    Details
    ISSN: 1432-0444
    Source: Springer Online Journal Archives 1860-2000
    Topics: Computer Science , Mathematics
    Notes: Abstract Given a setV ofn points ink-dimensional space, and anL q -metric (Minkowski metric), the all-nearest-neighbors problem is defined as follows: for each pointp inV, find all those points inV−{p} that are closest top under the distance metricL q . We give anO(n logn) algorithm for the all-nearest-neighbors problem, for fixed dimensionk and fixed metricL q . Since there is an Θ(n logn) lower bound, in the algebraic decision-tree model of computation, on the time complexity of any algorithm that solves the all-nearest-neighbors problem (fork=1), the running time of our algorithm is optimal up to a constant factor.
    Type of Medium: Electronic Resource
    URL: http://dx.doi.org/10.1007/BF02187718
    Location Call Number Expected Availability
    BibTip Others were also interested in ...
    Paper (German National Licenses)
    Fulltext
  • 6
    facet.materialart.
    Unknown
    Approximate minimum weight matching on points ink-dimensional space (1989)
    Springer
    Details
    Publication Date: 1989-06-01
    Print ISSN: 0178-4617
    Electronic ISSN: 1432-0541
    Topics: Computer Science , Mathematics
    Published by Springer
    Location Call Number Expected Availability
    BibTip Others were also interested in ...
    PAPER CURRENT
Close ⊗
This website uses cookies and the analysis tool Matomo. More information can be found here...