Bibliothek

X
feed icon rss

Ihre E-Mail wurde erfolgreich gesendet. Bitte prüfen Sie Ihren Maileingang.

Leider ist ein Fehler beim E-Mail-Versand aufgetreten. Bitte versuchen Sie es erneut.

Vorgang fortführen?

Exportieren
  • 1
    Digitale Medien
    Digitale Medien
    On the symmetric travelling salesman problem I: Inequalities (1979)
    Springer
    Mathematical programming 16 (1979), S. 265-280 
    Details
    ISSN: 1436-4646
    Schlagwort(e): Linear Inequalities ; Convex Polytopes ; Facets ; Travelling Salesman Problem
    Quelle: Springer Online Journal Archives 1860-2000
    Thema: Informatik , Mathematik
    Notizen: Abstract We investigate several classes of inequalities for the symmetric travelling salesman problem with respect to their facet-defining properties for the associated polytope. A new class of inequalities called comb inequalities is derived and their number shown to grow much faster with the number of cities than the exponentially growing number of subtour-elimination constraints. The dimension of the travelling salesman polytope is calculated and several inequalities are shown to define facets of the polytope. In part II (“On the travelling salesman problem II: Lifting theorems and facets”) we prove that all subtour-elimination and all comb inequalities define facets of the symmetric travelling salesman polytope.
    Materialart: Digitale Medien
    URL: http://dx.doi.org/10.1007/BF01582116
    Bibliothek Standort Signatur Band/Heft/Jahr Verfügbarkeit
    BibTip Andere fanden auch interessant ...
    Artikel (Nationallizenzen)
    Volltext
  • 2
    Digitale Medien
    Digitale Medien
    Partial linear characterizations of the asymmetric travelling salesman polytope (1975)
    Springer
    Mathematical programming 8 (1975), S. 378-381 
    Details
    ISSN: 1436-4646
    Quelle: Springer Online Journal Archives 1860-2000
    Thema: Informatik , Mathematik
    Notizen: Abstract We consider the linear programming formulation of the asymmetric travelling salesman problem. Several new inequalities are stated which yield a sharper characterization in terms of linear inequalities of the travelling salesman polytope, i.e., the convex hull of tours. In fact, some of the new inequalities as well as some of the well-known subtour elimination constraints are indeed facets of the travelling salesman polytope, i.e., belong to the class of inequalities that uniquely characterize the convex hull of tours to an-city problem.
    Materialart: Digitale Medien
    URL: http://dx.doi.org/10.1007/BF01580454
    Bibliothek Standort Signatur Band/Heft/Jahr Verfügbarkeit
    BibTip Andere fanden auch interessant ...
    Artikel (Nationallizenzen)
    Volltext
  • 3
    Digitale Medien
    Digitale Medien
    On the facial structure of set packing polyhedra (1973)
    Springer
    Mathematical programming 5 (1973), S. 199-215 
    Details
    ISSN: 1436-4646
    Quelle: Springer Online Journal Archives 1860-2000
    Thema: Informatik , Mathematik
    Notizen: Abstract In this paper we address ourselves to identifying facets of the set packing polyhedron, i.e., of the convex hull of integer solutions to the set covering problem with equality constraints and/or constraints of the form “⩽”. This is done by using the equivalent node-packing problem derived from the intersection graph associated with the problem under consideration. First, we show that the cliques of the intersection graph provide a first set of facets for the polyhedron in question. Second, it is shown that the cycles without chords of odd length of the intersection graph give rise to a further set of facets. A rather strong geometric property of this set of facets is exhibited.
    Materialart: Digitale Medien
    URL: http://dx.doi.org/10.1007/BF01580121
    Bibliothek Standort Signatur Band/Heft/Jahr Verfügbarkeit
    BibTip Andere fanden auch interessant ...
    Artikel (Nationallizenzen)
    Volltext
  • 4
    Digitale Medien
    Digitale Medien
    The travelling salesman problem and a class of polyhedra of diameter two (1974)
    Springer
    Mathematical programming 7 (1974), S. 32-45 
    Details
    ISSN: 1436-4646
    Quelle: Springer Online Journal Archives 1860-2000
    Thema: Informatik , Mathematik
    Notizen: Abstract A class of polytopes is defined which includes the polytopes related to the assignment problem, the edge-matching problem on complete graphs, the multi-dimensional assignment problem, and many other set partitioning problems. Modifying some results due to Balas and Padberg, we give a constructive proof that the diameter of these polytopes is less than or equal to two. This result generalizes a result obtained by Balinski and Rusakoff in connection with the assignment problem. Furthermore, it is shown that the polytope associated with the travelling salesman problem has a diameter less than or equal to two. A weaker form of the Hirsch conjecture is also shown to be true for this polytope.
    Materialart: Digitale Medien
    URL: http://dx.doi.org/10.1007/BF01585502
    Bibliothek Standort Signatur Band/Heft/Jahr Verfügbarkeit
    BibTip Andere fanden auch interessant ...
    Artikel (Nationallizenzen)
    Volltext
  • 5
    Digitale Medien
    Digitale Medien
    On the symmetric travelling salesman problem II: Lifting theorems and facets (1979)
    Springer
    Mathematical programming 16 (1979), S. 281-302 
    Details
    ISSN: 1436-4646
    Schlagwort(e): Linear Inequalities ; Convex Polytopes ; Facets ; Lifting Theorems ; Travelling Salesman Problem
    Quelle: Springer Online Journal Archives 1860-2000
    Thema: Informatik , Mathematik
    Notizen: Abstract Four lifting theorems are derived for the symmetric travelling salesman polytope. They provide constructions and state conditions under which a linear inequality which defines a facet of then-city travelling salesman polytope retains its facetial property for the (n + m)-city travelling salesman polytope, wherem ≥ 1 is an arbitrary integer. In particular, they permit a proof that all subtour-elimination as well as comb inequalities define facets of the convex hull of tours of then-city travelling salesman problem, wheren is an arbitrary integer.
    Materialart: Digitale Medien
    URL: http://dx.doi.org/10.1007/BF01582117
    Bibliothek Standort Signatur Band/Heft/Jahr Verfügbarkeit
    BibTip Andere fanden auch interessant ...
    Artikel (Nationallizenzen)
    Volltext
  • 6
    Digitale Medien
    Digitale Medien
    (1,k)-configurations and facets for packing problems (1980)
    Springer
    Mathematical programming 18 (1980), S. 94-99 
    Details
    ISSN: 1436-4646
    Schlagwort(e): Integer Programming ; Integral Polyhedra ; Linear Inequalities ; Facets
    Quelle: Springer Online Journal Archives 1860-2000
    Thema: Informatik , Mathematik
    Notizen: Abstract A new class of facets for knapsack polytopes is obtained. This class of inequalities is shown to define a polytope with zero–one vertices only. A combinatorial inequality is obtained from Fulkerson's max—max inequality.
    Materialart: Digitale Medien
    URL: http://dx.doi.org/10.1007/BF01588301
    Bibliothek Standort Signatur Band/Heft/Jahr Verfügbarkeit
    BibTip Andere fanden auch interessant ...
    Artikel (Nationallizenzen)
    Volltext
  • 7
    Digitale Medien
    Digitale Medien
    Perfect zero–one matrices (1974)
    Springer
    Mathematical programming 6 (1974), S. 180-196 
    Details
    ISSN: 1436-4646
    Quelle: Springer Online Journal Archives 1860-2000
    Thema: Informatik , Mathematik
    Notizen: Abstract A zero–one matrix is called perfect if the polytope of the associated set packing problem has integral vertices only. By this definition, all totally unimodular zero–one matrices are perfect. In this paper we give a characterization of perfect zero–one matrices in terms offorbidden submatrices. Perfect zero–one matrices are closely related to perfect graphs and constitute a generalization of balanced matrices as introduced by C. Berge. Furthermore, the results obtained here bear on an unsolved problem in graph theory, the strong perfect graph conjecture, also due to C. Berge.
    Materialart: Digitale Medien
    URL: http://dx.doi.org/10.1007/BF01580235
    Bibliothek Standort Signatur Band/Heft/Jahr Verfügbarkeit
    BibTip Andere fanden auch interessant ...
    Artikel (Nationallizenzen)
    Volltext
  • 8
    Buch
    Buch
    Linear optimization and extensions : problems and solutions (2001)
    Berlin u.a. :Springer,
    Details
    Titel: Linear optimization and extensions : problems and solutions
    Autor: Alevras, Dimitris
    Beteiligte Person(en): Padberg, Manfred W.
    Verlag: Berlin u.a. :Springer,
    Erscheinungsjahr: 2001
    Seiten: 449 S.
    Serie: Universitext
    Materialart: Buch
    Bibliothek Standort Signatur Band/Heft/Jahr Verfügbarkeit
    BibTip Andere fanden auch interessant ...
    ZIB Katalog
    Zuse-Institut Berlin get availability status
  • 9
    Buch
    Buch
    Combinatorial optimization /; 12 (1980)
    Details
    Titel: Combinatorial optimization /; 12
    Beteiligte Person(en): Padberg, Manfred W.
    Erscheinungsjahr: 1980
    Seiten: VII, 221 S.
    Serie: Mathematical programming 12
    ISBN: 0-444-854-894
    Materialart: Buch
    Sprache: Englisch
    Bibliothek Standort Signatur Band/Heft/Jahr Verfügbarkeit
    BibTip Andere fanden auch interessant ...
    ZIB Katalog
    Zuse-Institut Berlin get availability status
Schließen ⊗
Diese Webseite nutzt Cookies und das Analyse-Tool Matomo. Weitere Informationen finden Sie hier...