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
    On the geometric structure of independence systems (1989)
    Springer
    Mathematical programming 45 (1989), S. 255-277 
    Details
    ISSN: 1436-4646
    Keywords: Independence system ; bouquet of matroids ; matroid ; the greedy algorithm
    Source: Springer Online Journal Archives 1860-2000
    Topics: Computer Science , Mathematics
    Notes: Abstract A bouquet of matroids is a combinatorial structure that generalizes the properties of matroids. Given an independence systemℐ, there exist several bouquets of matroids having the same familyℐ of independent sets. We show that the collection of these geometries forms in general a meet semi-lattice and, in some cases, a lattice (for instance, whenℐ is the family of the stable sets in a graph). Moreover, one of the bouquets that correspond to the highest elements in the meet semi-lattice provides the smallest decomposition ofℐ into matroidal families, such that the rank functions of the different matroids have the same values for common sets. In the last section, we give sharp bounds on the performance of the greedy algorithm, using parameters of some special bouquets in the semi-lattice.
    Type of Medium: Electronic Resource
    URL: http://dx.doi.org/10.1007/BF01589106
    Library Location Call Number Volume/Issue/Year Availability
    BibTip Others were also interested in ...
    Paper (German National Licenses)
    Fulltext
  • 2
    Electronic Resource
    Electronic Resource
    Facets for the cut cone I (1992)
    Springer
    Mathematical programming 56 (1992), S. 121-160 
    Details
    ISSN: 1436-4646
    Keywords: Max-cut problem ; cone ; polytope ; facet ; lifting ; hypermetric inequality
    Source: Springer Online Journal Archives 1860-2000
    Topics: Computer Science , Mathematics
    Notes: Abstract We study facets of the cut coneC n , i.e., the cone of dimension 1/2n(n − 1) generated by the cuts of the complete graph onn vertices. Actually, the study of the facets of the cut cone is equivalent in some sense to the study of the facets of the cut polytope. We present several operations on facets and, in particular, a “lifting” procedure for constructing facets ofC n+1 from given facets of the lower dimensional coneC n . After reviewing hypermetric valid inequalities, we describe the new class of cycle inequalities and prove the facet property for several subclasses. The new class of parachute facets is developed and other known facets and valid inequalities are presented.
    Type of Medium: Electronic Resource
    URL: http://dx.doi.org/10.1007/BF01580897
    Library Location Call Number Volume/Issue/Year Availability
    BibTip Others were also interested in ...
    Paper (German National Licenses)
    Fulltext
  • 3
    Electronic Resource
    Electronic Resource
    Facets for the cut cone II: Clique-web inequalities (1992)
    Springer
    Mathematical programming 56 (1992), S. 161-188 
    Details
    ISSN: 1436-4646
    Keywords: Cone ; polytope ; facet ; antiweb ; cut ; hypermetric inequality
    Source: Springer Online Journal Archives 1860-2000
    Topics: Computer Science , Mathematics
    Notes: Abstract We study new classes of facets for the cut coneC n generated by the cuts of the complete graph onn vertices. This cone can also be interpreted as the cone of all semi-metrics onn points that are isometricallyl 1-embeddable and, in fact, the study of the facets of the cut polytope is in some sense equivalent to the study of the facets ofC n . These new facets belong to the class of clique-web inequalities which generalize the hypermetric and cycle inequalities as well as the bicycle odd wheel inequalities.
    Type of Medium: Electronic Resource
    URL: http://dx.doi.org/10.1007/BF01580898
    Library Location Call Number Volume/Issue/Year Availability
    BibTip Others were also interested in ...
    Paper (German National Licenses)
    Fulltext
  • 4
    Electronic Resource
    Electronic Resource
    One-third-integrality in the max-cut problem (1995)
    Springer
    Mathematical programming 71 (1995), S. 29-50 
    Details
    ISSN: 1436-4646
    Keywords: Max-cut ; Cut polytope ; Metric polytope ; Linear relaxation ; One-third-integrality ; Box one-third-integrality ; Forbidden minor
    Source: Springer Online Journal Archives 1860-2000
    Topics: Computer Science , Mathematics
    Notes: Abstract Given a graphG = (V, E), the metric polytopeS (G) is defined by the inequalitiesx(F) − x(C∖F) ⩽ |F| − 1 for $$F \subseteq C$$ , |F| odd,C cycle ofG, and 0 ⩽x e ⩽ 1 fore ∈ E. Optimization overS (G) provides an approximation for the max-cut problem. The graphG is called 1/d-integral if all the vertices ofS(G) have their coordinates in{i/d ∣ 0 ⩽ i ⩽ d}. We prove that the class of 1/d-integral graphs is closed under minors, and we present several minimal forbidden minors for 1/3-integrality. In particular, we characterize the 1/3-integral graphs on seven nodes. We study several operations preserving 1/d-integrality, in particular, thek-sum operation for 0 ⩽k ⩽ 3. We prove that series parallel graphs are characterized by the following stronger property. All vertices of the polytopeS (G) ∩ {x ∣ ℓ ⩽ x ⩽ u} are 1/3-integral for every choice of 1/3-integral boundsℓ, u on the edges ofG.
    Type of Medium: Electronic Resource
    URL: http://dx.doi.org/10.1007/BF01592243
    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 generalization of antiwebs to independence systems and their canonical facets (1989)
    Springer
    Mathematical programming 45 (1989), S. 97-108 
    Details
    ISSN: 1436-4646
    Keywords: 0, 1 integer programming ; independence system ; facet ; antiweb
    Source: Springer Online Journal Archives 1860-2000
    Topics: Computer Science , Mathematics
    Notes: Abstract We consider independence system polytopes, i.e. polytopes whose extreme points are the incidence vectors of the sets of an independence system. We first give a sufficient condition for recognizing Boolean facets. Then, the notion of antiweb introduced by Trotter for graphs is generalized to independence systems and used for obtaining canonical facets of the associated polytopes. We also point out how our results relate with known ones for knapsack, set covering and matroid polytopes.
    Type of Medium: Electronic Resource
    URL: http://dx.doi.org/10.1007/BF01589098
    Library Location Call Number Volume/Issue/Year Availability
    BibTip Others were also interested in ...
    Paper (German National Licenses)
    Fulltext
  • 6
    Electronic Resource
    Electronic Resource
    Equilateral Dimension of the Rectilinear Space (2000)
    Springer
    Designs, codes and cryptography 21 (2000), S. 149-164 
    Details
    ISSN: 1573-7586
    Keywords: Touching number ; rectilinear space ; equidistant set ; cut metric ; design ; touching simplices
    Source: Springer Online Journal Archives 1860-2000
    Topics: Computer Science , Mathematics
    Notes: Abstract Itis conjectured that there exist at most 2k equidistantpoints in the k-dimensional rectilinear space.This conjecture has been verified for k ≤ 3; we show here its validity in dimension k = 4. We alsodiscuss a number of related questions. For instance, what isthe maximum number of equidistant points lying in the hyperplane: $$\sum\nolimits_{i = 1}^k {x_i } = 0?$$ If this number would be equal to k, then the above conjecture would follow. Weshow, however, that this number is ≥ k + 1 for k ≥ 4.
    Type of Medium: Electronic Resource
    URL: http://dx.doi.org/10.1023/A:1008391712305
    Library Location Call Number Volume/Issue/Year Availability
    BibTip Others were also interested in ...
    Paper (German National Licenses)
    Fulltext
  • 7
    Electronic Resource
    Electronic Resource
    DNA rearrangements linked to expression of a predominant surface antigen gene of trypanosomes (1983)
    [s.l.] : Nature Publishing Group
    Nature 302 (1983), S. 263-266 
    Details
    ISSN: 1476-4687
    Source: Nature Archives 1869 - 2009
    Topics: Biology , Chemistry and Pharmacology , Medicine , Natural Sciences in General , Physics
    Notes: [Auszug] To analyse the gene of the predominant antigen AnTat 1.3, we first prepared an AnTat 1.3-specific cDNA probe. Cloned populations of T. b. brucei (stock EATRO 1125) expressing the variable antigenic types AnTat 1.3 and AnTat 1.13 were obtained from infected rats as described previously19. Total ...
    Type of Medium: Electronic Resource
    URL: http://dx.doi.org/10.1038/302263a0
    Library Location Call Number Volume/Issue/Year Availability
    BibTip Others were also interested in ...
    Paper (German National Licenses)
    Fulltext
  • 8
    Electronic Resource
    Electronic Resource
    Evolution qualitative à long terme des rotifères du Lac Léman (1990)
    Springer
    Aquatic sciences 52 (1990), S. 156-161 
    Details
    ISSN: 1420-9055
    Keywords: Lake Geneva ; rotifers ; eutrophication ; long-term changes ; trophic indicators
    Source: Springer Online Journal Archives 1860-2000
    Topics: Biology
    Notes: Abstract Seventy-five species and lower taxonomic units of rotifers have been identified in Lake Geneva (= lac Léman); seven species and one form are new for the lake. When using indicators of trophic conditions, the qualitative composition of the biocenosis is still dominated by oligo-mesotrophic lake indicators, mixed with eutrophic and oligotrophic ones. However the rotifer biocenosis has not yet reached a steady state.
    Type of Medium: Electronic Resource
    URL: http://dx.doi.org/10.1007/BF00902377
    Library Location Call Number Volume/Issue/Year Availability
    BibTip Others were also interested in ...
    Paper (German National Licenses)
    Fulltext
  • 9
    Electronic Resource
    Electronic Resource
    Evolution quantitative à long terme des rotifères au cours de l'eutrophisation du Lac Léman (1990)
    Springer
    Aquatic sciences 52 (1990), S. 162-175 
    Details
    ISSN: 1420-9055
    Keywords: Lake Geneva ; rotifers ; long-term changes ; eutrophication ; population structure
    Source: Springer Online Journal Archives 1860-2000
    Topics: Biology
    Notes: Abstract Eutrophication in Lake Geneva (= Lake Léman) appears primarily as changes in chemical characteristics and plankton populations, inducing quantitative changes in the rotifer assemblages and species combinations. In the course of eutrophication, an increase of the rotifer abundance was found, together with settlement of new species and increase of eutrophication tolerant species, and despite the decrease or disappearance of eutrophication sensitive species. The new equilibrium in the trophic state of Lake Geneva related with the decreasing inputs of nutrients, induces a new structure and less abundance of the total pelagic rotatorian community.
    Type of Medium: Electronic Resource
    URL: http://dx.doi.org/10.1007/BF00902378
    Library Location Call Number Volume/Issue/Year Availability
    BibTip Others were also interested in ...
    Paper (German National Licenses)
    Fulltext
  • 10
    Electronic Resource
    Electronic Resource
    The cut cone III: On the role of triangle facets (1992)
    Springer
    Graphs and combinatorics 8 (1992), S. 125-142 
    Details
    ISSN: 1435-5914
    Source: Springer Online Journal Archives 1860-2000
    Topics: Computer Science , Mathematics
    Notes: Abstract The cut polytopeP n is the convex hull of the incidence vectors of the cuts (i.e. complete bipartite subgraphs) of the complete graph onn nodes. A well known class of facets ofP n arises from the triangle inequalities:x ij +x ik +x jk ≤2 andx ij −x ik −x jk ≤0 for 1≤i, j, k≤n. Hence, the metric polytopeM n , defined as the solution set of the triangle inequalities, is a relaxation ofP n .We consider several properties of geometric type forP n , in particular, concerning its position withinM n . Strengthening the known fact ([3]) thatP n has diameter 1, we show that any set ofk cuts,k≤log2 n, satisfying some additional assumption, determines a simplicial face ofMn and thus, also, ofP n . In particular, the collection of low dimension faces ofP n is contained in that ofM n . Among a large subclass of the facets ofP n , the triangle facets are the closest ones to the barycentrum ofP n and we conjecture that this result holds in general. The lattice generated by all even cuts (corresponding to bipartitions of the nodes into sets of even cardinality) is characterized and some additional questions on the links between general facets ofP n and its triangle facets are mentioned.
    Type of Medium: Electronic Resource
    URL: http://dx.doi.org/10.1007/BF02350631
    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...