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
  • 1
    Electronic Resource
    Electronic Resource
    Algorithms for a Class of Isotonic Regression Problems (1999)
    Springer
    Algorithmica 23 (1999), S. 211-222 
    Details
    ISSN: 1432-0541
    Keywords: Key words. Isotonic regression, Binomial heap, Linear time algorithms.
    Source: Springer Online Journal Archives 1860-2000
    Topics: Computer Science , Mathematics
    Notes: Abstract. The isotonic regression problem has applications in statistics, operations research, and image processing. In this paper a general framework for the isotonic regression algorithm is proposed. Under this framework, we discuss the isotonic regression problem in the case where the directed graph specifying the order restriction is a directed tree with n vertices. A new algorithm is presented for this case, which can be regarded as a generalization of the PAV algorithm of Ayer et al. Using a simple tree structure such as the binomial heap, the algorithm can be implemented in O(n log n) time, improving the previously best known O(n 2 ) time algorithm. We also present linear time algorithms for special cases where the directed graph is a path or a star.
    Type of Medium: Electronic Resource
    URL: http://dx.doi.org/10.1007/PL00009258
    Library Location Call Number Volume/Issue/Year Availability
    BibTip Others were also interested in ...
    Paper (German National Licenses)
    Fulltext
  • 2
    Electronic Resource
    Electronic Resource
    Global minimization of indefinite quadratic problems (1987)
    Springer
    Computing 39 (1987), S. 281-291 
    Details
    ISSN: 1436-5057
    Keywords: 65K05 ; 90C30
    Source: Springer Online Journal Archives 1860-2000
    Topics: Computer Science
    Description / Table of Contents: Zusammenfassung Wir schlagen einen neuen „branch and bound” Algorithmus vor, um globale Optima indefiniter quadratischer Probleme über einem Polytop zu berechnen. Unser Algorithmus benutzt separable Programmierung und Techniken der konkaven Optimierung zur näherungsweisen Berechnung von Lösungen. Ferner wird eine Fehleranalyse durchgeführt und es wird über vorläufige experimentelle Ergebnisse (auf einer Cray 1 S) berichtet.
    Notes: Abstract A branch and bound algorithm is proposed for finding the global optimum of large-scale indefinite quadratic problems over a polytope. The algorithm uses separable programming and techniques from concave optimization to obtain approximate solutions. Results on error bounding are given and preliminary computational results using the Cray 1S supercomputer as reported.
    Type of Medium: Electronic Resource
    URL: http://dx.doi.org/10.1007/BF02239972
    Library Location Call Number Volume/Issue/Year Availability
    BibTip Others were also interested in ...
    Paper (German National Licenses)
    Fulltext
  • 3
    Electronic Resource
    Electronic Resource
    Computational aspects of a branch and bound algorithm for quadratic zero-one programming (1990)
    Springer
    Computing 45 (1990), S. 131-144 
    Details
    ISSN: 1436-5057
    Keywords: 65K05 ; 90C30 ; Quadratic 0–1 programming ; branch and bound ; computation ; test problems
    Source: Springer Online Journal Archives 1860-2000
    Topics: Computer Science
    Description / Table of Contents: Zusammenfassung In dieser Arbeit beschreiben wir rechnerische Erfahrungen bei der Lösung von unbeschränkten quadratischen Null-Eins-Problemen mit einem “Branch and Bound”-Algorithmus. Der Algorithmus erlaubt dynamische Vorbereitungs-Techniken zur Erzwingung ausgewählter Variablen und Heuristiken zur Wahl von guten Startpunkten. Resultate von Berechnungen und Vergleiche mit früheren Arbeiten mit mehreren hundert Testproblemen mit Dimensionen bis 200 zeigen die Effizienz unseres Algorithmus.
    Notes: Abstract In this paper we describe computational experience in solving unconstrained quadratic zero-one problems using a branch and bound algorithm. The algorithm incorporates dynamic preprocessing techniques for forcing variables and heuristics to obtain good starting points. Computational results and comparisons with previous studies on several hundred test problems with dimensions up to 200 demonstrate the efficiency of our algorithm.
    Type of Medium: Electronic Resource
    URL: http://dx.doi.org/10.1007/BF02247879
    Library Location Call Number Volume/Issue/Year Availability
    BibTip Others were also interested in ...
    Paper (German National Licenses)
    Fulltext
  • 4
    Electronic Resource
    Electronic Resource
    Enumerative techniques for solving some nonconvex global optimization problems (1988)
    Springer
    OR spectrum 10 (1988), S. 29-35 
    Details
    ISSN: 1436-6304
    Source: Springer Online Journal Archives 1860-2000
    Topics: Mathematics , Economics
    Description / Table of Contents: Zusammenfassung Wir geben einen Überblick über verschiedene Methoden für nicht konvexe Minimisierungsaufgaben. Insbesondere diskutieren wir Aufzählungsmethoden für Extrempunkte. Wir betrachten konkave, quadratisch indefinite Probleme ebenso wie Probleme spezieller Struktur: konkave Netzwerk-Fluß-Probleme und lineare Komplementaritäts-Probleme. Wir schlagen neue Methoden vor, um lineare untere Schranken für Aufzählungstechnicken zu erhalten.
    Notes: Summary We give an overview on different methods for solving nonconvex minimization problems using techniques of enumeration of extreme points. The problems considered include concave, indefinite quadratic, and special structured problems such as the concave cost network flow problem and linear complementarity. For methods that enumerate the extreme points according to the ascending order of the value of a linear underestimating function we propose new techniques for obtaining such underestimators.
    Type of Medium: Electronic Resource
    URL: http://dx.doi.org/10.1007/BF01720032
    Library Location Call Number Volume/Issue/Year Availability
    BibTip Others were also interested in ...
    Paper (German National Licenses)
    Fulltext
  • 5
    Electronic Resource
    Electronic Resource
    Minimum concave-cost network flow problems: Applications, complexity, and algorithms (1990)
    Springer
    Annals of operations research 25 (1990), S. 75-99 
    Details
    ISSN: 1572-9338
    Keywords: Concave-cost network flow ; global optimization ; complexity theory ; NP-hard transportation problems
    Source: Springer Online Journal Archives 1860-2000
    Topics: Mathematics , Economics
    Notes: Abstract We discuss a wide range of results for minimum concave-cost network flow problems, including related applications, complexity issues, and solution techniques. Applications from production and inventory planning, and transportation and communication network design are discussed. New complexity results are proved which show that this problem is NP-hard for cases with cost functions other than fixed charge. An overview of solution techniques for this problem is presented, with some new results given regarding the implementation of a particular branch-and-bound approach.
    Type of Medium: Electronic Resource
    URL: http://dx.doi.org/10.1007/BF02283688
    Library Location Call Number Volume/Issue/Year Availability
    BibTip Others were also interested in ...
    Paper (German National Licenses)
    Fulltext
  • 6
    Electronic Resource
    Electronic Resource
    Lower bounds for the quadratic assignment problem (1994)
    Springer
    Annals of operations research 50 (1994), S. 387-410 
    Details
    ISSN: 1572-9338
    Keywords: Quadratic assignment problem ; branch-and-bound ; lower bound ; combinatorial optimization ; AMS(MOS) 68Q25 ; 90B80 ; 90C27
    Source: Springer Online Journal Archives 1860-2000
    Topics: Mathematics , Economics
    Notes: Abstract We investigate the classical Gilmore-Lawler lower bound for the quadratic assignment problem. We provide evidence of the difficulty of improving the Gilmore-Lawler bound and develop new bounds by means of optimal reduction schemes. Computational results are reported indicating that the new lower bounds have advantages over previous bounds and can be used in a branch-and-bound type algorithm for the quadratic assignment problem.
    Type of Medium: Electronic Resource
    URL: http://dx.doi.org/10.1007/BF02085649
    Library Location Call Number Volume/Issue/Year Availability
    BibTip Others were also interested in ...
    Paper (German National Licenses)
    Fulltext
  • 7
    Electronic Resource
    Electronic Resource
    Parallel branch and bound algorithms for quadratic zero–one programs on the hypercube architecture (1990)
    Springer
    Annals of operations research 22 (1990), S. 271-292 
    Details
    ISSN: 1572-9338
    Source: Springer Online Journal Archives 1860-2000
    Topics: Mathematics , Economics
    Notes: Abstract We present a parallel branch and bound algorithm for unconstrained quadratic zero-one programs on the hypercube architecture. Subproblems parallelize well without the need of a shared data structure to store expanded nodes of the search tree. Load balancing is achieved by demand splitting of neighboring subproblems. Computational results on a variety of large-scale problems are reported on an iPSC/1 32-node hypercube and an iPSC/2 16-node hypercube.
    Type of Medium: Electronic Resource
    URL: http://dx.doi.org/10.1007/BF02023057
    Library Location Call Number Volume/Issue/Year Availability
    BibTip Others were also interested in ...
    Paper (German National Licenses)
    Fulltext
  • 8
    Electronic Resource
    Electronic Resource
    A heuristic for the Steiner problem in graphs (1996)
    Springer
    Computational optimization and applications 6 (1996), S. 5-14 
    Details
    ISSN: 1573-2894
    Keywords: Steiner problem ; heuristics ; minimum spanning tree ; testing
    Source: Springer Online Journal Archives 1860-2000
    Topics: Computer Science
    Notes: Abstract In this paper, we present a heuristic for the Steiner problem in graphs (SPG) along with some experimental results. The heuristic is based on an approach similar to Prim's algorithm for the minimum spanning tree. However, in this approach, arcs are associated with preference weights which are used to break ties among alternative choices of shortest paths occurring during the course of the algorithm. The preference weights are calculated according to a global view which takes into consideration the effect of all the regular nodes, nodes to be connected, on determining the choice of an arc in the solution tree.
    Type of Medium: Electronic Resource
    URL: http://dx.doi.org/10.1007/BF00248006
    Library Location Call Number Volume/Issue/Year Availability
    BibTip Others were also interested in ...
    Paper (German National Licenses)
    Fulltext
  • 9
    Electronic Resource
    Electronic Resource
    Minimization approach to membership evaluation in fuzzy sets and error analysis (1990)
    Springer
    Journal of optimization theory and applications 66 (1990), S. 275-287 
    Details
    ISSN: 1573-2878
    Keywords: Fuzzy sets ; degree of membership ; eigenvectors ; leastsquare problems ; decision making
    Source: Springer Online Journal Archives 1860-2000
    Topics: Mathematics
    Notes: Abstract Evaluation of the degree of membership in fuzzy sets is a fundamental topic in fuzzy set theory. Saaty (Ref. 1) proposes a method for solving this problem that has been widely accepted. In this paper, we examine the problem from an error minimization point of view that attempts to reflect the real intentions of the decision maker. When this approach is used, the findings reveal that fuzzy sets of different cardinalities have dramatically different requirements in the consistency level of the input data as far as the error minimization criterion is concerned.
    Type of Medium: Electronic Resource
    URL: http://dx.doi.org/10.1007/BF00939539
    Library Location Call Number Volume/Issue/Year Availability
    BibTip Others were also interested in ...
    Paper (German National Licenses)
    Fulltext
  • 10
    Electronic Resource
    Electronic Resource
    Active constraints, indefinite quadratic test problems, and complexity (1991)
    Springer
    Journal of optimization theory and applications 68 (1991), S. 499-511 
    Details
    ISSN: 1573-2878
    Keywords: Local minima ; global minima ; active constraints ; complexity theory ; indefinite quadratic test programs
    Source: Springer Online Journal Archives 1860-2000
    Topics: Mathematics
    Notes: Abstract The observation that at leasts constraints are active when the Hessian of the Lagrangian hass negative eigenvalues at a local minimizer is used to obtain two results: (i) a class of nearly concave quadratic minimization problem can be solved in polynomial time; (ii) a class of indefinite quadratic test problems can be constructed with a specified number of positive and negative eigenvalues and with a known global minimizer.
    Type of Medium: Electronic Resource
    URL: http://dx.doi.org/10.1007/BF00940067
    Library Location Call Number Volume/Issue/Year 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...