Item Successfully Added to Cart
An error was encountered while trying to add the item to the cart. Please try again.
OK
Please make all selections above before adding to cart
OK
Share this page via the icons above, or by copying the link below:
Copy To Clipboard
Successfully Copied!
Polyhedral Computation
 
Edited by: David Avis McGill University, Montréal, QC, Canada
David Bremner University of New Brunswick, Fredericton, NB, Canada
Antoine Deza McMaster University, Hamilton, ON, Canada
A co-publication of the AMS and Centre de Recherches Mathématiques
Polyhedral Computation
Softcover ISBN:  978-0-8218-4633-9
Product Code:  CRMP/48
List Price: $89.00
MAA Member Price: $80.10
AMS Member Price: $71.20
eBook ISBN:  978-1-4704-1774-1
Product Code:  CRMP/48.E
List Price: $83.00
MAA Member Price: $74.70
AMS Member Price: $66.40
Softcover ISBN:  978-0-8218-4633-9
eBook: ISBN:  978-1-4704-1774-1
Product Code:  CRMP/48.B
List Price: $172.00 $130.50
MAA Member Price: $154.80 $117.45
AMS Member Price: $137.60 $104.40
Polyhedral Computation
Click above image for expanded view
Polyhedral Computation
Edited by: David Avis McGill University, Montréal, QC, Canada
David Bremner University of New Brunswick, Fredericton, NB, Canada
Antoine Deza McMaster University, Hamilton, ON, Canada
A co-publication of the AMS and Centre de Recherches Mathématiques
Softcover ISBN:  978-0-8218-4633-9
Product Code:  CRMP/48
List Price: $89.00
MAA Member Price: $80.10
AMS Member Price: $71.20
eBook ISBN:  978-1-4704-1774-1
Product Code:  CRMP/48.E
List Price: $83.00
MAA Member Price: $74.70
AMS Member Price: $66.40
Softcover ISBN:  978-0-8218-4633-9
eBook ISBN:  978-1-4704-1774-1
Product Code:  CRMP/48.B
List Price: $172.00 $130.50
MAA Member Price: $154.80 $117.45
AMS Member Price: $137.60 $104.40
  • Book Details
     
     
    CRM Proceedings & Lecture Notes
    Volume: 482009; 147 pp
    MSC: Primary 52; 90;

    Many polytopes of practical interest have enormous output complexity and are often highly degenerate, posing severe difficulties for known general-purpose algorithms. They are, however, highly structured, and attention has turned to exploiting this structure, particularly symmetry. Initial applications of this approach have permitted computations previously far out of reach, but much remains to be understood and validated experimentally.

    The papers in this volume give a good snapshot of the ideas discussed at a Workshop on Polyhedral Computation held at the CRM in Montréal in October 2006 and, with one exception, the current state of affairs in this area. The exception is the inclusion of an often cited 1980 technical report of Norman Zadeh, which was never published in a journal and has passed into the folklore of the discipline. This paper illustrates beautifully the work still to be done in the field: it gives a simple pivot rule for the simplex method for which it is still unknown if it yields a polynomial time algorithm.

    Titles in this series are co-published with the Centre de Recherches Mathématiques.

    Readership

    Graduate students and research mathematicians interested in discrete and computational geometry, combinatorial and continuous optimization, linear programming, enumeration algorithms, and computational complexity.

  • Table of Contents
     
     
    • Chapters
    • On combinatorial properties of linear program digraphs
    • Generating vertices of polyhedra and related problems of monotone generation
    • Polyhedral representation conversion up to symmetries
    • An output-sensitive algorithm for multi-parametric LCPs with sufficient matrices
    • Hyperplane arrangements with large average diameter
    • Enumerating the Nash equilibria of rank-1 games
    • What is the worst case behavior of the simplex algorithm?
    • Postscript to "What is the worst case behavior of the simplex algorithm?"
  • Additional Material
     
     
  • Requests
     
     
    Review Copy – for publishers of book reviews
    Accessibility – to request an alternate format of an AMS title
Volume: 482009; 147 pp
MSC: Primary 52; 90;

Many polytopes of practical interest have enormous output complexity and are often highly degenerate, posing severe difficulties for known general-purpose algorithms. They are, however, highly structured, and attention has turned to exploiting this structure, particularly symmetry. Initial applications of this approach have permitted computations previously far out of reach, but much remains to be understood and validated experimentally.

The papers in this volume give a good snapshot of the ideas discussed at a Workshop on Polyhedral Computation held at the CRM in Montréal in October 2006 and, with one exception, the current state of affairs in this area. The exception is the inclusion of an often cited 1980 technical report of Norman Zadeh, which was never published in a journal and has passed into the folklore of the discipline. This paper illustrates beautifully the work still to be done in the field: it gives a simple pivot rule for the simplex method for which it is still unknown if it yields a polynomial time algorithm.

Titles in this series are co-published with the Centre de Recherches Mathématiques.

Readership

Graduate students and research mathematicians interested in discrete and computational geometry, combinatorial and continuous optimization, linear programming, enumeration algorithms, and computational complexity.

  • Chapters
  • On combinatorial properties of linear program digraphs
  • Generating vertices of polyhedra and related problems of monotone generation
  • Polyhedral representation conversion up to symmetries
  • An output-sensitive algorithm for multi-parametric LCPs with sufficient matrices
  • Hyperplane arrangements with large average diameter
  • Enumerating the Nash equilibria of rank-1 games
  • What is the worst case behavior of the simplex algorithm?
  • Postscript to "What is the worst case behavior of the simplex algorithm?"
Review Copy – for publishers of book reviews
Accessibility – to request an alternate format of an AMS title
You may be interested in...
Please select which format for which you are requesting permissions.