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
    Node and edge relaxations of the Max-cut problem (1994)
    Springer
    Computing 52 (1994), S. 123-137 
    Details
    ISSN: 1436-5057
    Keywords: 90C06 ; 90C27 ; Max-cut problem ; semidefinite programming ; min-max eigenvalue problem
    Source: Springer Online Journal Archives 1860-2000
    Topics: Computer Science
    Description / Table of Contents: Zusammenfassung Es wird eine obere Schranke für das Max-Cut Problem untersucht, die sich aus einer Relaxation des diskreten Problems zu einem stetigen, nichtlinearen konvexen Problem ergibt. Die Relaxation ist polynomial lösbar. Es werden die Grenzen des Ansatzes unter dem Einsatz fortgeschrittener Methoden aus numerischer linearer Algebra und nichtglatter Optimierung untersucht. Verschiedene Graphenklassen mit bis zu 50 000 Knoten und 4 Millionen Kanten werden mit dem Ansatz behandelt. Da die theoretische obere Schranke in der Praxis nur mit einer gewissen Genauigkeit bestimmt werden kann, wird ein Dualitätsmodell zwischen knoten- und kantenorientierten Relaxationen verwendet, um den Unterschied zwischen der theoretischen und der berechneten Schranke abzuschätzen.
    Notes: Abstract We study an upper bound on the max-cut problem defined via a relaxation of the discrete problem to a continuous nonlinear convex problem, which can be solved efficiently. We demonstrate how far the approach can be pushed using advanced techniques from numerical linear algebra and nonsmooth optimization. Various classes of graphs with up to 50 000 nodes and up to four million edges are considered. Since the theoretical bound can be computed only with a certain precision in practice, we use duality between node- and edge-oriented relaxations to estimate the difference between the theoretical and the computed bounds.
    Type of Medium: Electronic Resource
    URL: http://dx.doi.org/10.1007/BF02238072
    Library Location Call Number Volume/Issue/Year Availability
    BibTip Others were also interested in ...
    Paper (German National Licenses)
    Fulltext
  • 2
    Electronic Resource
    Electronic Resource
    Semidefinite Programs and Association Schemes (1999)
    Springer
    Computing 63 (1999), S. 331-340 
    Details
    ISSN: 1436-5057
    Keywords: Key words.Semidefinite programming, association scheme, maximum cut problem.
    Source: Springer Online Journal Archives 1860-2000
    Topics: Computer Science
    Notes: Abstract. We consider semidefinite programs, where the matrices defining the problem all arise from some association scheme. We show that in this case the semidefinite program can be solved through an ordinary linear program. As an application, we consider the max-cut problem, where the underlying graph arises from an association scheme.
    Type of Medium: Electronic Resource
    URL: http://dx.doi.org/10.1007/s006070050038
    Library Location Call Number Volume/Issue/Year Availability
    BibTip Others were also interested in ...
    Paper (German National Licenses)
    Fulltext
  • 3
    Electronic Resource
    Electronic Resource
    Buchbesprechungen (1989)
    Springer
    OR spectrum 11 (1989), S. 114-120 
    Details
    ISSN: 1436-6304
    Source: Springer Online Journal Archives 1860-2000
    Topics: Mathematics , Economics
    Type of Medium: Electronic Resource
    URL: http://dx.doi.org/10.1007/BF01746009
    Library Location Call Number Volume/Issue/Year Availability
    BibTip Others were also interested in ...
    Paper (German National Licenses)
    Fulltext
  • 4
    Electronic Resource
    Electronic Resource
    A Semidefinite Programming Approach to the Quadratic Knapsack Problem (2000)
    Springer
    Journal of combinatorial optimization 4 (2000), S. 197-215 
    Details
    ISSN: 1573-2886
    Keywords: semidefinite programming ; quadratic knapsack problem ; cutting planes ; 0/1 polytopes ; relaxations
    Source: Springer Online Journal Archives 1860-2000
    Topics: Mathematics
    Notes: Abstract In order to gain insight into the quality of semidefinite relaxations of constrained quadratic 0/1 programming problems we study the quadratic knapsack problem. We investigate several basic semidefinite relaxations of this problem and compare their strength in theory and in practice. Various possibilities to improve these basic relaxations by cutting planes are discussed. The cutting planes either arise from quadratic representations of linear inequalities or from linear inequalities in the quadratic model. In particular, a large family of combinatorial cuts is introduced for the linear formulation of the knapsack problem in quadratic space. Computational results on a small class of practical problems illustrate the quality of these relaxations and cutting planes.
    Type of Medium: Electronic Resource
    URL: http://dx.doi.org/10.1023/A:1009898604624
    Library Location Call Number Volume/Issue/Year Availability
    BibTip Others were also interested in ...
    Paper (German National Licenses)
    Fulltext
  • 5
    Electronic Resource
    Electronic Resource
    A recipe for semidefinite relaxation for (0,1)-quadratic programming (1995)
    Springer
    Journal of global optimization 7 (1995), S. 51-73 
    Details
    ISSN: 1573-2916
    Keywords: Quadratic boolean programming ; semidefinite programming ; bounds ; Lagrangian duality ; parametric programming ; trust region subproblems ; minmax eigenvalue problems ; quadratic assignment problem ; graph partitioning ; max-clique ; theta function
    Source: Springer Online Journal Archives 1860-2000
    Topics: Mathematics
    Notes: Abstract We review various relaxations of (0,1)-quadratic programming problems. These include semidefinite programs, parametric trust region problems and concave quadratic maximization. All relaxations that we consider lead to efficiently solvable problems. The main contributions of the paper are the following. Using Lagrangian duality, we prove equivalence of the relaxations in a unified and simple way. Some of these equivalences have been known previously, but our approach leads to short and transparent proofs. Moreover we extend the approach to the case of equality constrained problems by taking the squared linear constraints into the objective function. We show how this technique can be applied to the Quadratic Assignment Problem, the Graph Partition Problem and the Max-Clique Problem. Finally we show our relaxation to be best possible among all quadratic majorants with zero trace.
    Type of Medium: Electronic Resource
    URL: http://dx.doi.org/10.1007/BF01100205
    Library Location Call Number Volume/Issue/Year Availability
    BibTip Others were also interested in ...
    Paper (German National Licenses)
    Fulltext
  • 6
    Electronic Resource
    Electronic Resource
    Quadratic assignment problems on series-parallel digraphs (1986)
    Springer
    Mathematical methods of operations research 30 (1986), S. A161 
    Details
    ISSN: 1432-5217
    Keywords: Quadratic assignment problems ; series-parallel digraphs
    Source: Springer Online Journal Archives 1860-2000
    Topics: Mathematics , Economics
    Description / Table of Contents: Zusammenfassung Christofides hat gezeigt, daß das quadratische Zuordnungsproblem (QZP) auf isomorphen Bäumen polynomial lösbar ist. Der Ansatz von Christofides wird auf minimale serienparallele Digraphen verallgemeinert, und es wird gezeigt, daß das resultierende QZP äquivalent zum allgemeinen QZP ist, also NP-schwer. Die Einschränkung des Problems auf diejenigen serien-parallelen Digraphen, die keine bipartiten Teilgraphen enthalten, ist wieder polynomial lösbar. Dafür wird ein Algorithmus angegeben.
    Notes: Abstract Christofides has shown that the quadratic assignment problem (QAP) on isomorphic trees is solvable in polynomial time by dynamic programming. We generalize the approach to minimal series-parallel digraphs and show that this problem is equivalent to the general QAP, thus NP-hard. However the restriction to the subclass of series-parallel digraphs not containing bipartite subgraphs again is solvable in polynomial time. An algorithm for this class is given.
    Type of Medium: Electronic Resource
    URL: http://dx.doi.org/10.1007/BF01919179
    Library Location Call Number Volume/Issue/Year Availability
    BibTip Others were also interested in ...
    Paper (German National Licenses)
    Fulltext
  • 7
    Electronic Resource
    Electronic Resource
    k-Best constrained bases of a matroid (1990)
    Springer
    Mathematical methods of operations research 34 (1990), S. 79-89 
    Details
    ISSN: 1432-5217
    Keywords: k-best solutions ; ranking ; matroid intersections
    Source: Springer Online Journal Archives 1860-2000
    Topics: Mathematics , Economics
    Description / Table of Contents: Zusammenfassung Es wird eine Methode zur Bestimmung vonk-besten Basen eines Matroids vorgeschlagen. Die betrachteten Basen erfüllen noch zusätzliche partitionsartige Nebenbedingungen. Eine Anwendung dieses Problems wird erörtert.
    Notes: Abstract We propose a method for finding a set ofk-best bases of an arbitrary matroid where the bases are required to satisfy additional partitionlike constraints. An application of this problem is discussed.
    Type of Medium: Electronic Resource
    URL: http://dx.doi.org/10.1007/BF01415971
    Library Location Call Number Volume/Issue/Year Availability
    BibTip Others were also interested in ...
    Paper (German National Licenses)
    Fulltext
  • 8
    Electronic Resource
    Electronic Resource
    Book review (1995)
    Springer
    Mathematical methods of operations research 41 (1995), S. 56-56 
    Details
    ISSN: 1432-5217
    Source: Springer Online Journal Archives 1860-2000
    Topics: Mathematics , Economics
    Type of Medium: Electronic Resource
    URL: http://dx.doi.org/10.1007/BF01415064
    Library Location Call Number Volume/Issue/Year Availability
    BibTip Others were also interested in ...
    Paper (German National Licenses)
    Fulltext
  • 9
    Electronic Resource
    Electronic Resource
    Book reviews (1985)
    Springer
    Mathematical methods of operations research 29 (1985), S. 268-268 
    Details
    ISSN: 1432-5217
    Source: Springer Online Journal Archives 1860-2000
    Topics: Mathematics , Economics
    Type of Medium: Electronic Resource
    URL: http://dx.doi.org/10.1007/BF01918758
    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...