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
Filter
  • 1970-1974  (3)
Source
Material
Years
Year
  • 1
    Electronic Resource
    Electronic Resource
    On the facial structure of set packing polyhedra (1973)
    Springer
    Mathematical programming 5 (1973), S. 199-215 
    Details
    ISSN: 1436-4646
    Source: Springer Online Journal Archives 1860-2000
    Topics: Computer Science , Mathematics
    Notes: 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.
    Type of Medium: Electronic Resource
    URL: http://dx.doi.org/10.1007/BF01580121
    Library Location Call Number Volume/Issue/Year Availability
    BibTip Others were also interested in ...
    Paper (German National Licenses)
    Fulltext
  • 2
    Electronic Resource
    Electronic Resource
    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
    Source: Springer Online Journal Archives 1860-2000
    Topics: Computer Science , Mathematics
    Notes: 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.
    Type of Medium: Electronic Resource
    URL: http://dx.doi.org/10.1007/BF01585502
    Library Location Call Number Volume/Issue/Year Availability
    BibTip Others were also interested in ...
    Paper (German National Licenses)
    Fulltext
  • 3
    Electronic Resource
    Electronic Resource
    Perfect zero–one matrices (1974)
    Springer
    Mathematical programming 6 (1974), S. 180-196 
    Details
    ISSN: 1436-4646
    Source: Springer Online Journal Archives 1860-2000
    Topics: Computer Science , Mathematics
    Notes: 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.
    Type of Medium: Electronic Resource
    URL: http://dx.doi.org/10.1007/BF01580235
    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...