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
    Gröbner bases and triangulations of the second hypersimplex (1995)
    Springer
    Combinatorica 15 (1995), S. 409-424 
    Details
    ISSN: 1439-6912
    Keywords: 52 B 12 ; 13 P 10 ; 05 C 50
    Source: Springer Online Journal Archives 1860-2000
    Topics: Mathematics
    Notes: Abstract The algebraic technique of Gröbner bases is applied to study triangulations of the second hypersimplex Δ(2,n). We present a quadratic Gröbner basis for the associated toric idealK(K n ). The simplices in the resulting triangulation of Δ(2,n) have unit volume, and they are indexed by subgraphs which are linear thrackles [28] with respect to a circular embedding ofK n . Forn≥6 the number of distinct initial ideals ofI(K n ) exceeds the number of regular triangulations of Δ(2,n); more precisely, the secondary polytope of Δ(2,n) equals the state polytope ofI(K n ) forn≤5 but not forn≥6. We also construct a non-regular triangulation of Δ(2,n) forn≥9. We determine an explicit universal Gröbner basis ofI(K n ) forn≤8. Potential applications in combinatorial optimization and random generation of graphs are indicated.
    Type of Medium: Electronic Resource
    URL: http://dx.doi.org/10.1007/BF01299745
    Library Location Call Number Volume/Issue/Year Availability
    BibTip Others were also interested in ...
    Paper (German National Licenses)
    Fulltext
  • 2
    Electronic Resource
    Electronic Resource
    An algebraic geometry algorithm for scheduling in presence of setups and correlated demands (1995)
    Springer
    Mathematical programming 69 (1995), S. 369-401 
    Details
    ISSN: 1436-4646
    Keywords: Scheduling ; Chance constrained programming ; Integer programming ; Decomposition ; Gröbner basis ; Polynomial ideals
    Source: Springer Online Journal Archives 1860-2000
    Topics: Computer Science , Mathematics
    Notes: Abstract We study here a problem of schedulingn job types onm parallel machines, when setups are required and the demands for the products are correlated random variables. We model this problem as a chance constrained integer program. Methods of solution currently available—in integer programming and stochastic programming—are not sufficient to solve this model exactly. We develop and introduce here a new approach, based on a geometric interpretation of some recent results in Gröbner basis theory, to provide a solution method applicable to a general class of chance constrained integer programming problems. Out algorithm is conceptually simple and easy to implement. Starting from a (possibly) infeasible solution, we move from one lattice point to another in a monotone manner regularly querying a membership oracle for feasibility until the optimal solution is found. We illustrate this methodology by solving a problem based on a real system.
    Type of Medium: Electronic Resource
    URL: http://dx.doi.org/10.1007/BF01585566
    Library Location Call Number Volume/Issue/Year Availability
    BibTip Others were also interested in ...
    Paper (German National Licenses)
    Fulltext
  • 3
    facet.materialart.
    Unknown
    Test sets and inequalities for integer programs: extended abstract (1995)
    Details
    Publication Date: 2014-02-26
    Description: This paper presents some connections between test sets and valid inequalities of integer programs. The reason for establishing such relationships is the hope that information (even partial) on one of these objects can be used to get information on the other and vice versa. We approach this study from two directions: On the one hand we examine the geometric process by which the secondary polytope associated with a matrix $A$ transforms to the state polytope as we pass from linear programs that have $A$ as coefficient matrix to the associated integer programs. The second direction establishes the notion of classes of augmentation vectors parallel to the well known concept of classes of facet defining inequalities for integer programs. We show how certain inequalities for integer programs can be derived from test sets for these programs.
    Keywords: ddc:000
    Language: English
    Type: reportzib , doc-type:preprint
    Format: application/postscript
    Format: application/pdf
    Library Location Call Number Volume/Issue/Year Availability
    BibTip Others were also interested in ...
    OPUS
  • 4
    facet.materialart.
    Unknown
    Truncated Gröbner Bases for Integer Programming (1995)
    Details
    Publication Date: 2014-02-26
    Description: {\def\N{{\mbox{{\rm I\kern-0.22emN}}}}In this paper we introduce a multivariate grading of the toric ideal associated with the integer program $min \{ cx : Ax = b, x \in \N^n \}$, and a truncated Buchberger algorithm to solve the program. In the case of $max \{ cx : Ax \leq b, x \leq u, x \in \N^n \}$ in which all data are non-negative, this algebraic method gives rise to a combinatorial algorithm presented in UWZ94}.
    Keywords: ddc:000
    Language: English
    Type: reportzib , doc-type:preprint
    Format: application/postscript
    Format: application/pdf
    Library Location Call Number Volume/Issue/Year Availability
    BibTip Others were also interested in ...
    OPUS
Close ⊗
This website uses cookies and the analysis tool Matomo. More information can be found here...