Nothing Special   »   [go: up one dir, main page]
Skip to main content

Advertisement

Springer Nature Link
Log in

Fence facets from non-regular graphs for the linear ordering polytope

  • Original Paper
  • Published:
Optimization Letters Aims and scope Submit manuscript

Abstract

We present a new class of facet defining inequalities for the linear ordering polytope. The underlying graphs of these new inequalities are non-regular (have vertices of different degrees); the other known classes of fence inequalities are induced by regular graphs.

This is a preview of subscription content, log in via an institution to check access.

Access this article

Log in via an institution

Subscribe and save

Springer+ Basic
$34.99 /Month
  • Get 10 units per month
  • Download Article/Chapter or eBook
  • 1 Unit = 1 Article or 1 Chapter
  • Cancel anytime
Subscribe now

Buy Now

Price excludes VAT (USA)
Tax calculation will be finalised during checkout.

Instant access to the full article PDF.

Institutional subscriptions

Similar content being viewed by others

References

  1. Bolotashvili, G.G.: A class of facets of the permutation polytope and a method for constructing facets of the permutation polytope. Preprint VINITI N3403–B87, N3405–B87, (1987, in Russian)

  2. Cohen, M., Falmagne, J.-C.: Random utility representation of binary choice probabilities: a new class of necessary conditions. J. Math. Psych. 34, 88–94 (1990)

    Article  MATH  MathSciNet  Google Scholar 

  3. Christophe, J., Doinon, J.-P., Fiorini, S.: The biorder polytope. Order 21, 61–82 (2004)

    Article  MATH  MathSciNet  Google Scholar 

  4. Fishburn, P.C.: Binary probabilities induced by rankings. SIAM J. Discrete Math. 3, 478–488 (1990)

    Article  MATH  MathSciNet  Google Scholar 

  5. Grotschel, M., Junger, M., Reinelt, G.: Facets of the linear ordering polytope. Math. Program. 33, 43–60 (1985)

    Article  MathSciNet  Google Scholar 

  6. Koppen, M.: Random utility representation of binary choice probabilities: critical graphs yielding critical necessary conditions. J. Math. Psych. 39, 21–39 (1995)

    Article  MATH  MathSciNet  Google Scholar 

  7. Leung, J., Lee, J.: More facets from fances for linear ordering and acyclic subgraph polytopes. Discr. Appl. Math. 50, 185–200 (1994)

    Article  MATH  MathSciNet  Google Scholar 

Download references

Author information

Authors and Affiliations

  1. United Institute of Informatics Problems, National Akademy of Science of Belarus, Surganov St., 6, 220012 , Minsk, Belarus

    G. G. Bolotashvili

  2. Institute of Mathematics, National Akademy of Science of Belarus, Surganov St., 11, 220072 , Minsk, Belarus

    V. M. Demidenko

  3. Faculty of Economy, Belarus State University, Independence Av., 4, 220088 , Minsk, Belarus

    N. N. Pisaruk

Authors
  1. G. G. Bolotashvili
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. V. M. Demidenko
    View author publications

    You can also search for this author in PubMed Google Scholar

  3. N. N. Pisaruk
    View author publications

    You can also search for this author in PubMed Google Scholar

Corresponding author

Correspondence to N. N. Pisaruk.

Rights and permissions

Reprints and permissions

About this article

Cite this article

Bolotashvili, G.G., Demidenko, V.M. & Pisaruk, N.N. Fence facets from non-regular graphs for the linear ordering polytope. Optim Lett 8, 841–848 (2014). https://doi.org/10.1007/s11590-013-0625-6

Download citation

  • Received:

  • Accepted:

  • Published:

  • Issue Date:

  • DOI: https://doi.org/10.1007/s11590-013-0625-6

Keywords

Search

Navigation