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
    Testing balancedness and perfection of linear matrices (1993)
    Springer
    Mathematical programming 61 (1993), S. 1-18 
    Details
    ISSN: 1436-4646
    Keywords: Combinatorial optimization ; (0, 1) matrices ; integrality of polyhedra
    Source: Springer Online Journal Archives 1860-2000
    Topics: Computer Science , Mathematics
    Notes: Abstract A (0, 1) matrix is linear if it does not contain a 2×2 submatrix of all ones. In this paper we give polynomial algorithms to test whether a linear matrix is balanced or perfect. The algorithms are based on decomposition results previously obtained by the authors.
    Type of Medium: Electronic Resource
    URL: http://dx.doi.org/10.1007/BF01582135
    Location Call Number Expected Availability
    BibTip Others were also interested in ...
    Paper (German National Licenses)
    Fulltext
  • 2
    Electronic Resource
    Electronic Resource
    The equipartition polytope. I: Formulations, dimension and basic facets (1990)
    Springer
    Mathematical programming 49 (1990), S. 49-70 
    Details
    ISSN: 1436-4646
    Keywords: Equipartition polytope ; cut polytope ; Boolean quadratic programming
    Source: Springer Online Journal Archives 1860-2000
    Topics: Computer Science , Mathematics
    Notes: Abstract The following basic clustering problem arises in different domains, ranging from physics, statistics and Boolean function minimization. Given a graphG = (V, E) and edge weightsc e , partition the setV into two sets of ⌈1/2|V|⌉ and ⌊1/2|V|⌋ nodes in such a way that the sum of the weights of edges not having both endnodes in the same set is maximized or minimized. Anequicut is a feasible solution of the above problem and theequicut polytope Q(G) is the convex hull of the incidence vectors of equicuts inG. In this paper we give some integer programming formulations of the equicut problem, study the dimension of the equicut polytope and describe some basic classes of facet-inducing inequalities forQ(G).
    Type of Medium: Electronic Resource
    URL: http://dx.doi.org/10.1007/BF01588778
    Location Call Number Expected Availability
    BibTip Others were also interested in ...
    Paper (German National Licenses)
    Fulltext
  • 3
    Electronic Resource
    Electronic Resource
    The equipartition polytope. II: Valid inequalities and facets (1990)
    Springer
    Mathematical programming 49 (1990), S. 71-90 
    Details
    ISSN: 1436-4646
    Keywords: Equipartition polytope ; cut polytope ; Boolean quadratic programming
    Source: Springer Online Journal Archives 1860-2000
    Topics: Computer Science , Mathematics
    Notes: Abstract Theequipartition problem is defined as follows: given a graphG = (V, E) and edge weightsc e , partition the setV into two sets of ⌈1/2|V|⌉ and ⌊1/2|V|⌋ nodes in such a way that the sum of the weights of edges not having both endnodes in the same set is maximized or minimized. Anequicut is a feasible solution of the above problem and theequicut polytope Q(G) is the convex hull of the incidence vectors of equicuts inG. In this paper we describe some facet inducing inequalities of this polytope.
    Type of Medium: Electronic Resource
    URL: http://dx.doi.org/10.1007/BF01588779
    Location Call Number Expected 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...